TY - GEN
T1 - Routing via single-source and multiple-source queries in static sensor networks
AU - Ga̧sieniec, Leszek
AU - Su, Chang
AU - Wong, Prudence W.H.
AU - Xin, Qin
PY - 2005
Y1 - 2005
N2 - In this paper, we introduce new geometric ad-hoc routing algorithms to route queries in static sensor networks. For single-source-queries routing, we utilise centralised mechanism to accomplish a query using an optimal number of transmissions O(c), where c is the length of the shortest path between the source and the destination. For multiple-source-queries routing, the number of transmissions for each query is bounded by O(c log n), where n is the number of nodes in the network. For both single-source and multiple-source queries, the routing stage is preceded by preprocessing stages requiring O(nD) and O(n 2D) transmissions, respectively, where D is the diameter of the network. Our algorithm improves the complexity of the currently best known algorithms in terms of the number of transmissions for each query. The preprocessing is worthwhile if it is followed by frequent queries. We could also imagine that there is an extra initial power (say, batteries) available during the preprocessing stage or alternatively the position of the sensors are known in advance and the preprocessing can be done before the sensors are deployed in the field. It also worths mentioning that a lower bound Ω(c 2) transmissions has been proved if preprocessing is not allowed [17].
AB - In this paper, we introduce new geometric ad-hoc routing algorithms to route queries in static sensor networks. For single-source-queries routing, we utilise centralised mechanism to accomplish a query using an optimal number of transmissions O(c), where c is the length of the shortest path between the source and the destination. For multiple-source-queries routing, the number of transmissions for each query is bounded by O(c log n), where n is the number of nodes in the network. For both single-source and multiple-source queries, the routing stage is preceded by preprocessing stages requiring O(nD) and O(n 2D) transmissions, respectively, where D is the diameter of the network. Our algorithm improves the complexity of the currently best known algorithms in terms of the number of transmissions for each query. The preprocessing is worthwhile if it is followed by frequent queries. We could also imagine that there is an extra initial power (say, batteries) available during the preprocessing stage or alternatively the position of the sensors are known in advance and the preprocessing can be done before the sensors are deployed in the field. It also worths mentioning that a lower bound Ω(c 2) transmissions has been proved if preprocessing is not allowed [17].
UR - http://www.scopus.com/inward/record.url?scp=33746313656&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746313656&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2005.384
DO - 10.1109/IPDPS.2005.384
M3 - Conference contribution
AN - SCOPUS:33746313656
SN - 0769523129
SN - 0769523129
SN - 9780769523125
T3 - Proceedings - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005
BT - Proceedings - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005
T2 - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005
Y2 - 4 April 2005 through 8 April 2005
ER -