| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Topology Control in Ad Hoc Wireless Networks Using Cooperative Communication
June 2006 (vol. 5 no. 6)
pp. 711-724
In this paper, we address the Topology control with Cooperative Communication (TCC) problem in ad hoc wireless networks. Cooperative communication is a novel model introduced recently that allows combining partial messages to decode a complete message. The objective of the TCC problem is to obtain a strongly-connected topology with minimum total energy consumption. We show that the TCC problem is NP-complete and design two distributed and localized algorithms to be used by the nodes to set up their communication ranges. Both algorithms can be applied on top of any symmetric, strongly-connected topology to reduce total power consumption. The first algorithm uses a distributed decision process at each node that makes use of only 2-hop neighborhood information. The second algorithm sets up the transmission ranges of nodes iteratively, over a maximum of six steps, using only 1-hop neighborhood information. We analyze the performance of our approaches through extensive simulation.
[1] M. Agarwal, J.H. Cho, L. Gao, and J. Wu, “Energy Efficient Broadcast in Wireless Ad Hoc Networks with Hitch-Hiking,” Proc. IEEE INFOCOM, 2004.
[2] M. Cardei, J. Wu, and S. Yang, “Topology Control in Ad Hoc Wireless Networks with Hitch-Hhiking,” Proc. First IEEE Int'l Conf. Sensor and Ad Hoc Comm. and Networks (SECON '04), Oct. 2004.
[3] W.-T. Chen and N.-F. Huang, “The Strongly Connecting Problem on Multihop Packet Radio Networks,” IEEE Trans. Comm., vol. 37, no. 3, pp. 293-295, Mar. 1989.
[4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, second ed. McGraw-Hill, 2002.
[5] R. Gallager, P. Humblet, and P. Spira, “A Distributed Algorithm for Minimum-Weight Spanning Tree,” ACM Trans. Programming Languages and Systems, 1983.
[6] T.-C. Hou and V.O.K. Li, “Transmission Range Control in Multihop Packet Radio Networks,” IEEE Trans. Comm., vol. 34, no. 1, pp. 38-44, Jan. 1986.
[7] L. Hu, “Topology Control for Multihop Packet Radio Networks,” IEEE Trans. Comm., vol. 41, no. 10, pp. 1474-1481, 1993.
[8] X. Jia, D. Li, and D.-Z. Du, “QoS Topology Control in Ad Hoc Wireless Networks,” Proc. IEEE INFOCOM, 2004.
[9] C.E. Jones, K.M. Sivalingam, P. Agrawal, and J.C. Chen, “A Survey of Energy Efficient Network Protocols for Wireless Networks,” Wireless Networks, vol. 7, no. 4, pp. 343-358, Aug. 2001.
[10] L.M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, “Power Consumption in Packet Radio Networks,” Proc. 14th Ann. Symp. Theoretical Aspects of Computer Science (STACS '97), pp. 363-374, 1997.
[11] N. Laneman, D. Tse, and G. Wornell, “Cooperative Diversity in Wireless Networks: Efficient Protocols and Outage Behavior,” IEEE Trans. Information Theory, 2003.
[12] L. Li, J.Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer, “Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-Hop Networks,” Proc. ACM Symp. Principles of Distributed Computing, pp. 264-273, Aug. 2001.
[13] N. Li, J. Hou, and L. Sha, “Design and Analysis of an MST-Based Topology Control Algorithm,” Proc. IEEE Infocom, 2003.
[14] X.-Y. Li, Topology Control in Wireless Ad Hoc Networks, Ad Hoc Networking, S. Basagni, M. Conti, S. Giordano, and I. Stojmenovic, eds. IEEE Press, 2003.
[15] A. Nosratinia, T.E. Hunter, and A. Hedayat, “Cooperative Communication in Wireless Networks,” IEEE Comm. Magazine, vol. 42, no. 10, pp. 74-80, Oct. 2004.
[16] J.G. Proakis, Digital Communications, fourth ed. McGraw Hill, 2001.
[17] T.S. Rappaport, Wireless Communications, second ed. Prentice-Hall, 2002.
[18] R. Ramanathan and R. Rosales-Hain, “Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment,” Proc. IEEE INFOCOM, pp. 404-413, 2000.
[19] P. Santi, D.M. Blough, and F. Vainstein, “A Probabilistic Analysis for the Range Assignment Problem in Ad Hoc Networks,” Proc. ACM Mobihoc, pp. 212-220, Aug. 2000.
[20] C.-C. Shen and Z. Huang, Topology Control for Ad Hoc Networks: Present Solutions and Open Issues, Handbook of Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, J. Wu, ed. CRC Press, 2005.
[21] J. Wu, M. Cardei, F. Dai, and S. Yang, “Extended Dominating Set and Its Applications in Ad Hoc Networks Using Cooperative Communication,” IEEE Trans. Parallel and Distributed Systems, accepted for publication.
Index Terms:
Ad hoc wireless networks, cooperative communication, energy efficiency, topology control.
Citation:
Mihaela Cardei, Jie Wu, Shuhui Yang, "Topology Control in Ad Hoc Wireless Networks Using Cooperative Communication," IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 711-724, June 2006, doi:10.1109/TMC.2006.87
