Electrical, Computer and Systems Engineering Dept.
Rensselaer Polytechnic Institute
Office: Room 6038,
Tel: (518) 276-6534 Fax: (518) 276-4403
E - Mail: abouzeid/@/ecse.rpi.edu
Following is a list of recent
research directions and sample of related publications. Also I have recently (9/06)
prepared a set of slides clustering some of the most recent research results.
Information Theory and Routing
Protocols
Motivation: The significance of characterizing the overhead is
that routing overhead may dominate network traffic. Since routing protocols
need to adjust to topology changes, a routing overhead is incurred, represented
by the exchange of routing messages. For networks with frequent change, such
overhead may become a significant limit on the scalability and effective
capacity. The results below apply to link-state routing and geographic
routing protocols. A manuscript for reactive protocols has been submitted for
review.
Approach: The
key idea behind this work is that we propose to treat a variable topology
network as a physical system that exhibits random (topology) changes. The
minimum routing overhead is related to the minimum amount of information needed
to identify the current state of the system (i.e. the current network topology).
The various topology changes are derived from the probability distribution
describing the individual node mobility. Thus the routing overhead can be
related to the entropy rate of the system. Further, we differentiate between
different types of routing protocols based on the subset of changes that are
relevant to the specific class of protocols under study. For example, proactive
protocols keep track of any change in the system (i.e. network), while reactive
protocols keep track of a subset of the system changes (those changes that
affect nodes/links actively participating in routing packets).
Links: Presentation to DARPA ITMANET workshop; Project web page.
·
N. Zhou and A.A. Abouzeid, “Routing in Ad
Hoc Networks: A Theoretical Framework with Practical Implications,”
IEEE Transactions on Information Theory, submitted April 2004, revised August
2006.
·
N. Bisnik and A.A. Abouzeid, “Capacity
Deficit in Mobile Ad Hoc Networks Due to Geographic Protocols Overhead,”
IEEE Transactions on Information Theory, submitted September 2006.
·
N. Zhou and A. Abouzeid, “Routing in Ad
Hoc Networks: A Theoretical Framework with Practical Implications,”
in Proceedings of 24th IEEE Conference on Computer Communications (INFOCOM’2005),
·
N. Bisnik, A. A. Abouzeid, “Rate-Distortion Bounds on
Location-Based Routing Protocol Overheads in Mobile Ad Hoc Networks”
Proceedings of Forty Fourth Annual Allerton Conference on Communication,
Control, and Computing, Monticello, IL, Sept. 2006.
Infinitely Scalable Reactive
Routing Protocols in Unreliable Networks
This work develops a
mathematical and simulative framework for quantifying the overhead of reactive
routing protocols, such as dynamic source routing and ad hoc on-demand distance
vector, in wireless variable topology (ad hoc) networks. Two network models are
analyzed; a Manhattan grid model for the case of regular node placement, and a
Poisson model for the case of random node placement. We focus on situations
where the nodes are stationary but unreliable. One of the key insights that can
be drawn from the mathematical results of this paper is that it is possible to
design infinitely scalable reactive routing protocols for variable topology
networks by judicious engineering of the traffic patterns to satisfy certain
“statistical locality” discovered in this research.
Presentation at Princeton ISS seminar; Project web page.
·
N. Zhou, H. Wu and A. Abouzeid, “Reactive
Routing Overhead in Networks with Unreliable Nodes,” Proceedings of Ninth
Annual International Conference on
·
N. Zhou, H. Wu and A. A. Abouzeid, “The
Impact of Traffic Patterns on the Overhead of Reactive Routing Protocols,”
IEEE Journal on Selected Areas in Communications, Special Issue on
·
Huaming Wu and A. A. Abouzeid, "Analysis of A
Cluster-based Routing Protocol Overhead in An Unreliable Network", in
Proceedings of IEEE Wireless Communications and Networking Conference
(WCNC’04), Vol.4 pp.2557-62,
Queuing Networks Analysis of
Delay &Throughput of Random Access Ad Hoc and Mesh Networks
This work considers the
throughput vs. delay (including queuing) in random access multi-hop wireless
networks employing random access schemes, in addition to (for mesh networks)
controlled access schemes at the MAC layer, and multi-hop routing at the network
layer.
Wireless mesh networks
(WMNs) are emerging as a promising means of providing connectivity to
communities in both affluent and poor parts of the world. The presence of
backbone mesh routers and the use of multiple channels and interfaces allow mesh
networks to have better capacity than infrastructure-less multihop ad hoc
networks. In this work characterize the average delay and capacity in WMNs that
utilize random medium access (MAC).We model residential area WMNs as open G/G/1
queuing networks. The analytical model takes into account the density of the
mesh clients and mesh routers, the random packet arrival process, the degree of
locality of traffic and the collision avoidance mechanism of random access MAC.
We obtain closed form expressions for (a) end-to-end packet delay and (b)
maximum achievable per-node throughput. The analytical results describe how the
performance of WMNs scales with the number of mesh routers and clients. The
results obtained from simulations agree closely with the analytical results.
For the asymptotic case (as the network size grows indefinitely), we discuss
how the results obtained using the proposed queuing network framework compare
against previous well known results on asymptotic capacity of
infrastructure-less ad hoc networks.
·
N.
Bisnik and A.A. Abouzeid, “Queuing Network Models for
Delay Analysis of Multihop Wireless Ad Hoc Networks,” Proceedings of
International Symposium on Wireless Local and Personal Area Networks, International
Wireless Communications and Mobile Computing Conference (IWCMC 2006), July
2006, Vancouver, Canada.
·
N.
Bisnik and A.A. Abouzeid, “Queuing Delay and Achievable
Throughput in Random Access Wireless Ad Hoc Networks,” Proceedings
of The 2006 IEEE International Workshop on Wireless Ad-hoc and Sensor Networks
(IWWAN 2006), June 2006, New York, NY.
·
Random Walk in Ad Hoc Networks
Locating a resource or
service efficiently is one of the most important issues related to unstructured
decentralized peer-to-peer networks. The objective of a search mechanism is to
successfully locate resources while incurring low overhead and low delay. In
order to fulfill this objective, several random walk based search algorithms
have been proposed for resource discovery in decentralized peer-to-peer
networks. However, no analytical model has been proposed to quantify the effect
of parameters of random walk, such as the number and time to live (TTL) of
random walkers, on the performance of search algorithms. In this work we
develop a mathematical model for random walk search in a peer-to-peer network.
Using the model we derive analytical expressions for the performance metrics,
such as delay, overhead and success rate, of the search in terms of the
popularity of the resource being searched for and the parameters of random
walk. We propose an algorithm that uses the analytical expressions in order to
adaptively set the parameters of random walk so that it maintains a certain minimum
level of performance. The algorithm is referred to as Equation Based Adaptive
Search (EBAS). We also propose a method for maintaining popularity estimates of
the resources in the network. The work in this paper is based on an important
recent observation regarding the relationship between random walk and uniform
sampling.
·
N.
Bisnik and A. Abouzeid, “Modeling and
Analysis of Random Walk Search Algorithms in P2P Networks,” in Proceedings
of IEEE Second International Workshop on Hot Topics in Peer-to-Peer Systems
(Hot-P2P 05), San Diego, CA, July, 2005.
Stochastic Event Capture Using
Mobile Sensors
Mobile sensors cover more
area over a period of time than the same number of stationary sensors. However,
the quality of coverage achieved by mobile sensors depends on velocity,
mobility pattern and number of mobile sensors deployed and the dynamics of the
phenomenon being sensed. This research considers the gains attained, if any, by
mobile sensors over static sensors and the optimal motion strategies for mobile
sensors.
·
N.
Bisnik, A.A. Abouzeid and V. Isler, “Stochastic Event
Capture in Mobile Sensor Networks Subject to a Quality Metric,” Proceedings
of The Twelfth Annual International Conference on
Energy Efficient Coverage with
Directional Sensors
We study a new “coverage by
directional sensors” problem with tunable orientations on a set of discrete
targets. This is an Integer Linear Programming problem, which we formulate as
bi-objective and single-objective optimization. We consider centralized as well
as distributed solutions of this problem, and evaluate the properties of the
proposed solutions and algorithms in terms of providing coverage and maximizing
network lifetime through mathematical analysis and extensive simulations.
·
J. Ai and A. A. Abouzeid, “Coverage by
Directional Sensors in Randomly Deployed Wireless Sensor Networks” Journal
of Combinatorial Optimization (Springer), Special Issue on Network
Applications, 11(1):21-24, February 2006.
·
J.
Ai and A. A. Abouzeid, “Coverage by Directional Sensors,”
Proceedings of 4th Intl. Symposium on Modeling and Optimization in Mobile, Ad
Hoc, and Wireless Networks (WiOpt 2006), Boston, MA, April 3-7, 2006.
·
Optimal Stochastic Decision
Policies in Ad Hoc and Sensor Networks
·
J. Ai, Z. Ye and A. A. Abouzeid, “Cross-layer
Optimal Decision Policies for Spatial Diversity Forwarding in Wireless Ad Hoc
Networks,” in Proceedings of The Third IEEE International
Conference on Mobile Ad-hoc and Sensor Systems (MASS’06), October, 2006,
Vancouver, Canada.
·
Z. Ye, A.A. Abouzeid and J. Ai, “Optimal Policies for
Distributed Data Aggregation in Wireless Sensor Networks,” submitted.
Image Communication in
Ad-Hoc/Sensor Networks
·
A.
A. Abouzeid and H. Wu, “Energy Efficient Distributed
Image Compression in Resource-Constrained Multihop Networks,” Computer
Communications (Elsevier), 28(14):1658-1668, Sept. 2005.
·
H.
Wu and A. A. Abouzeid, “Error Resilient Image Transport
in Wireless Sensor Networks,” Computer Networks (Elsevier), to
appear.
·
H.
Wu and A.A. Abouzeid, "Power Aware Image Transmission
in Energy Constrained Wireless Networks," in Proceedings of the 9th
IEEE Symposium on Computers and Communications (ISCC), Vol.1 pages 202-7,
Alexandria, Egypt, June 2004.
·
H.
Wu and A. Abouzeid, "Energy Efficient Distributed
JPEG2000 Image Compression in Multihop Wireless Networks," in
Proceedings of the 4th workshop on Applications and Services in Wireless
Networks (ASWN), Boston, Massachusetts, August 2004.
·
H.
Wu and A. Abouzeid, “Error Resilient Image Transport in
Wireless Sensor Networks,” Proceedings of 5th Workshop
on Applications and Services in Wireless Networks (ASWN’05),