Efficient one-To-many broadcasting is an essential function in dense or large-scale wireless systems managed by a sink or gateway. This paper describes HASTE, a novel heuristic designed for broadcast tree production. Minimizing maximum hop count reduces worst case broadcast latency, while maximizing the number of leaf nodes reduces the number of transmitted messages. The algorithm is designed to be used with current wireless routing protocols that have the capability to push tree configurations into the network. We evaluated HASTE against an approximation algorithm and found that it consistently produces trees with lower latencies and fewer transmissions. HASTE was also evaluated using a packet simulator and a novel approach using Bloom filters was proposed to include tree configuration information in packets. The results show that the HASTE generated spanning tree can be efficiently pushed into the network achieving high packet delivery rates with minimal overhead in packet transmissions.
|Title of host publication||Proceedings of the 40th Annual IEEE Conference on Local Computer Networks, LCN 2015|
|Editors||Salil Kanhere, Jens Tolle, Soumaya Cherkaoui|
|Publisher||IEEE Computer Society|
|Number of pages||8|
|Publication status||Published - 24 Dec 2015|
|Event||2015 IEEE 40th Conference on Local Computer Networks, LCN 2015 - Clearwater Beach, United States|
Duration: 26 Oct 2015 → 29 Oct 2015
|Name||Proceedings - Conference on Local Computer Networks, LCN|
|Conference||2015 IEEE 40th Conference on Local Computer Networks, LCN 2015|
|Period||26/10/15 → 29/10/15|
Bibliographical noteFunding Information:
This work is supported by NSF under grants CNS-1116122 and CNS-1205453.
© 2015 IEEE.
Copyright 2016 Elsevier B.V., All rights reserved.