**Routing Overhead in Variable Topology Networks**

**PI: A. Abouzeid**

**Funding: NSF**

*Synopsis of the Project:*

This project
is developing mathematical analysis leading to fundamental understanding of the
performance limits and design principles of routing protocols in variable
topology networks, in particular related to the routing overhead as a key
parameter of interest.

We have
developed mathematical models of proactive routing protocols in mobile ad-hoc
networks. Treating the topology as a physical system exhibiting random
(topology) changes induced by the underlying mobility model, we relate the
routing overhead to the entropy rate of the system. The results thus far apply
to the class of proactive routing protocols. Results for other classes of
protocols are being developed, by differentiating between the subset of changes
that are relevant to each.

We have
also derived a scalability result for reactive routing protocols overhead in
unreliable networks, by first quantifying the relation between the routing
overhead and the route-request/reply patterns, and hence finding the conditions
for infinite scalability (i.e. overhead grows as O(1) with the size of the
network).

*Students:*

- Nianjun Zhou
- Huaming Wu
- Nabhendra Bisnik

*Publications:*

- N. Bisnik, A.A. Abouzeid, “Capacity
Deficit in Mobile Ad Hoc Networks Due to Geographic Routing Overheads,”
to appear,
*Proceedings of 26th Annual IEEE Conference on Computer Communications (***INFOCOM 2007***)*, Anchorage, Alaska, USA, May 6-12, 2007.

·
N. Zhou and A.
Abouzeid, “Routing in Ad-Hoc Networks: A Theoretical
Framework with Practical Implications,” Proceedings
of 24th IEEE International Conference on Computer Communications (**Infocom2005**),

·
N. Zhou, H. Wu
and A. Abouzeid, “The Impact of Traffic Patterns on the Overhead of Reactive
Routing Protocols,”** IEEE Journal on
Selected Areas in Communications**, Special Issue on Wireless Ad Hoc
Networks, January 2005.

·
N. Zhou, H. Wu
and A. Abouzeid, “Reactive
Routing Overhead in Networks with Unreliable Nodes,” Proceedings of Ninth
Annual International Conference on **MobiCom’03**),

·
N. Zhou and A.
Abouzeid, “Information-Theoretic
Lower Bounds on the Routing Overhead in Mobile Ad-hoc Networks,”
Proceedings of IEEE International Symposium on Information Theory (**ISIT03**), Yokohama, Japan, June 2003.

·
N. Zhou and A.
Abouzeid, “Information-Theoretic Bounds for Mobile Ad-hoc Networks Routing
Protocols,” Proceedings of International Conference on Networks (**ICOIN03**), Jeju Island, Korea, February
2003. (Selected as One of the Best Papers in ICOIN2003).

·
Huaming Wu and Alhussein Abouzeid, "Cluster-based
Routing Overhead in Networks with Unreliable Nodes", To appear in
Proceedings of IEEE Wireless Communications and Networking Conference (**WCNC 200**4),
Atlanta, Georgia, USA, 2004.