Advanced
A Genetic Approach for Joint Link Scheduling and Power Control in SIC-enable Wireless Networks
A Genetic Approach for Joint Link Scheduling and Power Control in SIC-enable Wireless Networks
KSII Transactions on Internet and Information Systems (TIIS). 2016. Apr, 10(4): 1679-1691
Copyright © 2016, Korean Society For Internet Information
  • Received : November 04, 2015
  • Accepted : March 03, 2016
  • Published : April 30, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
About the Authors
Xiaodong, Wang
College of Computer National University of Defense Technology, Changsha, 410073, P. R. China
Hu, Shen
College of Computer National University of Defense Technology, Changsha, 410073, P. R. China
Shaohe, Lv
College of Computer National University of Defense Technology, Changsha, 410073, P. R. China
Xingming, Zhou
College of Computer National University of Defense Technology, Changsha, 410073, P. R. China

Abstract
Successive interference cancellation (SIC) is an effective means of multi-packet reception to combat interference at the physical layer. We investigate the joint optimization issue of channel access and power control for capacity maximization in SIC-enabled wireless networks. We propose a new interference model to characterize the sequential detection nature of SIC. Afterward, we formulize the joint optimization problem, prove it to be a nondeterministic polynomial-time-hard problem, and propose a novel approximation approach based on the genetic algorithm (GA). Finally, we discuss the design and parameter setting of the GA approach and validate its performance through extensive simulations.
Keywords
1. Introduction
I n the last decade, wireless networks have gained worldwide popularity and has attracted considerable industrial and research attention. However, the congestion issue in which tens or hundreds of links contend for a common channel has become a network bottleneck and severely limits the applications of wireless networks, particularly in overloaded traffic scenarios.
The emerging successive interference cancellation (SIC) [1] , one of the advanced signal-processing techniques, can decode multiple concurrent signals and exhibits a potential to mitigate the congestion issue in wireless networks. The principle of SIC is described as follows:
(1) A signal can basically be extracted when the signal-to-interference-plus-noise ratio (SINR) is larger than a given threshold even when some interfering signals exist;
(2) When a new signal is successfully decoded, the corresponding received signal can be regenerated and removed from the received composite one to reduce the interference in the remaining signals;
(3) The SIC-enabled receiver repeats these two steps until the desired signals are all successfully decoded or the decoding process is interrupted.
Compared with other multi-packet reception (MPR) techniques, the SIC-enabled receiver utilizes a single decoder iteratively, which reduces the hardware cost significantly. However, several urgent issues need to be considered seriously in the deployment of SIC [2] . First, the design of link scheduling is challenging because too few links selected to transmit simultaneously would waste the concurrent opportunity, whereas too many links or wrong selection would produce considerable interference, such that the desired signals cannot be extracted. Second, the power control for the selected links is also challenging because it determines the feasible data transmission rate.
The relationship between link scheduling and power control is interactive, that is, pure link scheduling cannot realize the concurrent potential of the SIC technique thoroughly, whereas the combination of link scheduling and power control can improve the concurrent feasibility of link sets and enhance the transmission rate of concurrent links. However, the interplay between link scheduling and power control renders the situation highly complicated.
In this study, the two dependent issues of link scheduling and power control are unified with a genetic algorithm (GA)-based framework [3] . First, a new physical interference model referred to as SIC-PHY is proposed to characterize the sequential detection nature of SIC. Second, an algorithm is presented to evaluate the transmission capacity of a link in the SIC-enhanced decoding process. Third, considering that the joint link scheduling and power control issue is proven to be a nondeterministic polynomial-time (NP)-hard problem, a novel GA-based solution is proposed. Finally, various simulations are conducted to show the advantage of the proposed solution.
The remainder of this paper is organized as follows. Section 2 summarizes related work, and Section 3 presents the physical interference model and problem formulation. Section 4 introduces the design of the GA-based approach. Section 5 provides the simulation and numerical results, and Section 6 presents the conclusions.
2. Related Work
SIC has been implemented in the software-defined radio platform and nearly achieved the Shannon capacity of multi-user additive white Gaussian noise (AWGN) channels [4] .
However, several stringent SINR constraints and hard limits need to be addressed by SIC; hence, careful transmission scheduling and assignment are required. In [5] , Gelal et al. proposed a topology-control framework that greedily forms and activates sub-topologies in a manner that exploits successful SIC decoding. In [6] , Lv et al. studied the link-scheduling problem for SIC-enabled wireless networks, and an independent set-based greedy scheme was proposed to construct a maximal feasible schedule. In [7] , Jiang et al. introduced a crosslayer optimization framework that incorporates variables at physical, link, and network layers in the context of multi-hop SIC-enabled wireless networks.
Only a few existing studies have considered the issue of power control [8 - 10] . Although power control can significantly enhance the transmission capacity of SIC-enabled networks, the corresponding complexity remains an issue.
3. System Model and Problem Formulation
- 3.1 SINR-based Interference Model
Considering a wireless network consisting of n nodes and N transmission links in the link set L , we let N 0 denote the average AWGN power, Pi the transmission power of the i -th link, and Sij = Pi /( ϑ ∙| dij | η ) the received signal power of the i -th link at the receiver side of the j -th link, where ϑ is the path-loss constant, η is the path-loss exponent (2 ≤ η ≤ 6), and dij is the distance between the transmitter of the i -th link and the receiver of the j -th link. Signal Sij is successful if the SINR is above a certain reception threshold β , that is,
PPT Slide
Lager Image
where αk ∈ {0,1} is the variation denoting whether the j -th link is in activation ( αk = 1) or not ( αk = 0). The feasible data rate of the j -th link is provided as follows:
PPT Slide
Lager Image
For simplicity, the bound in Equation (2) is approximated as an equation. Equations (1) and (2) show that a few links can be transmitted simultaneously and that network transmission performance is severely limited by the traditional reception techniques.
- 3.2 SIC-enabled Interference Model (SIC-PHY)
By utilizing SIC, a novel MPR technique that cancels the decoded signals to improve the SINR value of the remaining signal iteratively, the decoding constraint of Equation (1) can be relaxed significantly, and more concurrent links are enabled in the same transmission time slot.
We consider the SIC sequential detection nature of two concurrent links, the i -th and j -th links. The transmission of the i -th link cause much interference to the j -th link because the
SINR-decoding constraint of the j -th link cannot be satisfied, that is,
PPT Slide
Lager Image
Meanwhile, in SIC-enabled networks, the concurrent transmission of the i -th and j -th links can be successfully decoded as follows:
  • 1) Decoding strong interference: whenSijis sufficiently strong to tolerate the interference from thej-th link, the receiver of thej-th link can decode the signal of thei-th link, which is the strong interference of thej-th link;
  • 2) Decoding the desired signal: when the transmission of thei-th link is decoded, the corresponding interference can be removed from the original received signal, and the desired signal of thej-th link may be successfully decoded from the remaining signal.
