TY - GEN
T1 - On scheduling and real-time capacity of hexagonal wireless sensor networks
AU - Prabh, K. Shashi
AU - Abdelzaher, Tarek
PY - 2007/10/23
Y1 - 2007/10/23
N2 - Since wireless ad-hoc networks use shared communication medium, accesses to the medium must be coordinated to avoid packet collisions. Transmission scheduling algorithms allocate time slots to the nodes of a network such that if the nodes transmit only during the allocated time slots, no collision occurs. For real-time applications, by ensuring deterministic channel access, transmission scheduling algorithms have the added significance of making guarantees on transmission latency possible. In this paper we present a distributed transmission scheduling algorithm for hexagonalwireless ad-hoc networks with a particular focus on Wireless Sensor Networks. Afforded by the techniques of ad-hoc networks topology control, hexagonal meshes enable trivial addressing and routing protocols. Our transmission scheduling algorithm constructs network-wide conflict-free packet transmission schedule for hexagonal networks, where the overhead of schedule construction in terms of message exchanges is zero above and beyond that for topology control and other network control related functions. Furthermore, the schedule is optimal in the sense that the bottleneck node does not idle. We also present an implicit clock synchronization algorithm to facilitate scheduling. We derive the real time capacity of our scheduling algorithm. We present evaluations of our scheduling algorithm in the presence of topological irregularities using simulation.
AB - Since wireless ad-hoc networks use shared communication medium, accesses to the medium must be coordinated to avoid packet collisions. Transmission scheduling algorithms allocate time slots to the nodes of a network such that if the nodes transmit only during the allocated time slots, no collision occurs. For real-time applications, by ensuring deterministic channel access, transmission scheduling algorithms have the added significance of making guarantees on transmission latency possible. In this paper we present a distributed transmission scheduling algorithm for hexagonalwireless ad-hoc networks with a particular focus on Wireless Sensor Networks. Afforded by the techniques of ad-hoc networks topology control, hexagonal meshes enable trivial addressing and routing protocols. Our transmission scheduling algorithm constructs network-wide conflict-free packet transmission schedule for hexagonal networks, where the overhead of schedule construction in terms of message exchanges is zero above and beyond that for topology control and other network control related functions. Furthermore, the schedule is optimal in the sense that the bottleneck node does not idle. We also present an implicit clock synchronization algorithm to facilitate scheduling. We derive the real time capacity of our scheduling algorithm. We present evaluations of our scheduling algorithm in the presence of topological irregularities using simulation.
UR - http://www.scopus.com/inward/record.url?scp=35348908542&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35348908542&partnerID=8YFLogxK
U2 - 10.1109/ECRTS.2007.23
DO - 10.1109/ECRTS.2007.23
M3 - Conference contribution
AN - SCOPUS:35348908542
SN - 0769529143
SN - 9780769529141
T3 - Proceedings - Euromicro Conference on Real-Time Systems
SP - 136
EP - 145
BT - Proceedings - 19th Euromicro Conference on Real-Time Systems, ECRTS 2007
T2 - 19th Euromicro Conference on Real-Time Systems, ECRTS 2007
Y2 - 4 July 2007 through 6 July 2007
ER -