Wireless Netw DOI 10.1007/s11276-013-0676-8

Multi-layer optimization with backpressure and genetic algorithms for multi-hop wireless networks Yi Shi • Yalin E. Sagduyu • Jason H. Li

Ó Springer Science+Business Media New York 2013

Abstract This paper presents an efficient scheme to optimize multiple layers in multi-hop wireless networks with throughput objectives. Considering channel sensing and power control at the physical layer, a non-convex throughput optimization problem is formulated for resource allocation and a genetic algorithm is designed to allow distributed implementation. To address link and network layers, a localized back-pressure algorithm is designed to make routing, scheduling, and frequency band assignments along with physical-layer considerations. Our multi-layer scheme is extended to cognitive radio networks with different user classes and evaluate our analytical solution via simulations. Hardware-in-the-loop emulation test results obtained with real radio transmissions over emulated channels are presented to verify the performance of our distributed multi-layer optimization solution for multi-hop wireless networks. Finally, a security system is considered, where links have their security levels and data flows require certain security levels on each of its links. This problem is addressed by formulating additional constraints to the optimization problem.

Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Air Force Office of Scientific Research. Y. Shi (&)  Y. E. Sagduyu  J. H. Li Intelligent Automation Inc., 15400 Calhoun Drive, Rockville, MD 20855, USA e-mail: [email protected] Y. E. Sagduyu e-mail: [email protected] J. H. Li e-mail: [email protected]

Keywords Wireless networks  Multi-layer optimization  Throughput  Genetic algorithm backpressure algorithm

1 Introduction This paper considers maximizing the end-to-end throughput for multiple source-destination pairs in a multi-hop wireless network. Without any global network information available, we formulate a low-complexity multi-layer solution with communication strategies operating in two stages, channel sensing stage (to learn channel conditions) and actual data transmission stage. Resource allocation with throughput objectives has been studied mainly by two approaches. The first approach adopts (network) optimization techniques (see, e.g., [1, 2, 3, 4, 5]) to obtain optimal or near-optimal solutions. Solutions obtained by this approach may involve high complexity because of the strong coupling in multiple layers due to the interference effects. The second approach explores various insights into design of fast heuristics (see, e.g., [6, 7, 8]). Combining these two approaches, we design a multi-layer solution to integrate a genetic algorithm (GA) [9] for transmission power control with a back-pressure algorithm [10] that operates with local information for routing, scheduling, and frequency band assignments. These two algorithms combined in our multi-layer design solution balance channel sensing and transmission stages, and allow distributed implementation with low complexity. We begin our study at the physical layer and discuss various channel sensing schemes, where the channel state information is collected locally and exchanged among neighbor nodes. Our novel contribution lies in the integration of channel sensing results into transmission rate

123

Wireless Netw

and power optimization. In particular, we allow possible channel sensing errors included in the analysis and give a uniform representation for the achievable throughput and the corresponding overhead. In this formulation, we express the throughput achieved at any receiver with Shannon capacity formula depending on the Signal-toInterference-and-Noise (SINR). We use this expression in the initial optimization formulation and then show that our GA-based algorithm can actually work with any given capacity formula. As a novel testing approach, we use our real-time wireless emulation platform, RFnestTM [11] (previously developed by Intelligent Automation, Inc. and offered as a COTS product), and apply our throughput optimization results to the realistic SINR-throughput relationship of actual radios transmitting real packet traffic over emulated channels. Building upon physical-layer design, we apply the backpressure algorithm [10], which is a throughput-optimal joint scheduling and routing solution, to the link and network layers in a multi-hop network. Our novel contribution lies in the design of a distributed multi-layer solution with local decisions to set link weights for the physical layer problem. Then, we apply our combined solution to a cognitive radio network [12], where each cognitive radio node senses and identifies a set of available bands (not used by primary nodes) for data transmission and reception. We demonstrate the performance via simulations and highfidelity wireless emulation tests with real radio transmissions. Finally, we extend our multi-layer solution to a security system, where we ensure that data flows with certain security levels are transmitted on links with the same or higher security levels. The remaining of this paper is organized as follows. Section 2 describes channel sensing and data transmission at the physical layer. We develop a GA-based scheme for power control in Sects. 3 and 4 shows how to combine back-pressure algorithm and GA-based algorithm in a multi-hop network. We apply our solution to cognitive radio networks in Sect. 5 and present simulation and emulation results in Sects. 6 and 7 discusses extension to security systems and Sect. 8 concludes this paper.

