Routing with uncertainty in the position of the destination

Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Anup Patnaik, Sunil Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in [1] that we propose has the best performance.

Original languageEnglish (US)
Title of host publicationIEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006
Pages9-16
Number of pages8
DOIs
StatePublished - Dec 1 2006
EventIEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006 - Montreal, QC, United States
Duration: Jun 19 2006Jun 21 2006

Publication series

NameIEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006

Other

OtherIEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006
CountryUnited States
CityMontreal, QC
Period6/19/066/21/06

Fingerprint

Routing algorithms
Mobile ad hoc networks
Ad hoc networks
Costs
Uncertainty

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Ad hoc networks
  • Face traversal
  • Flooding
  • Geocasting
  • Greedy routing
  • MANET
  • Routing
  • Wireless networks

Cite this

Kranakis, E., Krizanc, D., Narayanan, L., Patnaik, A., & Shende, S. (2006). Routing with uncertainty in the position of the destination. In IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006 (pp. 9-16). [1696352] (IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006). https://doi.org/10.1109/WIMOB.2006.1696352
Kranakis, Evangelos ; Krizanc, Danny ; Narayanan, Lata ; Patnaik, Anup ; Shende, Sunil. / Routing with uncertainty in the position of the destination. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006. 2006. pp. 9-16 (IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006).
@inproceedings{892befabc3f143c29c1222ebc30f39ed,
title = "Routing with uncertainty in the position of the destination",
abstract = "Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in [1] that we propose has the best performance.",
keywords = "Ad hoc networks, Face traversal, Flooding, Geocasting, Greedy routing, MANET, Routing, Wireless networks",
author = "Evangelos Kranakis and Danny Krizanc and Lata Narayanan and Anup Patnaik and Sunil Shende",
year = "2006",
month = "12",
day = "1",
doi = "https://doi.org/10.1109/WIMOB.2006.1696352",
language = "English (US)",
isbn = "1424404940",
series = "IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006",
pages = "9--16",
booktitle = "IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006",

}

Kranakis, E, Krizanc, D, Narayanan, L, Patnaik, A & Shende, S 2006, Routing with uncertainty in the position of the destination. in IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006., 1696352, IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006, pp. 9-16, IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006, Montreal, QC, United States, 6/19/06. https://doi.org/10.1109/WIMOB.2006.1696352

Routing with uncertainty in the position of the destination. / Kranakis, Evangelos; Krizanc, Danny; Narayanan, Lata; Patnaik, Anup; Shende, Sunil.

IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006. 2006. p. 9-16 1696352 (IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Routing with uncertainty in the position of the destination

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Narayanan, Lata

AU - Patnaik, Anup

AU - Shende, Sunil

PY - 2006/12/1

Y1 - 2006/12/1

N2 - Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in [1] that we propose has the best performance.

AB - Position-based routing algorithms for mobile ad hoc networks utilize the position or location of the destination node to inform routing decisions. We consider the problem of routing in an ad hoc network where the source node knows the approximate position of the destination node, but is uncertain about its exact current location. We investigate two approaches to this problem: one, based on a traversal of the faces of a planar sub-graph of the graph representing the network, and the second, based on flooding a limited area of the graph that represents the region the destination is likely to be found. We propose several variants of both approaches, and do extensive simulations to analyze the performance of the algorithms. Our results indicate that a simple modification of the basic flooding approach yields the best trade-off for optimizing delivery rate, stretch factor, as well as transmission cost. If however, delivery is required to be guaranteed, then a variant of the face tree approach in [1] that we propose has the best performance.

KW - Ad hoc networks

KW - Face traversal

KW - Flooding

KW - Geocasting

KW - Greedy routing

KW - MANET

KW - Routing

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=40949128728&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40949128728&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/WIMOB.2006.1696352

DO - https://doi.org/10.1109/WIMOB.2006.1696352

M3 - Conference contribution

SN - 1424404940

SN - 9781424404940

T3 - IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006

SP - 9

EP - 16

BT - IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006

ER -

Kranakis E, Krizanc D, Narayanan L, Patnaik A, Shende S. Routing with uncertainty in the position of the destination. In IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006. 2006. p. 9-16. 1696352. (IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006). https://doi.org/10.1109/WIMOB.2006.1696352