This article is part of the series Quality of Service in Mobile Ad Hoc Networks.

Open Access Research Article

QoS Topology Control for Nonhomogenous Ad Hoc Wireless Networks

Deying Li1*, Xiaohua Jia2 and Hongwei Du2

Author Affiliations

1 School of Information, Renmin University of China, Beijing 100872, China

2 Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2006, 2006:082417 doi:10.1155/WCN/2006/82417


The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2006/1/082417


Received:27 July 2005
Revisions received:24 November 2005
Accepted:22 December 2005
Published:6 March 2006

© 2006 Li et al.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

This paper discusses the energy-efficient QoS topology control problem for nonhomogenous ad hoc wireless networks. Given a set of nodes with different energy and bandwidth capacities in a plane, and given the end-to-end traffic demands and delay bounds between node-pairs, the problem is to find a network topology that can meet the QoS requirements and the maximum energy utilization of nodes is minimized. Achieving this objective is vital to the increase of network lifetime. We consider two cases of the problem: (1) the traffic demands are not splittable, and (2) the traffic demands are splittable. For the former case, the problem is formulated as an integer linear programming problem. For the latter case, the problem is formulated as a mixed integer programming problem, and an optimal algorithm has been proposed to solve the problem.

References

  1. S Chen, K Nahrstedt, Distributed quality-of-service routing in ad hoc networks. IEEE Journal on Selected Areas in Communications 17(8), 1488–1505 (1999). Publisher Full Text OpenURL

  2. CR Lin, Admission control in time-slotted multihop mobile networks. IEEE Journal on Selected Areas in Communications 19(10), 1974–1983 (2001). Publisher Full Text OpenURL

  3. C Lin, JS Liu, QoS routing in ad hoc wireless networks. IEEE Journal on Selected Areas in Communications 17(8), 1426–1438 (1999). Publisher Full Text OpenURL

  4. C Zhu, MS Corson, QoS routing for mobile ad hoc networks. Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03), June 2002, New York, NY, USA 2, 958–967

  5. T Hou, VOK Li, Transmission range control in multihop packet radio networks. IEEE Transactions on Communications 34(1), 38–44 (1986)

  6. L Hu, Topology control for multihop packet radio networks. IEEE Transactions on Communications 41(10), 1474–1481 (1993). Publisher Full Text OpenURL

  7. EL Lloyd, R Liu, MV Marathe, R Ramanathan, SS Ravi, Algorithmic aspects of topology control problems for ad hoc networks. Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '02), June 2002, Lausanne, Switzerland, 123–134

  8. R Ramanathan, R Rosales-Hain, Topology control of multihop wireless networks using transmit power adjustment. Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '00), March 2000, Tel Aviv, Israel 2, 404–413

  9. N Li, JC Hou, L Sha, Design and analysis of an MST-based topology control algorithm. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03), March-April 2003, San Francisco, Calif, USA 3, 1702–1712

  10. R Wattenhofer, L Li, P Bahl, Y-M Wang, Distributed topology control for power efficient operation in multihop wireless ad hoc networks. Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01), April 2001, Anchorage, Alaska, USA 3, 1388–1397

  11. Z Huang, CC Shen, C Srisathapornphat, C Jaikaeo, Topology control for ad hoc networks with directional antennas. Proceedings of the 11th International Conference on Computer Communications and Networks (ICCCN '02), October 2002, Miami, Fla, USA, 16–21

  12. MA Marsan, CF Chiasserini, A Nucci, G Carello, L De Giovanni, Optimizing the topology of Bluetooth wireless personal area networks. Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '02), June 2002, New York, NY, USA 2, 572–579

  13. X Cheng, B Narahari, R Simha, MX Cheng, D Liu, Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics. IEEE Transactions on Mobile Computing 2(3), 248–256 (2003). Publisher Full Text OpenURL

  14. X Jia, D Li, D Du, QoS topology control in ad hoc wireless networks. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04), March 2004, Hong Kong 2, 1264–1272

  15. V Rodoplu, TH Meng, Position based CDMA with multiuser detection (P-CDMA/MUD) for wireless ad hoc networks. Proceedings of 6th IEEE International Symposium on Spread Spectrum Techniques and Applications (ISSSTA '00), September 2000, Parsippany, NJ, USA 1, 336–340

  16. S Sing, M Woo, C Raghavendra, Power-aware routing in mobile ad hoc networks. Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '98), October 1998, Dallas, Tex, USA, 181–190

  17. V Kawadia, PR Kumar, Power control and clustering in ad hoc networks. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03), March-April 2003, San Francisco, Calif, USA 1, 459–469

  18. JE Wieselthier, GD Nguyen, A Ephremides, On the construction of energy-efficient broadcast and multicast trees in wireless networks. Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '00), March 2000, Tel Aviv, Israel 2, 585–594

  19. P-J Wan, G Calinescu, X-Y Li, O Frieder, Minimum-energy broadcast routing in static ad hoc wireless networks. Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01), April 2001, Anchorage, Alaska, USA 2, 1162–1171

  20. A Muqattash, M Krunz, CDMA-based MAC protocol for wireless ad hoc networks. Proceedings of the 4th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '03), June 2003, Annapolis, Md, USA, 153–164

  21. L Hu, Distributed code assignments for CDMA packet radio networks. IEEE/ACM Transactions on Networking 1(6), 668–677 (1993). Publisher Full Text OpenURL

  22. A Schrijver, Theory of Linear and Integer Programming (John Wiley & Sons, Chichester, UK, 1986)