Successive interference cancellation (SIC) is an effective means of multipacket reception to combat interference at the physical layer. We investigate the joint optimization issue of channel access and power control for capacity maximization in SICenabled 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 polynomialtimehard 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.
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 signalprocessing 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 signaltointerferenceplusnoise 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 SICenabled receiver repeats these two steps until the desired signals are all successfully decoded or the decoding process is interrupted.
Compared with other multipacket reception (MPR) techniques, the SICenabled 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 SICPHY 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 SICenhanced decoding process. Third, considering that the joint link scheduling and power control issue is proven to be a nondeterministic polynomialtime (NP)hard problem, a novel GAbased 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 GAbased approach. Section 5 provides the simulation and numerical results, and Section 6 presents the conclusions.
2. Related Work
SIC has been implemented in the softwaredefined radio platform and nearly achieved the Shannon capacity of multiuser 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 topologycontrol framework that greedily forms and activates subtopologies in a manner that exploits successful SIC decoding. In
[6]
, Lv et al. studied the linkscheduling problem for SICenabled wireless networks, and an independent setbased 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 multihop SICenabled 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 SICenabled networks, the corresponding complexity remains an issue.
3. System Model and Problem Formulation
 3.1 SINRbased 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,
P_{i}
the transmission power of the
i
th link, and
S_{ij}
=
P_{i}
/(
ϑ
∙
d_{ij}

^{η}
) the received signal power of the
i
th link at the receiver side of the
j
th link, where
ϑ
is the pathloss constant,
η
is the pathloss exponent (2 ≤
η
≤ 6), and
d_{ij}
is the distance between the transmitter of the
i
th link and the receiver of the
j
th link. Signal
S_{ij}
is successful if the SINR is above a certain reception threshold
β
, that is,
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:
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 SICenabled Interference Model (SICPHY)
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
SINRdecoding constraint of the
j
th link cannot be satisfied, that is,
Meanwhile, in SICenabled 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 thejth link, the receiver of thejth link can decode the signal of theith link, which is the strong interference of thejth link;

2) Decoding the desired signal: when the transmission of theith link is decoded, the corresponding interference can be removed from the original received signal, and the desired signal of thejth link may be successfully decoded from the remaining signal.
In each single iterative process of SICenabled decoding, the SINR constraint is still assumed to be satisfied, that is,
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:
where
is the link set denoting the corresponding signals decoded successfully and removed from the composite received signal before the decoding process of signal
S_{ij}
. The feasible data rate of the
j
th link in SICenabled networks can be extended to
 3.3 Achievable Transmission Capacity Calculation
Equations (2) and (5) show two issues related to improving network performance. These two are the linkscheduling 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
P_{i}
(
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
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
= {(
t_{i}
,
P_{i}
)
i
∈
L
, 1 ≤
t_{i}
≤
m
,
P_{i}
∈
P
}, which schedules the
i
th link in time slot
t_{i}
with transmission power
P_{i}
, by denoting the active link set in time slot
t_{i}
by
L_{a}
(
t_{i}
), we can calculate the achievable transmission capacity of the
i
th link in the solution
P
,
r_{i}
(
P
) as the following
Algorithm 1
:
The first part of
Algorithm 1
, lines 1 to 11 pseudocode, checks the halfduplex restriction of the concurrent link set
L_{a}
(
t_{i}
). 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:
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 NPhard.
Proof: The proof is that the special case of MCP with
γ
= 0,
m
= 2,
P_{i}
=
P
(
i
∈
L
) can be reduced from the partition problem, a wellknown NPcomplete 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 NPhard, the general case is NPhard as well. ■
4. GAbased Approach
 4.1 Design Challenges
As one of the most popular stochastic optimization algorithms and a powerful solution to NPhard 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 chromosomelike 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 chromosomelike individual consists ofNstrings {str i:(αi:Pi),i∈L}

(2) Each individual string is divided into two substrings,andand presents an instance of link scheduling and power control for a link.

(3) A link scheduling (or power control) substringconsists 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 substringequals 1, then the corresponding time slotj(or transmission power) is selected for theith link; otherwise, theith link is silent in time slotj(or transmission poweris not selected for theith link).

(5) The restriction, ∀i∈Lshould be satisfied to guarantee that each individual string coding is a feasible solution of the optimization problem.
Chromosomelike individual of MCP
As an example, we consider a wireless network that consists of 12 communication links. A chromosomelike individual then comprises 12 substrings, and the string
str
1 =
(00100;00010)
denotes that the first link is scheduled in time slot 3 with transmission power
 4.3 Fitness Function
The fitness value of a chromosomelike 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
where
X
is a chromosomelike individual and
P_{X}
is the corresponding scheduling solution.
 4.4 Genetic Operations
The initial individuals are randomly produced, and only the individual strings that satisfy the restriction
, ∀
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
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 chromosomelike individuals, the size of which is denoted by
S_{C}
, a part of individuals,
S_{P}
, 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
p_{c}
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
p_{m}
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.
Illustration of the crossover process
The condition
S_{C}
= (1 +
p_{c}
+
p_{m}
) ·
S_{P}
should be satisfied to guarantee the stability of the evolution process.
 4.5 GA Process
Given the algorithm designs presented in Subsections 4.2, 4.3, and 4.4, GASIC is proposed as follows:
5. Experimental Results
We evaluate the proposed GASIC 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 pointtopoint links are selected to be scheduled in 10 transmission time slots with five different transmit power levels. All transmissions are implement in a halfduplex model. The pathloss constant
ϑ
, pathloss exponent
η
, and reception threshold
β
are set to 2, 2, and 10, respectively.
We set generation threshold
Many numerical experiments are executed to investigate five performancerelated effect factors, namely, population size
S_{P}
, crossover probability
p_{c}
, mutation probability
p_{m}
, network size
N
, and network topology (rand or grid). The default parameters are set to
S_{P}
= 50,
p_{c}
= 0.5,
p_{c}
= 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 (
S_{P}
< 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.
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
S_{P}
= 50, crossover probability
p_{c}
= 0.5, and mutation probability
p_{m}
= 0.3.
Effect of crossover probability
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.
Effect of network size
Effect of network toplogy
6. Conclusions
We investigated the joint optimization issue of channel access and power control for capacity maximization in SICenabled 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 NPhard problem. Second, we introduced a GAbased approach. Finally, extensive simulations were performed to demonstrate that our GAbased 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 multipacket 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, highperformance computing, and wireless networking.
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 BackoftheEnvelope 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 MultipleAccess 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 multiuser 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 GameTheoretic 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.
“Gametheoretic Resource Allocation in Relayassisted 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 NPcompleteness.
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