2 Physical layer resource allocation for channel sensing and data transmission We consider a network with n links (transmitter-receiver pairs), each link (si, di) associated with a weight wi. In this section, we focus on single hop traffic and assume that one band is available at all nodes for simplicity. We will consider multi-hop operation in Sect. 4 and show how to set the weight for each link. The case of multiple bands and cognitive users will be considered in Sect. 5 We aim to

123

maximize the utility for all links, in terms of the sum of P weighted rates ni¼1 wi ri , where ri is the achievable data rate for link i. Data transmissions are performed on a frame-by-frame basis. We assume slow fading channels, i.e., channel gains remain constant in a given frame. There are two stages in each frame: channel sensing and data transmission. In the first (channel sensing) stage, each transmitter si uses the maximum power P and each receiver dj senses channel state that is expressed as the ratio between the received power gij P and background noise N0, where gij is the channel gain from si to dj. To simplify the notation, we assume the same noise power at all nodes. It can be shown that the same approach in this section can handle different noise powers. Then, receivers send channel state back to transmitters. In the second (transmission) stage, the optimal transmission power pi and the corresponding peak data rates are selected for each link i. 2.1 Channel sensing stage Channel sensing results may or may not be accurate. We begin with the simple case that channel sensing can provide accurate channel state. 2.1.1 Accurate channel sensing We consider different channel sensing approaches. A simple approach is that transmitter si of each link i transmits with the maximum power P in a separate time slot. At receiver dj of link j, the Signal-to-Noise-Ratio SNR (if j = i, i.e., dj is the intended receiver) or Interference-and-Noise-Ratio INR (if g j = i, i.e., dj is not the intended receiver) is Nij0 P, where gij is the channel gain from si to dj and N0 is background noise. Each receiver broadcasts SNR or INR values in one time slot. With TDMA, the total number of required time slots is 2n if n links are in a single collision domain. If n links are not in a single collision domain, multiple transmitters can transmit in the same time slot and the number of required time slots for transmissions can be smaller than n. This number is a constant for a given network topology. Furthermore, SNR or INR values need to be transmitted or relayed to all transmitters in the network. The number of required time slots for node dj’s data is not greater than the maximum number of hops from dj to all transmitters. The total number of required time slots is less than the sum of these hop numbers, since multiple SNR or INR values can be transmitted in the same time slot (if these transmissions are in difference collision domains). This number is also a constant for a given network topology. Therefore, the total number of required time slots is a constant (other than 2n) if n links are not in the same collision domain.

Wireless Netw

Another channel sensing approach lets all senders transmit (also with the maximum power P) in the same time slot. A receiver dj obtains its SINR value sij for signals from each transmitter i (1 B i B n) as sij ¼

N0 þ

gij P Pk6¼i

1kn

gkj P

¼

1þ

gij N0 P Pk6¼i gkj 1  k  n N0

P

:

ð1Þ

By solving n equalities of sij for 1 B i B n, receiver dj g can retrieve all channel states, Nij0 P. Finally, each receiver dj broadcasts these SNR or INR values in one separate time slot. The total number of required time slots is n ? 1 if n links are in a single collision domain. Otherwise, the number of required time slots is a constant determined by the network topology. Comparing the above two approaches, we find that the first approach requires more time slots but can provide channel states directly. The second approach requires less time slots but needs to solve a set of equalities for channel states, which may introduce numerical inaccuracy. There are other possible approaches such as dividing all transmitters into groups and letting transmitters in one group transmit in the same time slot. The number of required time slots is between the above two approaches. In all these schemes, the number of time slots to obtain SNR or INR values is a constant T that is determined by the network topology. 2.1.2 Inaccurate channel sensing g

