Heuristic Algorithms for Combined Scheduling and Routing in Spatial TDMA Wireless Ad hoc Networks

• Multi-hop ad hoc wireless networking is a very attractive alternative for the communications in areas where there is a scarcity of telecommunications infrastructure. A major design issue in such networks is the formulation of the Medium Access Control (MAC) protocols. S-TDMA is a conflict-free MAC protocol thus enabling high spectral utilization, however scheduling is required. In link oriented S-TDMA the schedule specifies when particular radio links will be activated. In most wireless networks simultaneous links activation or "spatial reuse" is possible. An efficient schedule will take advantage of this reuse to ensure a high network throughput. Good scheduling is critical to network performance. Moreover, the "path finding" methods, i.e. the routing algorithm, are also critical in the design of multi-hop ad hoc wireless networks. This integrated or joint approach between routing and link scheduling is highly recommended in order to coordinates more efficiently the use of the communications resources in these networks. This paper investigates the performance gains with some heuristic algorithms for scheduling/routing in an S-TDMA ad hoc wireless networks, subject to given constraint regarding the peak transmission power ceiling per node. We introduce some routing/scheduling strategies, namely: MPRA (MinPowerpath Routing Algorithm), BMPRA (Balanced MPRA), COSRA (COmbined Scheduling & Routing Algorithm), and ARA-MHA (Advance Reuse Adaptive Minimum Hop Algorithm), and compare this strategies with MHA. The results show that when power control is used, ARA-MHA produces substantial improvement in throughput and packet delay.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Keyword

Information technology

Informationsteknik

SRA - ICT

SRA - Informations- och kommunikationsteknik

Publication and Content Type

ref (subject category)

kon (subject category)