Capacity-Optimized Access Scheduling Control for Heterogeneous MANETs with MIMO Links

Show more

1. Introduction

Recently, there are increasing interests in the use of wireless smart applications requiring higher data rate and reliability [1] . MIMO links can help to obtain this purpose. Conventional MIMO techniques have been widely studied in a centralized and infrastructure-based wireless networks [2] . Furthermore, MIMO-based adaptive scheduling algorithms in distributed manner have been also studied recently in [1] [2] . As a result, the benefits of MIMO links are now verified theoretically and experimentally as a promising approach to increase the network performance [3] .

However, most existing works in MIMO techniques focus on physical issues, such as increasing capacity and improving reliability [1] . In fact, a good access scheduling scheme should exploit the benefits of MIMO techniques and optimize the overall network performance while preserving some local distributed access property. Therefore, many upper layer aspects of networks with MIMO techniques merit further investigation, especially in mobile ad hoc networks (MANETs).

This paper will focus on access scheduling of MANETs taking impact of MIMO techniques into consideration. By carefully considering co-channel interference and contention issues, we propose a capacity-optimized access scheduling control (COASC) scheme for MANETs with MIMO links. Based on both upper layer network capacity and physical layer antenna selection, the access control problem in MANETs is formulated as a discrete stochastic approximation approach only with one-hop channel state information. To the best of our knowledge, COASC is the first access scheduling control scheme for MANETs with heterogeneous MIMO links and strong co-channel interference environments.

The rest of the paper is organized as follows. In Section 2, we introduce the system model and formulate the optimization problem. In Section 3, the proposed distributed interference-aware COASC scheme is described. Then, we present numerical results to demonstrate the performance improvement of the proposed strategy in Section 4. Finally, we conclude the paper in Section 5.

2. System Model and Problem Description

In this section, we describe the system model adopted in this paper and formulate the access scheduling control into an optimization problem based on the system model.

2.1. System Model

We consider resource scheduling schemes among MANET nodes that have different numbers of antenna elements and channel conditions, i.e., heterogeneous MANETs. As shown in Figure 1 [3] , in general, a MANET model involves two aspects: network nodes and connection links among them. Thus, we can use a graph $G\left(\mathcal{V}\mathrm{,}\mathcal{E}\right)$ to represent a MANET, where $\mathcal{V}$ and $\mathcal{E}$ are the sets of

(a) (b)

Figure 1. An illustration of network topology. (a) Topology example; (b) Corresponding channel contention.

nodes and edges in the network, respectively. A contention graph ${G}^{\prime}\left({\mathcal{V}}^{\prime}\mathrm{,}{\mathcal{E}}^{\prime}\right)$ can be generated based on the contention relationship among MIMO link flows, where ${\mathcal{V}}^{\prime}$ and ${\mathcal{E}}^{\prime}$ denote the links in the networks and relation weights between any two vertices in ${G}^{\prime}$ , respectively. Each link in the flow contention graph contents with each other and here ${W}_{x},x=1,\cdots ,10$ denotes the weight amount of interference between two links.

Usually, the spatial MIMO links between nodes ${n}_{k}$ and ${n}_{i}$ can be represen- ted as an antenna matrix [1] ,

${H}_{ki}=\left(\begin{array}{cccc}{h}_{11}& {h}_{12}& \dots & {h}_{1{N}_{i}}\\ {h}_{21}& {h}_{22}& \dots & {h}_{2{N}_{i}}\\ \vdots & \vdots & \ddots & \vdots \\ {h}_{{N}_{k}1}& {h}_{{N}_{k}2}& \dots & {h}_{{N}_{k}{N}_{i}}\end{array}\right)\mathrm{,}$ (1)

where ${N}_{k}$ and ${N}_{i}$ are the antenna numbers of nodes ${n}_{k}$ and ${n}_{i}$ , respectively. ${h}_{pq}$ denotes the spatial channel coefficient between the p-th antenna of node ${n}_{k}$ and q-th antenna of node ${n}_{i}$ . From [1] ,