In each single iterative process of SIC-enabled decoding, the SINR constraint is still assumed to be satisfied, that is,
PPT Slide
Lager Image
The SIC sequential detection nature can be generalized to an arbitrary number of concurrent links, and the relaxed decoding constraint with SIC can be expressed as follows:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the link set denoting the corresponding signals decoded successfully and removed from the composite received signal before the decoding process of signal Sij . The feasible data rate of the j -th link in SIC-enabled networks can be extended to
PPT Slide
Lager Image
- 3.3 Achievable Transmission Capacity Calculation
Equations (2) and (5) show two issues related to improving network performance. These two are the link-scheduling mechanism, which determines the links that access the common channel by adjusting parameter αi ( i L ), and the power control mechanism, which selects the appropriate transmission power Pi ( i L ) to increase the data rate or reduce the interference. Given that the interplay between link scheduling and power control is complicated, coordinating them independently is challenging.
In this study, we construct a unified framework for link scheduling and power control. N transmission links in the wireless network, with a given discrete transmission power set
PPT Slide
Lager Image
are assumed to be scheduled in m ( N > m ) time slots, and each link is scheduled exactly once.
Given a solution of link scheduling and power control P = {( ti , Pi )| i L , 1 ≤ ti m , Pi P }, which schedules the i -th link in time slot ti with transmission power Pi , by denoting the active link set in time slot ti by La ( ti ), we can calculate the achievable transmission capacity of the i -th link in the solution P , ri ( P ) as the following Algorithm 1 :
PPT Slide
Lager Image
The first part of Algorithm 1 , lines 1 to 11 pseudocode, checks the half-duplex restriction of the concurrent link set La ( ti ). On the one hand, any two concurrent links cannot share the same sender node; on the other hand, the sender node of one link cannot be the receiver node of another concurrent node. Considering that the SIC technique aims to resolve collision capability, concurrent links can share the same receiver node.
- 3.4 Formulization of the Maximum Capacity Problem (MCP)
MCP with joint link scheduling and power control can be formulized as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where Equation (6.a) illustrates that the objective of MCP is to maximize the total achievable transmission capacity of the scheduling links in the considered network, Equations (6.b) and (6.c) demonstrate that all links are scheduled exactly once with minimum transmission capacity threshold γ , and Equation (6.d) restricts the range of transmission power.
Proposition 1: MCP is NP-hard.
Proof: The proof is that the special case of MCP with γ = 0, m = 2, Pi = P ( i L ) can be reduced from the partition problem, a well-known NP-complete problem [11] , in a polynomial time. The proof detail is similar to that in [12] , and interested readers can refer to this reference. Given that a special case of the problem is NP-hard, the general case is NP-hard as well. ■
4. GA-based Approach
- 4.1 Design Challenges
As one of the most popular stochastic optimization algorithms and a powerful solution to NP-hard problems, GA is introduced to solve MCP in this study
The principal ideas of the GA approach are to represent the solutions of the target problem as chromosome-like codes; evaluate the chromosome codes with genetic mechanisms [3] , such as individual selection, crossover, and mutation; and determine the optimal solution with the maximum fitness index.
- 4.2 Chromosome Coding
We employ a bit string to code the solution in MCP, as shown in Fig. 1 .
  • (1) A chromosome-like individual consists ofNstrings {str i:(αi:Pi),i∈L}
  • (2) Each individual string is divided into two sub-strings,andand presents an instance of link scheduling and power control for a link.
  • (3) A link scheduling (or power control) sub-stringconsists of some bits, the length of which is determined by the number of time slots,m(or candidate transmission power,s).
  • (4) If a bit in a sub-stringequals 1, then the corresponding time slotj(or transmission power) is selected for thei-th link; otherwise, thei-th link is silent in time slotj(or transmission poweris not selected for thei-th link).
  • (5) The restriction, ∀i∈Lshould be satisfied to guarantee that each individual string coding is a feasible solution of the optimization problem.
