On graphs supporting greedy forwarding for directional wireless networks

Si, W; Scholz, B; Gudmundsson, J; Mao, G; Boreli, R; Zomaya, A

On graphs supporting greedy forwarding for directional wireless networks

Si, W Scholz, B Gudmundsson, J Mao, G

Boreli, R Zomaya, A

Permalink

Publication Type:: Conference Proceeding
Citation:: IEEE International Conference on Communications, 2012, pp. 751 - 756
Issue Date:: 2012-12-01

Closed Access

	Filename	Description	Size
	2013001566OK.pdf		1.26 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Si, W	en_US
dc.contributor.author	Scholz, B	en_US
dc.contributor.author	Gudmundsson, J	en_US
dc.contributor.author	Mao, G https://orcid.org/0000-0002-3598-4949	en_US
dc.contributor.author	Boreli, R	en_US
dc.contributor.author	Zomaya, A	en_US
dc.date.issued	2012-12-01	en_US
dc.identifier.citation	IEEE International Conference on Communications, 2012, pp. 751 - 756	en_US
dc.identifier.isbn	9781457720529	en_US
dc.identifier.issn	1550-3607	en_US
dc.identifier.uri	http://hdl.handle.net/10453/29999
dc.description.abstract	Greedy forwarding is an efficient and scalable geographic routing algorithm for wireless networks. To guarantee the success of greedy forwarding, many research efforts assign virtual coordinates to nodes to obtain a greedy embedding of the network. Different from these existing efforts, this paper presents an approach that enables greedy forwarding to succeed in directional wireless networks by selecting links in the network instead of assigning virtual coordinates to the nodes. Specifically, this paper studies the following problem: given a set of nodes on the Euclidean plane, how can we add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network. The motivation for studying this problem is that each point-to-point link in directional wireless networks is realized by a pair of directional antennas, so minimizing the number of links will reduce the network installation cost. This paper first presents the properties of the graphs supporting greedy forwarding, and then solves the above problem optimally by Integer Linear Programming and also sub-optimally by a polynomial-time 3-approximation algorithm. Finally, this paper compares the polynomial-time algorithm with the optimal solution, showing that the polynomial-time algorithm can actually generate within 1.1 times the number of links found by the optimal solution in most cases. © 2012 IEEE.	en_US
dc.relation.ispartof	IEEE International Conference on Communications	en_US
dc.relation.isbasedon	10.1109/ICC.2012.6363880	en_US
dc.title	On graphs supporting greedy forwarding for directional wireless networks	en_US
dc.type	Conference Proceeding
utslib.for	0906 Electrical and Electronic Engineering	en_US
dc.location.activity	Ottawa, ON	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Electrical and Data Engineering
pubs.organisational-group	/University of Technology Sydney/Strength - CRIN - Realtime Information Networks
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

Greedy forwarding is an efficient and scalable geographic routing algorithm for wireless networks. To guarantee the success of greedy forwarding, many research efforts assign virtual coordinates to nodes to obtain a greedy embedding of the network. Different from these existing efforts, this paper presents an approach that enables greedy forwarding to succeed in directional wireless networks by selecting links in the network instead of assigning virtual coordinates to the nodes. Specifically, this paper studies the following problem: given a set of nodes on the Euclidean plane, how can we add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network. The motivation for studying this problem is that each point-to-point link in directional wireless networks is realized by a pair of directional antennas, so minimizing the number of links will reduce the network installation cost. This paper first presents the properties of the graphs supporting greedy forwarding, and then solves the above problem optimally by Integer Linear Programming and also sub-optimally by a polynomial-time 3-approximation algorithm. Finally, this paper compares the polynomial-time algorithm with the optimal solution, showing that the polynomial-time algorithm can actually generate within 1.1 times the number of links found by the optimal solution in most cases. © 2012 IEEE.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/29999