${h}_{pq}=\sqrt{\frac{k}{k+1}}{\sigma}_{pq}{\text{e}}^{j\theta}+\sqrt{\frac{1}{k+1}}\mathcal{C}\mathcal{N}\left(\mathrm{0,}{\sigma}_{pq}^{2}\right)\mathrm{,}$ (2)

where parameter k, called k-factor, denotes the ratio of energy in specular path and in scattered paths. The larger of the k, the more deterministic of this channel. $\theta $ and $\epsilon $ are uniform phase constants and ${\sigma}_{pq}$ is a random variance. For ${h}_{pq}~\mathcal{C}\mathcal{N}\left(\mathrm{0,}{\sigma}_{l}^{2}\right)$ , the channel is called Rayleigh fading. Otherwise, the model is called Rician with k-factor.

Then, the maximal achievable rate of data flow s can be represented as [2] [4] ,

$C\left(s\right)=lo{g}_{2}\left(1+{P}_{s}{h}_{s}^{\mathrm{*}}{\left({N}_{0}{I}_{{N}_{d\left(s\right)}}+{\displaystyle \underset{q\in I\left(s\right)}{\sum}}{P}_{q}{h}_{q}{h}_{q}^{\mathrm{*}}\right)}^{-1}{h}_{s}\right)\mathrm{,}$ (3)

where ${P}_{s}$ is the transmission power of stream s. $d\left(s\right)$ is the terminal node of stream s. ${h}_{s}$ is the channel coefficient vector from transmitter antenna to receiver ones of stream s. ${N}_{0}$ is Gaussian white noise variance. $I\left(s\right)$ is the set of streams that interfere data stream s which will diminish the number of valid transmission antennas and reduce the system capacity. The data rate $C\left(s\right)$ can be estimated based on one-hop channel state condition and interference level during scheduling process.

2.2. Access Scheduling Control Formulation

An independent data flow from a source node in heterogeneous MANETs generally can be expressed by ${n}_{k}$ , ${n}_{i}$ , and ${I}^{ant}$ , where ${n}_{k}$ and ${n}_{i}$ represent transmitter and receiver, respectively, and ${I}^{ant}$ denotes the index of antenna which contains data flow. If we obtain the three parameters through optimization considerations, the access scheduling problem can be resolved easily. Therefore, the access scheduling control problem is how to select the three parameters to determine spectrum resource allocation for global optimal network performance. It can be formulated as [5] ,

$\begin{array}{l}{C}_{sum}\left({n}_{k}\mathrm{,}{n}_{i}\mathrm{,}{I}^{ant}\mathrm{,}{P}_{s}\right)\\ ={\mathrm{max}}_{\begin{array}{l}{n}_{k}\mathrm{,}{n}_{i}\mathrm{,}{I}^{ant}\mathrm{,}\\ {P}_{s}\mathrm{,}s=\mathrm{1,}\cdots \mathrm{,}{K}_{k}\end{array}}{Q}_{s}E\left[{\displaystyle \underset{{n}_{k}}{\sum}}{\displaystyle \underset{s}{\sum}}lo{g}_{2}\left(1+{P}_{s}{h}_{s}^{\mathrm{*}}{\left({N}_{0}{I}_{{N}_{d\left(s\right)}}+{\displaystyle \underset{q\in I\mathrm{(}s\mathrm{)}}{\sum}}{P}_{q}{h}_{q}{h}_{q}^{\mathrm{*}}\right)}^{-1}{h}_{s}\right)\right]\mathrm{,}\end{array}$ (4)

where ${K}_{k}$ is the number of data flows from ${n}_{k}$ . ${Q}_{s}$ denotes indicator function which equals 1 if stream s ia permitted to transmit. Otherwise, it equals 0. ${\sum}_{s=1}^{{K}_{k}}}{P}_{s}\le P$ and P denotes the total power constraint of each network node. ${C}_{sum}\left({n}_{k}\mathrm{,}{n}_{i}\mathrm{,}{I}^{ant}\mathrm{,}{P}_{s}\right)$ corresponds to the sum capacity of system. The network capacity expression is used as formulation objective function, which takes link capacity and interference into consideration. The optimal power allocation $\left({P}_{1}\mathrm{,}\cdots \mathrm{,}{P}_{{K}_{k}}\right)$ can maximize the sum capacity and it is jointly concave.

