Paper Info
Title
An integer linear programming (ILP)-based optimization for finding the optimal independent sets in wireless ad hoc networks
Abstract
In wireless ad hoc networks, one of the most important issues impacting performance is wireless interference between adjacent nodes. Such interference problem has often been approached to find independent sets in a topological graph. In general, the topological graph have exponentially many independent sets and and thus it is very difficult to find the optimal independent sets for high performance. It is known that this problem belongs to the class of NP-hard problems. To deal with this problem, heuristic methods such as greedy algorithm, local search and genetic algorithm have been usually used. Such heuristics are useful to speed up the process of finding a satisfactory solution, however they do not guarantee the optimality of the solution found. In this paper, we develop a linearization technique to transform the nonlinear equations into linear ones. Then, we propose a novel integer linear programming (ILP)-based optimization design not only to properly find the optimal independent sets, but also to appropriately schedule wireless nodes for high performance. Based on the priority of the multiple objectives, our design is presented as a two-stage problem and optimizes the system sequentially. Numerical results demonstrate the effectiveness of the proposed optimization design.
Year
DOI
Venue
2013
10.1145/2448556.2448655
ICUIMC
Keywords
Field
DocType
topological graph,proposed optimization design,optimal independent set,integer linear programming,two-stage problem,interference problem,wireless interference,high performance,np-hard problem,independent set,optimization design,independent set problem,linear programming,scheduling,wireless ad hoc network
Mathematical optimization,Heuristic,Computer science,Greedy algorithm,Independent set,Integer programming,Linear programming,Wireless ad hoc network,Local search (optimization),Genetic algorithm
Conference
Citations 
PageRank 
References 
2
0.37
10
Authors
3
Name
Order
Citations
PageRank
Jinchul Choi1455.31
Hyunshik Seo220.37
Chaewoo Lee333127.28