TY - GEN
T1 - Improved algorithms for two energy-optimal routing problems in ad-hoc wireless networks
AU - Baugh, Samuel
AU - Calinescu, Gruia
AU - Rincon-Cruz, David
AU - Qiao, Kan
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/10/26
Y1 - 2016/10/26
N2 - We study two problems of assigning transmission power to the nodes of ad hoc wireless networks to minimize total power consumption while satisfying certain connectivity constraints. The first problem requires to establish k node-disjoint paths from a given source to a given destination. Our new algorithm works for the most general cost model, and returns an optimal solution in time O(n3) (where n is the number of nodes), improving the running time over the previously published algorithm by a factor of k. The second problem assumes that the power requirement between any two nodes is symmetric, and that there are exactly two possible power levels, one of which is negligible. A source is given and all the nodes in the network must be reachable from the source (unidirectional links allowed for broadcast). We obtain a (4 + ln n)-approximation algorithm, while the best published approximation ratio is 2 (1+ln(n-1)). It was also known that no approximation ratio better than O(ln n) is possible unless P = NP.
AB - We study two problems of assigning transmission power to the nodes of ad hoc wireless networks to minimize total power consumption while satisfying certain connectivity constraints. The first problem requires to establish k node-disjoint paths from a given source to a given destination. Our new algorithm works for the most general cost model, and returns an optimal solution in time O(n3) (where n is the number of nodes), improving the running time over the previously published algorithm by a factor of k. The second problem assumes that the power requirement between any two nodes is symmetric, and that there are exactly two possible power levels, one of which is negligible. A source is given and all the nodes in the network must be reachable from the source (unidirectional links allowed for broadcast). We obtain a (4 + ln n)-approximation algorithm, while the best published approximation ratio is 2 (1+ln(n-1)). It was also known that no approximation ratio better than O(ln n) is possible unless P = NP.
UR - http://www.scopus.com/inward/record.url?scp=85001124959&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85001124959&partnerID=8YFLogxK
U2 - 10.1109/BDCloud-SocialCom-SustainCom.2016.80
DO - 10.1109/BDCloud-SocialCom-SustainCom.2016.80
M3 - Conference contribution
AN - SCOPUS:85001124959
T3 - Proceedings - 2016 IEEE International Conferences on Big Data and Cloud Computing, BDCloud 2016, Social Computing and Networking, SocialCom 2016 and Sustainable Computing and Communications, SustainCom 2016
SP - 509
EP - 516
BT - Proceedings - 2016 IEEE International Conferences on Big Data and Cloud Computing, BDCloud 2016, Social Computing and Networking, SocialCom 2016 and Sustainable Computing and Communications, SustainCom 2016
A2 - Cai, Zhipeng
A2 - Luo, Guangchun
A2 - Cheng, Liang
A2 - Angryk, Rafal
A2 - Li, Yingshu
A2 - Bourgeois, Anu
A2 - Song, Wenzhan
A2 - Cao, Xiaojun
A2 - Krishnamachari, Bhaskar
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 6th IEEE International Conference on Big Data and Cloud Computing, BDCloud 2016, 9th IEEE International Conference on Social Computing and Networking, SocialCom 2016 and 2016 IEEE International Conference on Sustainable Computing and Communications, SustainCom 2016
Y2 - 8 October 2016 through 10 October 2016
ER -