Proof: For the map from a set of powers to the corresponding sum rate, [4] , [5]

$\left({P}_{1}\mathrm{,}\cdots \mathrm{,}{P}_{{K}_{k}}\right)\stackrel{f}{\to}lo{g}_{det}\left({N}_{0}{I}_{{N}_{d\left(s\right)}}+{\displaystyle \underset{s=1}{\overset{{K}_{k}}{\sum}}}\text{\hspace{0.05em}}{P}_{s}{h}_{s}{h}_{s}^{\mathrm{*}}\right)\mathrm{,}$ (5)

the Lagrangian translation of the above optimization function is,

$\mathcal{L}\left({P}_{1}\mathrm{,}\cdots \mathrm{,}{P}_{{K}_{k}}\right)=-{\displaystyle \underset{s\mathrm{=1}}{\overset{{K}_{k}}{\sum}}}\text{\hspace{0.05em}}{\lambda}_{s}E\left[{P}_{s}\right]+E\left[lo{g}_{det}\left({N}_{0}{I}_{{N}_{d\left(s\right)}}+{\displaystyle \underset{s=1}{\overset{{K}_{k}}{\sum}}}\text{\hspace{0.05em}}{P}_{s}{h}_{s}{h}_{s}^{\mathrm{*}}\right)\right]\mathrm{.}$ (6)

Taking the optimal power allocation policy ${P}_{s}^{\mathrm{*}}$ satisfying Kuhn-Tucker equations,

