Analysis and algorithms design for the partition of large-scale adaptive mobile wireless networks

Bin Xiao, Jiannong Cao, Zili Shao, Qingfeng Zhuge, Edwin H M Sha

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

In a large-scale adaptive mobile wireless network, mobile units can communicate via either ad hoc or server-based communications. Ad hoc communication allows mobile units in close proximity to exchange messages directly. Server-based communication allows long distance contact between mobile units but must be supported by mobile servers. This paper investigates the partitioning problem as it applies to the assignment of mobile nodes, which contain mobile units in close proximity, to mobile servers under constraints of wireless transmission range and available bandwidth. This problem is even more difficult when the topologies of the mobile node connection graph and the mobile server network graph are dynamically changing. Given appropriate definitions for valid partitions in our framework, this paper shows the associated decision-based partition problems are NP-complete. In this paper, we propose assigning mobile nodes to mobile servers using efficient heuristic algorithms such that communication requirements among mobile nodes are successfully met by mobile servers. The simulation environment simulates a dynamically modified network topology of a wireless network consisting of roaming mobile nodes. The results show that proposed heuristic algorithms can yield effective assignments with a performance similar to that produced by exhaustive approaches.
Original languageEnglish
Pages (from-to)1899-1912
Number of pages14
JournalComputer Communications
Volume30
Issue number8
DOIs
Publication statusPublished - 8 Jun 2007

Keywords

  • Adaptive mobile networks
  • NP-complete
  • Partition

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this