TY - JOUR
T1 - Bypassing holes in sensor networks
T2 - Load-balance vs. latency
AU - Zhou, Fan
AU - Trajcevski, Goce
AU - Tamassia, Roberto
AU - Avci, Besim
AU - Khokhar, Ashfaq
AU - Scheuermann, Peter
N1 - Funding Information:
This work was supported by the U.S. National Science Foundation (Grants CNS-0910952, CNS-1646107, CCF-0830149, IIS-1213038 and IIS-1212508), ONR grant N00014-14-10215, National Natural Science Foundation of China (Grant No. 61602097 and No. 61672135), Sichuan Science-Technology Support Plan Program (No.2016GZ0065), and the Fundamental Research Funds for the Central Universities (No.ZYGX2015J072).
PY - 2017/6/1
Y1 - 2017/6/1
N2 - This work addresses problems that arise when geographic routing is used in the presence of holes in wireless sensor networks. We postulate that relying on the existing algorithms for bypassing a coverage hole may cause more severe depletion of the energy reserves among the nodes at (or near) that hole's boundary. This, in turn, will render some of those nodes useless for any routing (and/or sensing) purposes, thereby effectively enlarging the size of existing hole and inducing longer communication delays for certain (source, sink) pairs. We propose heuristics that address these complementary problems: (1) relieving some of the routing-load for the nodes around the boundary of a given hole, for the purpose of extending their lifetime; and (2) reducing the latency of the packets-delivery by using routes that are within certain bounds from the route based on the shortest-path. Our approaches are based on the idea that some of the packets that would (otherwise) need to be routed along the boundary of a given hole, should instead start to deviate from their original path further away from that hole. To investigate the potential benefits, we introduce approximations of the hole's boundary with a rectangle, a circle and an ellipse, respectively. We derive the bounds on reducing the routing latency for these three approximations. Our experiments demonstrate that the proposed approaches not only increase the lifetime of the nodes along the boundary of a given hole and yield a more uniform depletion of the energy reserves in its vicinity, but also reduce the communication latency, compared to the traditional face routing.
AB - This work addresses problems that arise when geographic routing is used in the presence of holes in wireless sensor networks. We postulate that relying on the existing algorithms for bypassing a coverage hole may cause more severe depletion of the energy reserves among the nodes at (or near) that hole's boundary. This, in turn, will render some of those nodes useless for any routing (and/or sensing) purposes, thereby effectively enlarging the size of existing hole and inducing longer communication delays for certain (source, sink) pairs. We propose heuristics that address these complementary problems: (1) relieving some of the routing-load for the nodes around the boundary of a given hole, for the purpose of extending their lifetime; and (2) reducing the latency of the packets-delivery by using routes that are within certain bounds from the route based on the shortest-path. Our approaches are based on the idea that some of the packets that would (otherwise) need to be routed along the boundary of a given hole, should instead start to deviate from their original path further away from that hole. To investigate the potential benefits, we introduce approximations of the hole's boundary with a rectangle, a circle and an ellipse, respectively. We derive the bounds on reducing the routing latency for these three approximations. Our experiments demonstrate that the proposed approaches not only increase the lifetime of the nodes along the boundary of a given hole and yield a more uniform depletion of the energy reserves in its vicinity, but also reduce the communication latency, compared to the traditional face routing.
KW - Communication latency
KW - Geographical routing
KW - Load-balancing
UR - http://www.scopus.com/inward/record.url?scp=85017580168&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85017580168&partnerID=8YFLogxK
U2 - 10.1016/j.adhoc.2017.03.002
DO - 10.1016/j.adhoc.2017.03.002
M3 - Article
AN - SCOPUS:85017580168
VL - 61
SP - 16
EP - 32
JO - Ad Hoc Networks
JF - Ad Hoc Networks
SN - 1570-8705
ER -