$\frac{\partial \mathcal{L}}{\partial {P}_{s}}=(\begin{array}{cc}=0& \text{if}\text{\hspace{0.17em}}{P}_{s}^{*}>0\\ \le 0& \text{if}\text{\hspace{0.17em}}{P}_{s}^{*}=0.\end{array}$ (7)

We can obtain the following expressions,

${h}_{s}^{\mathrm{*}}{\left({N}_{0}{I}_{{N}_{d\left(s\right)}}+{\displaystyle \underset{j=1}{\overset{{K}_{k}}{\sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{P}_{j}{h}_{j}{h}_{j}^{\mathrm{*}}\right)}^{-1}{h}_{s}(\begin{array}{cc}={\lambda}_{s}& \text{if}\text{\hspace{0.17em}}{P}_{s}^{*}>0\\ \le {\lambda}_{s}& \text{if}\text{\hspace{0.17em}}{P}_{s}^{*}=0.\end{array}$ (8)

where ${\lambda}_{1}\mathrm{,}\cdots \mathrm{,}{\lambda}_{{K}_{k}}$ are equal in the statistical channel and equal each other. +

3. Capacity-Optimized Access Scheduling Control

Based on the access scheduling control formulation above, we will design CO-ASC to maximize the network capacity in this section. A discrete distributed scheduling approach will be used to solve this problem.

3.1. Flow Control Motivation

Carrier sense multiple access with collision avoidance (CSMA/CA) is a basic medium access control (MAC) protocol for MANETs. It has been proven that stream control for multiple interfering links which operate simultaneously can achieve better overall throughput performance compared to the scenario using TDMA and k streams each [6] . Stream control over CSMA/CA can significantly decrease the effect of co-channel interference based on the actual strength of interference and the degree of spatial correlation. As the number of mutually interfering links increases, the subset of streams used by each transmit pair decreases, which in turn increases the gain obtained from performing stream control [3] .

To effectively utilize the capability of MIMO links in MANETs, we should resolve the interference problem with flow/stream control over CSMA/CA, that is, to find the suitable streams transmitted by each node to maximize the overall network throughput.

3.2. Clique Identification

Definition 1 (Maximal Clique). Maximal clique refers to a clique that cannot be extended by including one more adjacent vertex in ${G}^{\prime}$ [7] .

To identify the interfering flows, we should first find all of the maximal cliques in ${G}^{\prime}$ . A discrete perfect elimination ordering (PEO) approach [8] can be used to solve it based on a theorem of lexicographic breadth first search (LexBFS) [9] .

Definition 2 (Clique Degree). Clique degree refers to the number of maximal cliques that each link belongs to. After obtaining the maximal cliques sets, we will classified all vertex in ${G}^{\prime}$ into two categories. One are vertexes which belong to more than one maximal clique, which are easier to be interfered by links of neighbor nodes and we refer them “Links A”. The other are residual and we refer them “Links B”, which can transmit simultaneously without bringing out obvious interference and collision.

3.3. Constraints

There are at least two constraint conditions that should be considered in the capacity-optimized access scheduling control problem. One is network data flow set ${K}_{k}$ , ${n}_{k}\in \mathcal{V}$ , which is also the basic element in the access scheduling control. Actually, the end-to-end flow transmitting is guaranteed via a hop-by-hop manner in the objective function. Each node is in charge of the connection chance with its neighbor links. If all neighbor connections are guaranteed, the end-to-end connectivity in the whole network can be preserved. Thus, “Links A” and “Links B” are adjusted by the collision conditions or busy channels.

The other aspect that determines network capacity is the persistence parameter p of flow [10] [11] . Although persistence parameter is mainly determined by MAC, its limitation is the exact knowledge of channel status that may not be available in distributed MANETs. Instead, we typically have an estimate of the channel access channel. Thus, the access scheduling control problem becomes a stochastic optimization problem. In the next section, we will solve this problem via a stochastic approximation approach.

3.4. Scheduling Approaches for COASC

Assume ${S}_{k}$ denotes a set of candidate streams from node ${n}_{k}$ in the network and ${s}_{kq}$ denotes the q-th stream of node ${n}_{k}$ . An intuitive brute force approach to solve the discrete stochastic problem in (4) is as follows. To obtain all candidate streams from all nodes in the network, we first select the available candidate streams, ${s}_{kq}$ , in the set of ${S}_{k}\mathrm{,}{n}_{k}\in \mathcal{V}$ , so as to satisfy the two constraints presented in the previous section. And then, we remove the transmission conflicts which correspond to the third constraints (i.e., a node cannot be a transmitter and receiver at the same time).

Algorithm 1 Distributed COASC algorithm

Require: Network Topology graph $G\left(\mathcal{V}\mathrm{,}\mathcal{E}\right)$ , spatial channel matrix of MIMO links and ${N}_{k}$ ,

${N}_{k}$ = number of antenna elements at each node ${n}_{k}$ .

Step1: (Initialization)

Obtaining link contention graph ${G}^{\prime}\left({\mathcal{V}}^{\prime}\mathrm{,}{\mathcal{E}}^{\prime}\right)$ based on antenna spatial channel coefficients with neighborhood nodes.

Step2 : (Classification)

Classifying vertices in ${G}^{\prime}$ into Links A and Links B.

1: Get vertice clique degree (d) of each MIMO link,

2: if $\forall s\in {\mathcal{V}}^{\prime}$ , $d\left(s\right)>1$ , then, classify it Links A,

3: otherwise, it belongs to Links B.

Step3: (Link Scheduling)

4: if $\forall s\in LinksA$ , rank the link based on p(s).

Step4: (Flow Scheduling)

Obtain all candidate streams ${S}_{k}$ and select streams ${s}_{kq}^{allo}$ from remaining available streams ${S}_{k}^{res}$ in spectrum S to satisfy optimization objective.

Start: $q=1,{s}_{kq}^{res}={s}_{kq}^{allo}$ .

5: while ${s}_{kq}^{res}>0$ and there are data flows need to be transmit,

6: if ${s}_{kq}^{allo}\le {s}_{kq}^{res}$

7: $\left\{{n}_{\mathrm{max}},{s}_{\mathrm{max}}\right\}\Leftarrow \mathrm{max}C\left({n}_{k},{n}_{i},p\left({s}_{kq}\right),{P}_{s}\right)$

Allocate antenna streams ${s}_{\mathrm{max}}$ for receiver ${n}_{\mathrm{max}}$ .

Then, remove transmit conflict under constraints (i.e., each node can’t be as transmitter and receiver simultaneously).

8: ${s}_{kq}^{res}={s}_{kq}^{res}-{s}_{kq}^{allo}$

9: ${S}_{k}\Leftarrow {S}_{k}-\left\{S\left({n}_{\mathrm{max}},{s}_{\mathrm{max}}\right)\right\}$ ;

10: else

Stop and wait to access scheduling.

11: end if

12: $q\Leftarrow q+1$

13: end while

14: if Streams are towards one receiver,

15: Use precoding and optimal power allocation [12] .

16: else

17: Power ${P}_{s}$ is evenly distributed.

18: end if

When channel conditions are not good, both the number of antennas to transmit streams and the number of nodes allocated to transmit are reduced to save transmitting power to improve the transmission efficiency. In the heterogeneous MANETs, node heterogeneity, channel condition, transmission reliability, traffic demand, and network road of each link are different with the unequal antenna array weight vector of stream gains, even in the presence of strong co- channel interference. We select the optimal streams in order to increase the network utilization with consideration of the correlation coefficients ${W}_{x}$ . The details can be found in the following algorithm process.

4. Simulated Results

In this section, we evaluate the performance of the proposed COASC algorithm in the environment of strong co-channel interference. Nodes are randomly distributed in a 1250 m × 1250 m area, where each node has a transmission range of 250 m and each packet contains 1000 bytes. The MIMO channels are randomly generated. The bandwidth of spectrum resource is 20MHZ and a transmission period is 2.5 ms.

Figures 2-5 demonstrate the impact of mean/variance of antenna array size on data rate (i.e., global network capacity) and also compare the capacity perfor-

Figure 2. Impact of mean of antenna array size.

Figure 3. Impact of mean of antenna array size.

Figure 4. Impact of variance of antenna array size.

Figure 5. Impact of variance of antenna array size.

mance of three centralized/distributed access scheduling schemes including one without interference consideration, one without stream control optimization [1] and our proposed optimal algorithm. As the mean of antenna array size grows, both data rate of centralized scheduling and distributed scheduling also grows with or without interference. Furthermore, variance of antenna array size representing degree of node heterogeneity in MANETs also impacts data rate. The smaller of this parameter, the more deterministic of this MIMO link. Therefore, the advantage of proposed scheme becomes obvious with increasing of variance of antenna array size. Thus, with global optimization, it obtains higher capacity performance than the ones without stream control.

Figure 6 and Figure 7 show the impact of node density on network capacity and compares the performance of these three different schemes. As the number of nodes becomes larger before saturated channels, the total data rate becomes larger with or without interference. In fact, when higher node density links are used, there are only part of the maximal possible number of streams to be selected. It can distribute its transmission power [12] just to the strongest channel streams. Therefore, compared to several interfering links operating using TDMA

Figure 6. Impact of node density.

Figure 7. Impact of node density.

in [1] and [2] , allowing the links operate simultaneously (i.e., “Links B”) with suitable stream control will result in improving the overall utilization of the network resource, which may be called stream control gains. With stream control access scheduling optimization, it obtains better performance than other two algorithms.

Figures 8-11 demonstrate the impact of traffic arrival rate/mobility on data rate (i.e., global network capacity) and also compare the capacity performance of three centralized/distributed access scheduling schemes. The incoming traffic

Figure 8. Impact of traffic arrival rate.

Figure 9. Impact of traffic arrival rate.

Figure 10. Impact of mobility.

Figure 11. Impact of mobility.

uses poisson process with a given mean value λ. λ becoming larger means that more data need to be transmitted. From Figures 8-11, we can find that in a range of speed varied (i.e., by changing the distance between nodes), the data rate is not significantly impacted by speed varied. However, with global optimization, it still obtains higher capacity performance than the ones without stream control.

5. Conclusion

To improve the network capacity of MANETs with MIMO links, we have proposed a capacity-optimized access scheduling control (COASC) scheme in this paper, which considers both upper layer medium antenna stream access scheduling and physical layer network capacity. A discrete stochastic approximation approach has been used to resolve the interference issue in fully distributed environments. Simulation results show that MIMO links have obviously impacts on the network capacity and COASC is an efficient strategy to exploit the benefit of MIMO links in MANETs. However, the energy conservation on this paper should be expanded in the further research.

Acknowledgements

This work was financially supported by the Natural Science Foundation of China (61201255), the Science and Technology Program of Guangzhou (2017070- 10490) and the Innovation Project of Graduate School of South China Normal University.

References

[1] Chu, S., Wang, X. and Yang, Y. (2014) Adaptive Scheduling in MIMO-Based Heterogeneous ad Hoc Networks. IEEE Transactions on Mobile Computing, 13, 964-979.

https://doi.org/10.1109/TMC.2013.112

[2] Chu, S. and Wang, X. (2009) Adaptive and Distributed Scheduling in Heterogeneous MIMO-Based Ad Hoc Networks. IEEE, International Conference on Mobile Adhoc and Sensor Systems IEEE, Macau, 12-15 October 2009, 217-226.

https://doi.org/10.1109/mobhoc.2009.5336995

[3] Sundaresan, K., Sivakumar, R., Ingram, M.A. and Chang, T.Y. (2004) Medium Access Control in Ad Hoc Networks with MIMI Links: Optimization Considerations and Algorithms. IEEE Transactions on Mobile Computing, 3, 350-365.

https://doi.org/10.1109/TMC.2004.42

[4] Cui, H., Wang, Y., Guan, Q. and Zhang, H. (2015) Distributed Interference-Aware Cooperative MAC Based on Stackelberg Pricing Game. IEEE Transactions on Vehicular Technology, 64, 4124-4134.

https://doi.org/10.1109/TVT.2014.2364734

[5] Tse, D. and Viswanath, P. (2005) Fundamentals of Wireless Commuication. Cambridge University Press, Cambridge, 486-450.

https://doi.org/10.1017/CBO9780511807213

[6] Zheng, J. and Ma, M. (2010) Qos-Aware Cooperative Medium Access Control for MIMO Ad-Hoc Networks. IEEE Communications Letters, 14, 48-50.

https://doi.org/10.1109/LCOMM.2010.01.091549

[7] Fulkerson, D.R. and Gross, O. (1965) Incidence Matrices and Interval Graphs. Pacific Journal of Mathematics, 15, 835-855.

https://doi.org/10.2140/pjm.1965.15.835

[8] Rose, D.J., Tarjan, R.E. and Lueker, G.S. (1976) Algorithmic Aspects of Vertex Elimination on Graphs. SIAM Journal on Computing, 5, 266-283.

https://doi.org/10.1137/0205021

[9] Nandagopal, T., Kim, T., Gao, X. and Bharghavan, V. (2000) Achieving MAC Layer Fairness in Wireless Packet Networks. MobiCom '00 Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, Boston, Massachusetts, 6-11 August 2000, 87-98.

https://doi.org/10.1145/345910.345925

[10] Cui, H., Li, J., Li, Z., Pan, D. and He, Y. (2016) Distributed Interference-Aware Cooperative Random Access in Multi-hop Wireless Networks. IEEE Access, 4, 4823-4828.

[11] Li, Z., Zhong, Q. and Cui, H. (2013) Cooperative Medium Access Control in Distributed Wireless Sensor Networks with Multiuser Diversity. Applied Mechanics and Materials, 321-324, 596-599.

https://doi.org/10.4028/www.scientific.net/AMM.321-324.596

[12] Demirkol, M.F. and Ingram, M.A. (2001) Power-Controlled Capacity for Interfering MIMO Links. IEEE VTS 54th Vehicular Technology Conference, 2001, VTC 2001 Fall, 1, 187-191.

https://doi.org/10.1109/vtc.2001.956583