Minimum energy cooperative path routing in all-wireless networks: NP-completeness and heuristic algorithms

被引：4

作者：

Li, Fulu ^{[1
]}

Wu, Kui ^{[2
]}

Lippman, Andrew ^{[1
]}

机构：

[1] MIT, Media Lab, Cambridge, MA 02139 USA

[2] Univ Victoria, Dept Comp Sci, Victoria, BC V8W 2Y2, Canada

来源：

JOURNAL OF COMMUNICATIONS AND NETWORKS | 2008年 / 10卷 / 02期

关键词：

cooperative transmissions; distributed algorithms; energy efficiency; wireless networks;

D O I：

10.1109/JCN.2008.6389840

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the routing problem in all-wireless networks based on cooperative transmissions. We model the minimum-energy cooperative path (MECP) problem and prove that this problem is NP-complete. We hence design an approximation algorithm called cooperative shortest path (CSP) algorithm that uses Dijkstra's algorithm as the basic building block and utilizes cooperative transmissions in the relaxation procedure. Compared with traditional non-cooperative shortest path algorithms, the CSP algorithm can achieve a higher energy saving and better balanced energy consumption among network nodes, especially when the network is in large scale. The nice features lead to a unique, scalable routing scheme that changes the high network density from the curse of congestion to the blessing of cooperative transmissions.

引用

页码：204 / 212

页数：9