We assume that Nij0 P is a constant but the measured value of channel state has a random error (depending on sensing scheme and channel conditions) that is modeled with normal distribution. To improve accuracy, a sender can transmit m (C 2) samples in m time slots1 to determine a confidence interval [13]. If we let each sender si transmit in one time slot, after collecting m samples, receiver dj can calculate a cong fidence interval [Lij, Uij] for Nij0 P under a given confidence

for some constant cij determined by d and the variation of all samples. Finally, each receiver dj broadcasts its intervals. The total number of required time slots is mn ? n if n links are in a single collision domain. If we let all senders transmit simultaneously in the same time slots, a receiver dj can obtain its SINR value sij for signal from each transmitter si as (1). After collecting m samples, receiver dj can calculate a confidence interval [sLij, sU ij ] for sij under a confidence requirement 1 - d, where sLij ¼ sij  dij ;

sU ij ¼ sij þ dij

ð1  i; j  nÞ;

and sij is the average of all samples. Similar to the previous case, since the measurement error follows a normal distribution, we have eij dij ¼ pffiffiffiffi ð1  i; j  nÞ; m where eij is a constant and can be determined by d and the variation of all samples. Therefore, receiver dj obtains sLij 

1þ

gij N0 P Pk6¼i gkj 1  k  n N0

P

 sU ij

ð1  i  nÞ:

By solving the above 2n inequalities, dj can obtain a cong fidence interval [Lij, Uij] for Nij0 P with a confidence level 1 - d. Finally, each receiver dj broadcasts its intervals. The total number of required time slots is m ? n, if n links are in a single collision domain. In both approaches, if links are not in a single collision domain, the total number of required time slots becomes a constant determined by the network topology. We find that both g approaches can provide a confidence interval [Lij, Uij] for Nij0 P with a confidence level 1 - d by using T time slots, where T is a constant that depends on the network topology. Note that accurate channel sensing is a special case of inaccurate channel sensing with Lij = Uij and d = 0. Therefore, we focus on the inaccurate channel sensing case in the following discussions.

g

requirement d such that the probability of Nij0 P 2 ½Lij ; Uij  is 1 - d. Since the measurement error follows a normal distribution, this interval can be determined by Lij ¼

gij P  Dij ; N0

where

gij N0

gij P þ Dij N0

ð1  i; j  nÞ;

Denote pi as the transmission power used by link i, which g will be optimally determined. Since each Nij0 P value is within its confidence interval [Lij, Uij], link i’s SINR sii is

P is the average of all samples and

cij Dij ¼ pffiffiffiffi m

1

Uij ¼

2.2 Transmission stage

ð1  i; j  nÞ;

The value of m should be set appropriately. If m is too small, sensing results may not be accurate enough; but if m is too large, the transmission stage is too short to achieve a large throughput. An appropriate value can be determined off-line by comparing the performance with different m values.

sii ¼

1þ

gii pi N0 P P Pj6¼i gji 1  j  n N0

p P Pj



1þ

Lii p^i Pj6¼i

1jn

Uji p^j

;

ð2Þ

where p^i ¼ pPi 2 ½0; 1 is the normalized transmission power. Therefore, link i’s peak data rate can be set as ! Lii p^i peak ¼ W log2 1 þ ri ; ð3Þ P 1 þ j61¼i j  n Uji p^j

123

Wireless Netw

