1 Introduction
1.1 Motivation
1.2 Methods
2 Related work
-
A comprehensive cross-layer model for topology control problem is developed in which tools including power control, rate adaptation, channel assignment and selection, scheduling and routing are used.
-
A complete set of objectives such as throughput maximization, balancing and fairness is considered.
-
A decomposition-based heuristic method is proposed in order to reduce the computational complexity of the problem.
-
A new routing metric is introduced to determine the best K potential individual paths between node pairs based on the K-Connectivity feature
-
A channel assignment method based on the genetic algorithm is proposed to reduce the potential interference while preserves the K-Connectivity feature of the network
-
Genetic algorithm is used for power control and rate adaptation in order to determine the compatible links.
-
A heuristic method based on genetic algorithm is introduced for selecting the best path in order to provide fairness and balancing.
3 Network model and assumptions
4 Fault-tolerant topology control with throughput maximization, balancing and fairness (FTTC-TMBF)
-
\( {X}_{ijk}^{\omega t} \) is a binary variable which is equal to 1 if at least one packet in time slot t and frequency channel ω is transmitted from node i to node j with rate ρk.
-
\( {P}_{ij}^t \) is a real number from [0, Pmax] which shows the transmission power of link eijin time slot t .
-
\( {f}_{ijt}^{uv} \)represents the amount of traffic on link eijthat belongs to the traffic session (u, v) ∈ Q in time slot t.
Notation | Description |
---|---|
In
i
| Number of radio interfaces of node i |
R
| Set of M available transmission rates |
P
max
| Maximum transmission power |
Ω
| Set of non-overlapping channels |
ch
i
| Set of channels assigned to node i |
G
| Directed network graph |
V
| Set of n mesh routers |
E
| Set of directed links |
e
ij
| Directed link from node i to node j |
G
ij
| Propagation gain |
d
ij
| Geometric distance between two nodes i and j |
SINR
ij
| Signal to Interference and Noise Ratio in the receiver of link eij |
γ(ρ) | SINR threshold corresponding to the rate ρ |
N
0
| Thermal noise power |
\( {P}_{\mathrm{i}}^{min} \)
| Minimum transmission power of node i to satisfy K-degree requirement |
T
max
| Maximum number of time slots in a time frame |
P
ij
| Transmission power from node i to node j |
deg
i
| Degree of node i |
TD
uv
| The amount of traffic demand from source node u to destination node v |
\( {X}_{ijk}^{\omega t} \)
| A binary variable which is equal to 1 if the transmission from node i to node j is scheduled in time slot t with frequency channel ω and transmission rate ρk |
\( {P}_{ij}^t \)
| Transmission power of link eijscheduled in time slot t |
\( {f}_{ijt}^{uv} \)
| The amount of traffic belongs to traffic session (u, v) ∈ Q passed on link eij in time slot t |
\( {Z}_{ijt}^{uv} \)
| A binary parameter which is equal to 1 if \( {f}_{ijt}^{uv}\succ 0 \) |
υ(ρk) | The amount of transmitted traffic in one time slot at rate ρk |
C
uv
| End-to-end average throughput of traffic session (u, v) ∈ Q in each time slot |
SF
uv
| Satisfaction factor for each traffic session (u, v) ∈ Q |
\( {\sigma}_{SF}^2 \)
| Variance of satisfaction factor |
\( \overset{\_}{SF} \)
| Average satisfaction factor of all sessions |
\( {\sigma}_{SF}^{2,\max } \)
| Maximum variance of satisfaction factor |
\( {U}_n^i \)
| Utilization of node i |
\( {\sigma}_n^2 \)
| Variance of \( {U}_n^i \) |
\( {\overline{U}}_n \)
| Average utilization of all nodes |
\( {\sigma}_n^{2,\max } \)
| Maximum variance of node utilization |
\( {U}_c^{\omega } \)
| Utilization of channel ω |
\( {\sigma}_c^2 \)
| Variance of \( {U}_c^{\omega } \) |
\( {\overline{U}}_c \)
| Average utilization of all channels |
\( {\sigma}_c^{2,\max } \)
| Maximum variance of channel utilization |
5 The proposed heuristic solution for FTTC-TMBF problem
Notation | Description |
---|---|
K-Potential Best Paths Selection (KPBP) | |
NoPuv | Number of paths between two nodes u and v |
Pathuv, l | Indices of nodes on the lth path between two nodes u and v |
\( {\widehat{H}}_{uv,l} \) | Normalized value of the number of hops on the lth path between two nodes u and v |
\( {B}_{uv,l}^{n_x} \) | Number of usage of node nx located on the lth path between nodes u and v on other paths |
\( {P}_{uv,l}^{sum} \) | Total power consumption of links on the lth path between two nodes u and v |
\( {P}_{uv,l}^{max} \) | Maximum power consumption of links on the lth path between two nodes u and v |
\( {\widehat{P}}_{uv,l} \) | Normalize power factor on the lth path between two nodes u and v |
\( {B}_{uv,l}^{sum} \) | Total number of the usages of the nodes on the lth path between the two nodes u and v on other paths |
\( {B}_{uv,l}^{max} \) | Maximum number of the usages of the nodes on the lth path between the two nodes u and v on other paths |
\( {\widehat{B}}_{uv,l} \) | Normalized balance factor on the lth path between the two nodes u and v |
RCFuv, ℓ | Cost function of the lth path between nodes u and v |
ΓFTL | The set of required links to achieve a K-connected graph |
|ΓFTL| | Number of members in set ΓFTL |
Genetic Based Links Channel Assignment (GB-LCA) | |
\( {X}_{ij\omega}^{g\tau} \) | Gene in GB-LCA algorithm that is 1 if channel ω is assigned to link eij in generation g and chromosome τ |
Cgτ | Chromosome in GB-LCA algorithm |
Gg | Generation population |
PIgτ | Potential interference on each chromosome Cgτ belonging to generation g |
\( {\sigma}_{PI}^{2, g\tau} \) | Variance of potential interference in each chromosome |
\( {PI}_{\omega}^{g\tau} \) | Potential interference on each chromosome Cgτbelonging to generation g in frequency channel ω |
PIgmax | Maximum potential interference among all chromosomes of generation g |
\( {\sigma}_{PI}^{2,g\max } \) | Maximum variance of interference among all chromosomes of generation g |
COST(Cgτ) | Cost function of chromosome Cgτ |
Cgfa | First parent (Father) |
Cgma | Second parent (Mother) |
\( {\mathbf{C}}_c^{g\tau} \) | Children chromosome |
\( {\overset{\frown }{X}}_{ij\omega}^{g{\tau}_1} \) | Children gene |
\( {\mathbf{C}}_m^{g\tau} \) | Mutation chromosome |
μ | Mutation rate |
nm | Number of chromosomes resulting from mutation |
nμ | Number of mutated genes |
np | Number of chromosomes in current generation |
nc | Number of children chromosomes |
\( {\boldsymbol{\Gamma}}_{\omega}^{LCA} \) | Set of links with frequency channel ω ∈ Ω |
Genetic Based Compatible Sets Formation (GB-CSF) | |
\( {P}_{ij}^{g\tau} \) | Gene in GB-CSF that is the transmission power of each link eijbelonging to \( {\boldsymbol{\Gamma}}_{\omega}^{LCA} \) |
Sgτ | Chromosome in GB-CSF algorithm |
\( {\rho}_{ij}^{g\tau} \) | Transmission rate correspondent to gene \( {P}_{ij}^{g\tau} \) |
\( {\sigma}_{\rho}^{2, g\tau} \) | Transmission rate variance of links in the chromosome τ |
\( {\overline{\rho}}^{g\tau} \) | Transmission rate average of all links of the chromosome τ |
Pgmax | Maximum value of transmission power of the chromosome τ |
ρgmax | Maximum value of transmission rate of the chromosome τ |
\( {\sigma}_{\rho}^{2,g\max } \) | Maximum variance of transmission rate |
COST(Sgτ) | Cost function of chromosome Sgτ |
Sgfa | First parent (Father) |
Sgma | Second parent (Mother) |
\( {\mathbf{S}}_c^{g\tau} \) | Children chromosome |
\( {\overset{\frown }{P}}_{ij}^{g{\tau}_1} \) | Children gene |
\( {\mathbf{S}}_m^{g\tau} \) | Mutation chromosome |
\( {\tilde{P}}_{ij}^{g\tau} \) | Mutation gene |
Genetic Based Cross Layer Path Selection (GB-CLPS) | |
\( {X}_{uvk}^{g\tau} \) | This gene is 1 if kth path is selected for traffic flow of (u,v) |
Ρgτ | Chromosome in GB-CLPS algorithm |
\( {LT}_{ij}^{\tau } \) | Traffic on link eij when all paths are selected based on chromosome τ |
\( {\chi}_{uv{l}^{\prime}}^{ij} \) | A binary parameter that is 1 if link eijis on l’th path between nodes u and v |
\( {TN}_{\omega m}^{g\tau} \) | Number of time slots when mth configuration set is active on frequency channel ωin chromosome τ |
\( {\boldsymbol{\Gamma}}_m^{\omega } \) | Set of links belong to mth configuration set on frequency channel ω |
\( {\sigma}_{SF}^{2, g\tau} \) | Variance of satisfaction factor of different traffic flows |
\( {SF}_{uv}^{\tau } \) | Satisfaction factor of each traffic flow (u,v) |
\( {TN}_s^{g\max } \) | Maximum number of total time slots of all chromosomes |
\( {C}_{uv}^{\tau } \) | Transmission rate of the link on the path from u to v which requires maximum number of time slots for transmission |
\( {path}_{uv}^{\tau } \) | Set of links on the path selected between nodes u and v in chromosome τ |
\( {\sigma}_n^{2, g\tau} \) | Variance of node utilization |
\( {\sigma}_c^{2, g\tau} \) | Variance of frequency channel utilization |
\( {V}_a^{\tau } \) | Set of active nodes in chromosome τ |
\( {n}_a^{\tau } \) | Number of active nodes in chromosome τ |
\( {U}_i^{\tau } \) | Utilization of node i in chromosome τ |
\( {\overline{U}}_n^{\tau } \) | Average of node utilization in chromosome τ |
\( {\boldsymbol{\Omega}}_a^{\tau } \) | Set of active frequency channels in chromosome τ |
\( \left|{\boldsymbol{\Omega}}_a^{\tau}\right| \) | Number of active frequency channels in chromosome τ |
\( {U}_{\omega}^{\tau } \) | Utilization of frequency channel ω in chromosome τ |
\( {\overline{U}}_c^{\tau } \) | Average of frequency channel utilization in chromosome τ |
Pgfa | First parent (Father) |
Pgma | Second parent (Mother) |
\( {\mathbf{P}}_c^{g\tau} \) | Children chromosome |
\( {\overset{\frown }{X}}_{uvk}^{g\tau} \) | Children gene |
\( {\mathbf{P}}_m^{g\tau} \) | Mutation chromosome |