Minimum Energy Cooperative Path Routing in All-Wireless Networks: NP-Completeness and Heuristic Algorithms

다국어 초록 (Multilingual Abstract)

We study the routing problem in all-wireless networks
based on cooperative transmissions. We model the minimumenergy
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.

참고문헌 (Reference)

1 R. Min, "Top five myths about the energy consumption of wireless communication" 2002

2 A. Catovic, "Reducing transmit power and extending network lifetime via user cooperation in the next generation wireless multihop networks" 4 (4): 2002

3 J. Wieselthier, "On the construction of energy-efficient broadcast and multicast trees in wireless networks" 585-594, 2000

4 M. Cagalj, "Minimum-energy broadcast in allwireless networks: NP-completeness and distribution issues" 2003

5 V. Rodoplu, "Minimum energy mobile wireless networks" 17 (17): 1333-1344, 1999

6 A. Srinivas, "Minimum energy disjoint path routing in wireless ad-hoc networks" 2003

7 F. Li, "Minimum energy cooperative path routing in wireless networks: An integer programming formulation" 1-6, 2006

8 L. Feeney, "Investigating the energy consumption of a wireless network interface in an ad hoc networking environment" 2001

9 H. Cormen, "Introduction to Algorithms. 2nd Ed" MIT Press 2001

10 F. Li, "Energy-efficient cooperative routing in multi-hop wireless ad hoc networks" 2006

11 R.Wattenhofer, "Distributed topology control for power efficient operation in multihop wireless ad-hoc networks" 2001

12 A. Khandani, "Cooperative routing in wireless networks" 2003

13 W. Liang, "Constructing minimum-energy broadcast trees in wireless ad hoc networks" 2002

14 M. Garey, "Computers and Intractability: A Guide to the Theory of NP-Completeness" W.H. Freeman and Company 1979

15 Y. Tu, "Coherent cooperative transmission from multiple adjacent antennas to a distant stationary antenna through AWGN channels" 130-134, 2002