where W is channel bandwidth. Transmissions may fail if gji gii N0 P\Lii or N0 P [ Uji for some j. Assuming these events  n are independent, the success probability is at least 1  d2 . Denote M as the total number of time slots in a frame. For 1 B i B n, we calculate link i’s average data rate in the whole frame by   MT d n peak ri ¼ 1 ri : M 2

ð4Þ

Remark 1 The rate ri may be larger than the value in (4) since (i) link i’s peak achievable data rate W log2 (1 ? sii) may be set larger than rpeak by (2) and (ii) even if link i’s i peak peak data rate is set as ri , the success probability may  n be larger than 1  d2 . We use (4) in our analysis to provide a conservative result (i.e., lower bound) for the achievable rate, since the computation of the exact value for ri is not straightforward and goes beyond the scope of this paper.Remark 2 Asymptotic capacity formula (3) for rpeak may not hold in a real system, as we will show in i Sect. 6.B. This formula serves as a reference in analysis. Our multi-layer optimization solution does not depend on a particular capacity formula. In addition to simulation results based on (3), we will also show emulation results in a real wireless system deployment with the actual SINR-throughput relationship in Sect. 6.B. 2.3 Problem formulation By considering both the sensing and transmission stages, we obtain the following optimization problem that maximizes the weighted sum rate by selecting transmission rates and powers. OPT  Power :

Pn maximize i¼1 wi ri subject to ð3Þ; ð4Þ variables ri  0; p^i 2 ½0; 1:

ð5Þ

In (5), ri and p^i are variables to optimize the weighted sum rate, and wi, M, T, d, n, W, Lij, and Uij are constants (Lij and Uij follow from the confidence interval computation in the sensing stage). OPT-Power is a non-convex program because of the interference terms in (3).

Fig. 1 Flow chart of GA

3 Resource allocation with power control Since OPT-Power should be solved online to support adaptation to network dynamics, we aim to design a low complexity algorithm. Our solution is based on genetic algorithm (GA) [9]. There are several components in GA (see Fig. 1). Initially, we need to represent a solution by a sequence of genes (i.e., chromosome). We also need to have a set of solutions (or individuals) as the first generation. GA tries to improve the current generation iteratively. During each iteration, GA evaluates individuals by a fitness function (in the form of an objective function) and then checks whether some terminating condition is met. If so, the best individual is returned as the solution and GA terminates. Otherwise, GA selects some individuals by their fitness values and breeds the next generation by crossover and mutation. This completes one iteration. In the following sections, we will present details for each component of the optimization solution we develop to solve OPT-Power. The GA solution developed in this section can be applied for single-hop networks with given links. It can also be applied as a part of the multi-layer solution for multi-hop networks, as we will see in Sect. 4. 3.1 Representation and initialization Selecting a suitable chromosome to represent a solution is the most important step in GA. A suitable chromosome should satisfy the requirements that it only includes necessary information such that we have a small search space and that it facilitates the design of crossover and mutation operations. By (4), all ri-values can be determined once we obtain pi-values. Then based on the first requirement, we only include pi-values in a chromosome to represent a solution. This chromosome also facilitates the design of crossover and mutation operations, as we will see in Sects. 3.3 and 3.4. The first generation may include the following solutions: (1) a solution with all pi = P, i.e., all senders transmit at the same time, (2) n solutions, each with only one pi = P and pj = 0 for all j = i, i.e., only one sender transmits, and (3) some randomly generated solutions.

Stop (1−θ)

Yes Representation Initialization

123

Evaluation

Meet terminating condition

No

Selection

θ

Crossover

(1−μ) μ

Mutation

Wireless Netw

3.2 Evaluation and termination For each solution, we calculate ri-values by (4). By P defining the fitness function as ni¼1 wi ri , we can evaluate each solution. GA checks a set of terminating conditions such as (1) the best individual has not been changed or the improvement on the objective value is negligible for a number of iterations and (2) the maximum number of iterations is reached. Once terminating conditions are met, GA terminates.

Each node exchanges local queue information with neighbor nodes and selects one of them as the next hop by using the sum of differential queue backlogs. Then, the power allocation is optimized for all scheduled transmitterreceiver pairs, where the sum of differential backlogs serves as the weight in rate maximization. Finally, each node uses the differential queue backlogs of individual sessions (source-destination pairs) to decide which session’s packets to transmit on the scheduled link. 4.2 The first time frame of back-pressure algorithm

3.3 Selection and crossover If terminating conditions are not met, GA selects a group of individuals as parents to breed new individuals (children) for the next generation. We use the Tournament selection scheme [14] to choose parents. That is, we randomly choose some individuals from the current generation each time. Among these individuals, the two with the best (largest) fitness values are selected as parents to generate new individuals. This selection procedure continues until certain pairs of parents are selected. Suppose that a pair of parents is u1 = {p11, p12, ..., p1n} and u2 = {p21, p22, ..., p2n}. With a probability h, two ^1 ¼ fp11 ; . . .; p1k ; p2;kþ1 ; . . .; p2n g and new individuals u ^2 ¼ fp21 ; . . .; p2k ; p1;kþ1 ; . . .; p1n g are bred by crossover at u a random crossover point k [ [1,n - 1]. With a probability (1 - h), new individuals are the same as the original individuals. 3.4 Mutation

In the first time frame, only source nodes are the potential transmitters and the following steps are followed: 1. 2.

3.

4.

For each new individual, with a probability l, GA randomly chooses one element (a transmission power) and changes its value to a random number in [0, P].

4 Resource allocation in multi-hop networks We now consider a multi-hop network and aim to maximize the minimum end-to-end rate among all source-destination pairs. We apply back-pressure algorithm [10] for routing and scheduling, and apply GA-based optimization approach developed in Sect. 3 for power control. 4.1 Back-pressure algorithm with local information Traditionally, back-pressure algorithm with local queue information was used for routing decisions based on fixed link rates [10]. In this paper, we consider variable link rates to be optimized via power control. To handle variable link rates, we enhance local back-pressure algorithm as follows.

In the sensing stage, channel states from each potential transmitter to all its neighboring nodes are measured. To determine the set of links for the transmission stage, each source node (potential transmitter) first tries to select a next hop node with the best channel condition. If multiple source nodes select the same node, the one with the best channel condition uses this node. If a source node is selected as a next hop, this source node cannot transmit and thus is not a potential transmitter anymore. To determine the transmission powers and the expected data rates, we set a weight for each source node by a default source rate (possibly different for each source) and apply our GA-based approach in Sect. 3 Based on the expected rate and the determined transmission power by GA, data transmissions are performed as follows. In the first time slot of transmission stage, each node transmits data at the expected rate and uses the transmission power determined by GA. If the actual SINR at the next hop node is no less than the required SINR to decode, the transmitted data is received; otherwise this transmission fails. We assume that a transmitter can have the feedback on its actual SINR and thus data rate can be adjusted for the subsequent time slots.

4.3 Subsequent time frames of back-pressure algorithm In subsequent time frames, every node maintains a queue for data from each source node. The queue length of a source node for its own data increases by its default rate for every time slot, while the queue length of a destination node for its own data is always zero. The following steps are followed: 1.

All nodes with positive queue lengths participate in the sensing stage as potential transmitters and measure

123

Wireless Netw

2.

3.

4.

conditions of channels to all its potential receivers, including its neighboring nodes with shorter queue length. To determine the set of links for the transmission stage, a potential transmitter tries to select its next hop node with the largest differential queue backlogs. Denote qi(l) as the queue length at node i for session P l. Node i selects node j as the next hop node if l P [qi(l) - qj(l)]? [ l [qi(l) - qk(l)]? for any other neighbor k, where [x]? = max(x,0). If there are multiple potential receivers with the same differential queue backlogs, the one with the best channel condition is selected. If multiple potential transmitters select the same node, tie is broken by considering differential queue backlogs and then channel conditions. To determine the transmission powers and the expected data rates, we set a weight for each selected transmitter-receiver pair by differential queue backlogs P ? l [qi(l) - qj(l)] , and apply GA developed in Sect. 3 In particular, the transmission powers of all scheduled links are selected by solving OPT-Power in (5), where the weight wi for any node i’s rate on scheduled link P (i, j) is selected as l [qi(l) - qj(l)]?. In the first time slot of transmission stage, each node transmits data at the expected rate and uses the transmission power determined by GA. If the actual SINR at the next hop node is no less than the required SINR to decode, the transmitted data is received; otherwise, this transmission fails. Based on the actual SINR, the transmitter adjusts its data rate for the subsequent time slots. A session l’s data can be transmitted by node i to j if [qi(l) - qj(l)] C 0. If multiple session’s data can be transmitted by node i, we need to determine which session’s data should be transmitted. For this purpose, we keep track of the delivered data for each session and the one with less delivered data has higher priority.

j senses a primary node’s activity, it sends Lbij = 0 and Ubij = 0 to the transmitter i. This easily extends our approach, since secondary users will not use a channel with zero channel gain. Transmissions on one band cannot interfere with other bands and therefore cannot affect the objective value on other bands. Thus, the problem for cognitive radio networks can be solved separately for each band as follows. For a particular band m, we apply the same approach in Sect. 4 to select a set of links to be active on this band. The only difference is that only some nodes (say nodes in Nm) can be active due to primary nodes’ activities on band m. Thus, the selection is among a subset of links associated with nodes in Nm and the overall solution follows from combining the solutions obtained for each band. Note that nodes in Nm exchange control information in band m, which causes some overhead considered in previous sections.

6 Performance evaluation We perform both simulation and emulation tests to evaluate the proposed approach. As the cognitive radio network model, we consider a randomly generated 10-node mobile network in a 100m 9 100m area (shown in Fig. 2). There are three randomly selected sessions (with rates R1, R2 and R3) and five bands, each with bandwidth W = 10 MHz and is assigned to some primary users. The default source rate is 100 Mbps. At each node, the available bands (free of primary nodes) depend on channel sensing results on primary users’ activities. A time frame is one second divided into M = 100 time slots. For simplicity, we assume the total time for channel sensing and other overhead combined is T = 10. The ratio between the maximum 100

R =0.03 1

5 Cognitive radio networks In a cognitive radio network [12], each secondary node can sense multiple frequency bands. If a band is not used by primary nodes, it is available to secondary nodes. A secondary node can choose any of the available bands for data transmission. We need to characterize an unavailable band such that our previous approach can be extended to solve the OPTPower problem when multiple bands are available at each node. For an unavailable band b, if a secondary transmitter i senses a primary node’s activity, it should not transmit on this band. This can be done by setting the channel status values Lbij and Ubij for band b as zero. If a secondary receiver

123

80

d1

d

2

d

3

s1 60

s2 s3

40

20

0

0

20

40

60

Fig. 2 Routing topology at the 9-th frame

80

100

Wireless Netw

transmission power and noise is given by NP0 ¼ 10000. Each node may move up to 5 m in one time frame and the confidence level for channel sensing is d = 0.05. For GA algorithm, we choose h = 0.4 and l = 0.2. We randomly select 20 individuals to obtain a pair of parents. The algorithm terminates after 100 iterations with no improvement. 6.1 Simulation We assume that the channel gain is determined by path loss, i.e., gij = d-2 ij in the far-field region for any link (i, j). Our algorithm determines first the potential active links and then the transmission power and data rate on each of these links. After the 9-th frame, the data from s1 is delivered to d1 for the first time. We show all activated links (i.e., till the 9-th frame) in Fig. 2. The average rate achieved so far is R1 = 0.03 Mbps. After the 20-th frame, data from all source nodes are delivered to their respective destinations (see Fig. 3) and the objective value (minimum end-to-end rate) achievable by the algorithm is 0.97 Mbps. At the end of simulation, we have the routing topology shown in Fig. 4 with the objective value of 1.56 Mbps. 6.2 Emulation We further evaluated the proposed multi-layer optimization solution with our high-fidelity wireless network emulation testbed that allows real wireless radios to send signals over emulated channels and digitally controls channel attenuation between radios. Our testbed platform consists of four main components: radio frequency network emulator simulator tool, RFnestTM [11] (previously developed by Intelligent Automation, Inc. and offered as a COTS product), software simulator running higher-layer protocols on 100

a PC host, configurable RF front-ends (RouterStation Pro from Ubiquiti), and digital switch. We executed real radio hardware tests at 2.462 GHz channel with 10 dBm transmission power, 10MHz bandwidth, and tunable transmission rate (1, 2, 5.5, or 11 Mbps) (Fig. 5). By moving radio positions, we realized different channel gains and consequently different received signal strength (RSS) values according to the channel attenuation model. We find that the ideal capacity (4) cannot be achieved in such real system. Instead, we obtain the SINR-throughput relationship in Fig. 6. If SINR is low, higher rates yield higher packet loss rates and a lower transmission rate can yield higher throughput. On the other hand, if SINR is high, high transmission rates are preferable because of the decrease in packet loss rate. In particular, if SINR is\4 dB, almost all transmissions fail (with throughput close to zero). From our optimization solution, it follows that the transmission rate should be set as 1, 2, 5.5, or 11 Mbps, respectively, if SINR is in the interval [4, 12] dB, [12, 14.2] dB, [14.2, 17.5] dB, or more than 17.5dB. By using these rate decisions, the data from s1 is transmitted to d1 for the first time after the 9-th frame with the average rate of R1 = 0.01 Mbps and all destinations receive the corresponding data after the 20-th frame with average rates at least 0.12 Mbps. At the end of emulation, we achieve rates R1 = 1.20 Mbps, R2 = 0.19 Mbps, and R3 = 0.58 Mbps, and the objective value is 0.19 Mbps. We can see that actual results in emulation are less than corresponding simulation results, i.e., simulation results are optimistic and cannot be achieved in real systems.

7 Extension to security considerations We extend the model to a security system, where sessions and links are associated with security levels. A session’s 100

R1=0.97 R2=0.98 R =0.97

d1 d3

80

d2

3

d1 d3

80

R =7.71 1 R =1.56 2 R =4.78 3

s1

s1

60

d2

60

s2

s

2

s3

40

40

s

3

20

0

20

0

20

40

60

Fig. 3 Routing topology at the 20-th frame

80

100

0

0

20

40

60

80

100

Fig. 4 Routing topology at the end of simulation

123

Wireless Netw

i and j, where the total queue length only includes the queued data for sessions with a security level equal to or lower than lij (because link (i, j) cannot carry other sessions).

8 Conclusion

Fig. 5 Programmable RFnestTM testbed

Fig. 6 The SINR-throughput relationship obtained via emulation tests

security level depends on its content, which is fixed for all packets of this session. Each node has a security level based on its role and a link’s security level depends on its transmitter and receiver nodes. Since nodes’ security levels are pre-determined and fixed, a node only needs to exchange this information with its neighbors once, which does not cause much overhead. In this setup, data of a session can only be transmitted along links with the same or a higher security level. Our multi-layer optimization solution can be extended by revising the multi-hop network optimization approach in Sect. 4 to satisfy security requirements as follows: 1.

2.

Suppose the minimal security level for all data queued at a transmitter i is lmin i . Then, a neighboring node with the corresponding link security level lower than lmin i will not be considered as a potential receiver for node i, because it cannot receive any data from node i. For a potential receiver j with security level lij on link (i, j), the weight of link (i, j) is determined by the difference between the total queue length at nodes

123

We designed an efficient scheme to optimize multiple layers in multi-hop wireless networks with throughput objectives. This scheme can support distributed implementation with local information only. At the physical layer, we considered both channel sensing stage and transmission stage, and formulated a non-convex program to maximize throughput by a GA-based scheme for power control. For routing, scheduling, and frequency band assignment problem at the link and network layers, we applied back-pressure algorithm with local information to maximize the minimum end-to-end throughput among source-destination pairs and integrated it with channel sensing and power control. We applied this solution to cognitive radio networks with different user priorities and showed the performance of our solution via both simulation results and wireless network emulation tests with real radios. We also discussed extensions to security systems, where data can only be transmitted on links with the same or higher security levels. Acknowledgments This material is based upon work supported by the Air Force Office of Scientific Research under STTR Contracts FA9550-12-C-0037, FA9550-10-C-0026 and FA9550-11-C-0006.

References 1. Alicherry, M., Bhatia, R., & Li, L. (2005). Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks. In Proceedins of ACM MobiCom, Cologne, Germany, Augest 28–September 2. 2. Andrews, M., & Dinitz, M. (2009). Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In Proceedings of IEEE INFOCOM, Rio de Janeiro, Brazil, April 19–25, pp. 1332–1340. 3. Bhatia, R., & Li, L. (2007). Throughput optimization of wireless mesh networks with MIMO links. In Proceedings of IEEE INFOCOM, Anchorage, AK, pp. 2326–2330. 4. Gao, C., Shi, Y., Hou, Y. T., & Kompella, S. (2011). On the throughput of MIMO-empowered multi-hop cognitive radio networks. IEEE Transactions on Mobile Computing, 10(11), 1505–1519. 5. Shi, Y., Hou, Y. T., Kompella, S., & Sherali, H. D. (2011). Maximizing capacity in multi-hop cognitive radio networks under the SINR model. IEEE Transactions on Mobile Computing, 10(7), 954–967. 6. Yuan, Y., Bahl, P., Chandra, R., Moscibroda, T., & Wu, Y. (2007). Allocating dynamic time-spectrum blocks in cognitive radio networks. In Proceedins of ACM MobiHoc, Montreal, Quebec, Canada, September 9–14.

Wireless Netw 7. Zhao, J., Zheng, H., & Yang, G. (2005). Distributed coordination in dynamic spectrum allocation networks. In Proceedings of IEEE DySPAN, Baltimore, MD, November 8–11, pp. 259–268. 8. Chen, C.C., & Lee, D.S. (2006). A joint design of distributed QoS scheduling and power control for wireless networks. In Proceedings of IEEE INFOCOM, Barcelona, Catalunya, Spain, April 23–29. 9. Dreo, J., Petrowski, A., Siarry, P., & Taillard, E. (2006). Metaheuristics for hard optimization: Methods and case studies. Berlin: Springer. 10. Tassiulas, L. (1995). Adaptive back-pressure congestion control based on local information. IEEE Transactions on Automatic Control, 40(2), 236–250. 11. Yackoski, J., Azimi-Sadjadi, B., Namazi, A., Li, J. H., Sagduyu, Y., & Levy, R. (2011). RF-NEST: Radio frequency network emulator simulator tool. In Proceedings of IEEE MILCOM, Baltimore, MD, November. 12. Cox, D. R., & Hinkley, D. V. (1974). Theoretical statistics. London: Chapman and Hall. 13. Wyglinski, A. M., Nekovee, M., & Hou, Y. T. (eds) (2010). Cognitive radio communications and networks: Principles and practices. Amsterdam: Elsevier. 14. Back, T., Fogel, D., & Michalewicz, Z. (eds) (1997). Handbook of evolutionary computation. New York, NY: Oxford University Press.

Author Biographies Yi Shi received his Ph.D. degree in computer engineering from Virginia Tech, in 2007. He is a Senior Research Scientist in Intelligent Automation Inc., Rockville, MD. His research focuses on algorithms and optimization for wireless networks, social networks, network coding, security, game theory, and big data. He was a recipient of IEEE INFOCOM 2008 Best Paper Award and the only Best Paper Award Runner-Up of IEEE INFOCOM 2011. He is an Editor for IEEE Communications Surveys and Tutorials. He served as a Co-Chair for ACM Workshop on Cognitive Radio Architectures for Broadband (CRAB) 2013 and a TPC member for many major

international conferences (including ACM MobiHoc and IEEE INFOCOM). Yalin E. Sagduyu received the B.S. degree from Bogazici University, Turkey, in Electrical and Electronics Engineering and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of Maryland at College Park. Dr. Sagduyu is currently a Program Manager at Intelligent Automation Inc., Rockville, MD. He has been a Graduate Research Assistant at the Institute for Systems Research of the University of Maryland, College Park, and a Postdoctoral Fellow at the Electrical Engineering and Computer Science Department of Northwestern University. His research interests are in the areas of design and optimization of wireless networks, cognitive radio networks, network coding, information theory, security, game theory, social networks, and Big Data. Jason H. Li received the Ph.D. degree in electrical and computer engineering from the University of Maryland, College Park. He is currently the Senior Director of the Networks and Security Group with Intelligent Automation Inc. (IAI), Rockville, MD. Before joining IAI, he was a Researcher with Hughes Network Systems, Germantown, MD. He is the author of more than 40 publications in the area of networks, protocols, security, and multiagent systems. His research interests include computer networks, networks and systems security; cyber security analysis; network management and control; distributed systems; and intelligent software agents. Dr. Li is a member of the Association for Computing Machinery (ACM), the Advanced Computing Systems Association (USENIX), and the Armed Forces Communications and Electronics Association. He has served on numerous Technical Program Committees for major IEEE/ ACM conferences on networks and security-related technologies.

123