PPT Slide
Lager Image
Chromosome-like individual of MCP
As an example, we consider a wireless network that consists of 12 communication links. A chromosome-like individual then comprises 12 sub-strings, and the string str 1 = (00100;00010) denotes that the first link is scheduled in time slot 3 with transmission power
PPT Slide
Lager Image
- 4.3 Fitness Function
The fitness value of a chromosome-like individual determines the probability of the individual to participate in the reproduction process. Given that the objective of MCP is to determine the optimal solution of link scheduling and power control, the fitness value is supposed to characterize the feasibility of joint scheduling solution and the total achievable transmission capacity as follows: if the solutions do not satisfy Constraints (6.b), (6.c), and (6.d), then their corresponding fitness values are set to 0; otherwise, the fitness value of a feasible solution is set to the total achievable transmission capacity of concurrent links.
Fitness function F ( X ) can be expressed as
PPT Slide
Lager Image
where X is a chromosome-like individual and PX is the corresponding scheduling solution.
- 4.4 Genetic Operations
The initial individuals are randomly produced, and only the individual strings that satisfy the restriction
PPT Slide
Lager Image
, ∀ i L can be reserved in the initial generation. A new generation of offspring individuals with high fitness values is reproduced by using several basic genetic operations, such as individual selection, crossover, and mutation. When the number of evolution steps exceeds a predefined threshold
PPT Slide
Lager Image
or the fitness value stops to refresh in predefined evolution steps a (the improvement of optimal fitness is less than predefined threshold T ), the evolution process is interrupted, and the individual with the highest fitness value in the last generation is determined to be the optimal solution of MCP.
(1) Individual Selection : From the current generation of chromosome-like individuals, the size of which is denoted by SC , a part of individuals, SP , with a relatively high fitness value is selected to form the basis of a new generation.
(2) Individual Crossover : From the individuals selected by step (1), several individuals with probability pc are selected to perform the crossover operation illustrated in Fig. 2 . That is, a pair of individuals exchange some strings, the crossover point is randomly selected in the intersection positions of two strings, and the new produced individuals are added to the new generation.
(3) Individual Mutation : From the individuals selected by step (1), several individuals with probability pm are selected to perform the mutation operation. That is, some bits in the individual substrings are randomly changed. Given that the newly generated solution may be infeasible, an additional repair step is executed to accelerate the convergence process. With the link string str 1 = (00100;00010) as an example, if its second bit turns to “1” from “0,” str 1 = (01100;00010) , then link 1 is scheduled to two time slots, namely, slots 2 and 3. The third bit should turn to “0,” str 1 = (01000;00010) , to ensure the feasibility of the new solution.
PPT Slide
Lager Image
Illustration of the crossover process
The condition SC = (1 + pc + pm ) · SP should be satisfied to guarantee the stability of the evolution process.
- 4.5 GA Process
Given the algorithm designs presented in Sub-sections 4.2, 4.3, and 4.4, GA-SIC is proposed as follows:
PPT Slide
Lager Image
5. Experimental Results
We evaluate the proposed GA-SIC algorithm by implementing it on our customized C++ platform. Without loss of generality, 50 homogeneous nodes in our network are randomly deployed in a 1200 × 1200 m square shape, and 35 point-to-point links are selected to be scheduled in 10 transmission time slots with five different transmit power levels. All transmissions are implement in a half-duplex model. The path-loss constant ϑ , path-loss exponent η , and reception threshold β are set to 2, 2, and 10, respectively.
We set generation threshold
PPT Slide
Lager Image
Many numerical experiments are executed to investigate five performance-related effect factors, namely, population size SP , crossover probability pc , mutation probability pm , network size N , and network topology (rand or grid). The default parameters are set to SP = 50, pc = 0.5, pc = 0.3, and N = 35. The default network topology is rand.
The results of the simulation experiments are discussed below.
- 5.1 Effect of Genetic Operation Parameters
As shown in Fig. 3 , when the population size is small ( SP < 50), the capability of searching for optimized solutions and the achievable fitness value increases rapidly with the population size. When the population size reaches 50, the difference between the achievable fitness value and the global optimal one is only 2.40%. Thus, continuously increasing the population size would not increase the performance considerably but would introduce additional complication.
PPT Slide
Lager Image
Effect of population size
The effects of crossover and mutation probabilities are presented in Figs. 4 and 5 , respectively. When the crossover or mutation probability is too small, GA is premature; when the crossover or mutation probability is too large, the stability of GA decreases. The achievable fitness values in both cases are not satisfactory. In summary, the reasonable genetic operation parameters in our network scenario are population size SP = 50, crossover probability pc = 0.5, and mutation probability pm = 0.3.
PPT Slide
Lager Image
Effect of crossover probability
PPT Slide
Lager Image
Effect of mutation rate
- 5.2 Effect of Network Parameters
The effects of network size and topology are presented in Figs. 6 and 7 , respectively. The following findings are obtained.
(1) When the network has a relatively small size ( N < 35), improving the number of communication links can provide new concurrent opportunities and thus enhance the total network transmission capacity; however, a large number of links will introduce considerable interference among concurrent links and cause damage to network transmission performance.
(2) The network transmission performance of the rand network remarkably exceeds that of the grid network, and the performance gain can reach almost 40%; the rand network has higher diversity of communication links, which provides more concurrent opportunities.
PPT Slide
Lager Image
Effect of network size
PPT Slide
Lager Image
Effect of network toplogy
6. Conclusions
We investigated the joint optimization issue of channel access and power control for capacity maximization in SIC-enabled wireless networks. First, we formulized the joint optimization problem under a new physical interference model to characterize the sequential detection nature of SIC and proved it to be an NP-hard problem. Second, we introduced a GA-based approach. Finally, extensive simulations were performed to demonstrate that our GA-based approach is promising in solving the joint optimization problem.
BIO
Xiaodong Wang is a professor at Science and Technology on Parallel and Distributed Processing Laboratory, College of Computer, National University of Defense Technology (NUDT), China. He obtained his Ph.D., M.D, and B.S. degrees in computer science from NUDT in 2002, 1998, and 1996, respectively. His research interests include social networks, wireless ad hoc networks, and wireless sensor networks.
Hu Shen is a Ph.D. candidate at Science and Technology on Parallel and Distributed Processing Laboratory, College of Computer, National University of Defense Technology (NUDT), Changsha, China. He obtained his B.S. degree majoring in automation from Tsinghua University, Beijing, China, in 2008. He obtained his M.D. degree majoring in computer science from NUDT in 2010. His research interests include cooperation communication, resource allocation, and transmission protocol design for wireless networks with multi-packet reception capability.
Shaohe Lv is an assistant professor at Science and Technology on Parallel and Distributed Processing Laboratory, College of Computer, National University of Defense Technology (NUDT), China. He obtained his Ph.D., M.D., and B.S. degrees in computer science from NUDT in 2011, 2005, and 2003, respectively. He was a visiting Ph.D. student at the University of Waterloo, Canada, from December 2008 to December 2009. His research interests include cooperation communication and medium access control design in ad hoc networks. He received the Best Paper Award from the IEEE International Conference on Communications in 2012.
Xingming Zhou is currently affiliated with Science and Technology on Parallel and Distributed Processing Laboratory, College of Computer, National University of Defense Technology, China, where he has been a professor since 1986. He is a member of the China Academic of Science. His research interests include computer architecture, high-performance computing, and wireless networking.
References
Halperin D. , Anderson T. E. , Wetherall D. “Taking the Sting Out of Carrier Sense: Interference Cancellation for Wireless LANs,” in Proc. of ACM the ACM Annual International Conference on Mobile Computing and Networking (MOBICOM) 2008 339 - 350
Sen S. , Santhapuri N. , Choudhury R. R. “Successive Interference Cancellation: A Back-of-the-Envelope Perspective,” in Proc. of ACM SIGCOMM Workshop on Hot Topics in Networks (Hotnets) 2010
Davis L. D. 1991 Handbook of Genetic Algorithms. Van Nostrand New York
Viterbi A. J. 1990 “Very Low Rate Convolutional Codes for Maximum Theoretical Performance of Spreadspectrum Multiple-Access Channels,” IEEE Journal on Selected Areas in Communication (JSAC) 8 641 - 49    DOI : 10.1109/49.54460
Gelal E. , Pelechrinis K. , Kim T.S. , Broustis I. , Krishnamurthy S.V. , Rao B. “Topology control for effective interference cancellation in multi-user MIMO networks,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM) Mar. 2010 1 - 9
Lv S. , Zhuang W. , Wang X. 2011 “Link Scheduling in Wireless Networks with Successive Interference Cancellation,” Elsevier Computer Networks Journal 55 (13) 2929 - 2941    DOI : 10.1016/j.comnet.2011.06.008
Jiang C. , Shi Y. , Hou Y. T. “Squeezing the Most Out of Interference: An Optimization Framework for Joint Interference Exploitation and Avoidance,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM) 2012 424 - 432
Shi H. Y. , Wang W. L. , Kwok N. M. , Chen S. Y. 2012 “Game Theory for Wireless Sensor Networks: A Survey,” Sensors 9055 - 9097    DOI : 10.3390/s120709055
St. Jean C. A. , Jabbari B. 2009 “On Game-Theoretic Power Control under Successive Interference Cancellation,” IEEE Transactions on Wireless Communications 8 (4) 1655 - 1657    DOI : 10.1109/TWC.2009.080317
Zappon A. , Jorswieck E. “Game-theoretic Resource Allocation in Relay-assisted DS/CDMA Systems with Successive Interference Cancellation,” IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) May 2011 3208 - 3211
Garey M. , Johnson D. 1979 Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman &Co.
Mollanoori M. , Ghaderi M. “On the Complexity of Wireless Uplink Scheduling with Successive Interference Cancellatoin,” in Proc. of 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) Sept. 2011 1064 - 1071