TY - JOUR
T1 - A low-latency and energy-efficient neighbor discovery algorithm for wireless sensor networks
AU - Gu, Zhaoquan
AU - Cao, Zhen
AU - Tian, Zhihong
AU - Wang, Yuexuan
AU - Du, Xiaojiang
AU - Mohsen, Guizani
N1 - Publisher Copyright:
© 2020 by the authors. Licensee MDPI, Basel, Switzerland.
PY - 2020/2/1
Y1 - 2020/2/1
N2 - Wireless sensor networks have been widely adopted, and neighbor discovery is an essential step to construct the networks. Most existing studies on neighbor discovery are designed on the assumption that either all nodes are fully connected or only two nodes compose the network. However, networks are partially connected in reality: some nodes are within radio range of each other, while others are not. Low latency and energy efficiency are two common goals, which become even more challenging to achieve at the same time in partially connected networks. We find that the collision caused by simultaneous transmissions is the main obstruction of achieving the two goals. In this paper, we present an efficient algorithm called Panacea to address these challenges by alleviating collisions. To begin with, we design Panacea-NCD (Panacea no collision detection) for nodes that do not have a collision detection mechanism. When n is large, we show the discovery latency is bounded by O(n · ln n) for any duty cycle (the percentage time to turn on the radio), where each node has n neighbors on average. For nodes that can detect collisions, we then present Panacea-WCD which also bounds the latency within O(n · ln n) slots. Finally, we conduct extensive evaluations and the results also corroborate our analyses.
AB - Wireless sensor networks have been widely adopted, and neighbor discovery is an essential step to construct the networks. Most existing studies on neighbor discovery are designed on the assumption that either all nodes are fully connected or only two nodes compose the network. However, networks are partially connected in reality: some nodes are within radio range of each other, while others are not. Low latency and energy efficiency are two common goals, which become even more challenging to achieve at the same time in partially connected networks. We find that the collision caused by simultaneous transmissions is the main obstruction of achieving the two goals. In this paper, we present an efficient algorithm called Panacea to address these challenges by alleviating collisions. To begin with, we design Panacea-NCD (Panacea no collision detection) for nodes that do not have a collision detection mechanism. When n is large, we show the discovery latency is bounded by O(n · ln n) for any duty cycle (the percentage time to turn on the radio), where each node has n neighbors on average. For nodes that can detect collisions, we then present Panacea-WCD which also bounds the latency within O(n · ln n) slots. Finally, we conduct extensive evaluations and the results also corroborate our analyses.
KW - Communication collision
KW - Discovery latency
KW - Duty cycle
KW - Neighbor discovery
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=85078688489&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078688489&partnerID=8YFLogxK
U2 - 10.3390/s20030657
DO - 10.3390/s20030657
M3 - Article
C2 - 31991639
AN - SCOPUS:85078688489
SN - 1424-8220
VL - 20
JO - Sensors (Switzerland)
JF - Sensors (Switzerland)
IS - 3
M1 - 657
ER -