Towards the fast and robust optimal design of wireless body area networks

被引:54
作者
D'Andreagiovanni, Fabio [1 ,2 ,3 ,4 ]
Nardin, Antonella [5 ]
机构
[1] ZIB, Dept Math Optimizat, D-14195 Berlin, Germany
[2] Tech Univ Berlin, DFG Res Ctr MATHEON, D-10623 Berlin, Germany
[3] Einstein Ctr Math Berlin ECMath, D-10623 Berlin, Germany
[4] Consiglio Nazl Ric IASI CNR, Inst Syst Anal & Comp Sci, I-00185 Rome, Italy
[5] Univ Rome Tre, I-00154 Rome, Italy
关键词
Body area networks; Wireless sensor networks; Integer linear programming; Robust optimization; Traffic uncertainty; Metaheuristics; OPTIMIZATION; COLONY;
D O I
10.1016/j.asoc.2015.04.037
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:971 / 982
页数:12
相关论文
共 34 条
[1]  
Ahuja R., 1993, NETWORK FLOWS THEORY
[2]   A survey of very large-scale neighborhood search techniques [J].
Ahuja, RK ;
Ergun, Ö ;
Orlin, JB ;
Punnen, AP .
DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :75-102
[3]   Min-max and min-max regret versions of combinatorial optimization problems: A survey [J].
Aissi, Hassene ;
Bazgan, Cristina ;
Vanderpooten, Daniel .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 197 (02) :427-438
[4]  
[Anonymous], 2001, WIRELESS COMMUNICATI
[5]  
[Anonymous], 2009, 2009 IEEE INT S WORL
[6]   Offering Strategy Via Robust Optimization [J].
Baringo, Luis ;
Conejo, Antonio J. .
IEEE TRANSACTIONS ON POWER SYSTEMS, 2011, 26 (03) :1418-1425
[7]   Network Planning under Demand Uncertainty with Robust Optimization [J].
Bauschert, Thomas ;
Buesing, Christina ;
D'Andreagiovanni, Fabio ;
Koster, Arie M. C. A. ;
Kutschka, Manuel ;
Steglich, Uwe .
IEEE COMMUNICATIONS MAGAZINE, 2014, 52 (02) :178-185
[8]  
BenTal A, 2009, PRINC SER APPL MATH, P1
[9]   The price of robustness [J].
Bertsimas, D ;
Sim, M .
OPERATIONS RESEARCH, 2004, 52 (01) :35-53
[10]   Theory and Applications of Robust Optimization [J].
Bertsimas, Dimitris ;
Brown, David B. ;
Caramanis, Constantine .
SIAM REVIEW, 2011, 53 (03) :464-501