GreenWave Routing Trees for Wireless Sensor Networks Fikret Sivrikaya Bülent Yener Contention-free MAC protocols have the desired energy-saving characteristics for wireless sensor networks by avoiding collisions and minimizing retransmissions in the wireless medium [2] [4] [24] [25] [26]. Most of the contention-free MAC protocols split the channel in the time domain, by assigning each node a time slot for use in transmission, which is unique in its neighborhood. In such protocols, the time-multiplexed communication introduces extra delay on the packets when relayed by intermediate nodes. In this paper, we consider the delay optimal routing problem on sensor networks with such MAC protocols. We propose algorithms which construct routing trees rooted at sink nodes to route data to and from sensor nodes. First, we consider routing with data fusion, and present our GreenWave routing idea.We show that our algorithm significantly reduces the end-to-end delay when compared to routing over the shortest-hop paths. We also present a comparison of GreenWave routing over a contention-free MAC protocol to the shortest-path routing over the IEEE 802.11 MAC protocol, accompanied by an end-to-end delay analysis of 802.11. As a side result, we show that there is roughly a two-fold decrease in 802.11 performance when hidden terminals are taken into account. Moreover, we observe that a contention-free MAC protocol may outperform 802.11 with the help of GreenWave routing. Second, we consider routing without data fusion, by taking into account the effect of congestion along the paths on the end-to-end delays. We provide a quadratic integer programming (QIP) formulation of the problem, and present a lower bound and a heuristic algorithm to bound the optimal solution. Numerical results show that the results obtained by the heuristic are close to the lower bounds. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-05-17
GreenWave Routing Trees for Wireless Sensor Networks
Fikret Sivrikaya
Bülent Yener
Contention-free MAC protocols have the desired energy-saving characteristics for wireless sensor networks by avoiding collisions and minimizing retransmissions in the wireless medium [2] [4] [24] [25] [26]. Most of the contention-free MAC protocols split the channel in the time domain, by assigning each node a time slot for use in transmission, which is unique in its neighborhood. In such protocols, the time-multiplexed communication introduces extra delay on the packets when relayed by intermediate nodes. In this paper, we consider the delay optimal routing problem on sensor networks with such MAC protocols. We propose algorithms which construct routing trees rooted at sink nodes to route data to and from sensor nodes. First, we consider routing with data fusion, and present our GreenWave routing idea.We show that our algorithm significantly reduces the end-to-end delay when compared to routing over the shortest-hop paths. We also present a comparison of GreenWave routing over a contention-free MAC protocol to the shortest-path routing over the IEEE 802.11 MAC protocol, accompanied by an end-to-end delay analysis of 802.11. As a side result, we show that there is roughly a two-fold decrease in 802.11 performance when hidden terminals are taken into account. Moreover, we observe that a contention-free MAC protocol may outperform 802.11 with the help of GreenWave routing. Second, we consider routing without data fusion, by taking into account the effect of congestion along the paths on the end-to-end delays. We provide a quadratic integer programming (QIP) formulation of the problem, and present a lower bound and a heuristic algorithm to bound the optimal solution. Numerical results show that the results obtained by the heuristic are close to the lower bounds.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-05-17