Research Highlights (2008-2014):
The list below includes a selection of publications each grouped by a topic area. Each paper includes a link to a pdf of the camera version of the paper, which is included here under the relevant copyright rules and regulations for sharing for academic purposes. The final version is copyright protected by the corresponding publisher. A slide set for each paper is included when available, which may include results published in other venues.
Real-Time Auction Mechanisms for Dynamic Spectrum Sharing
- M. Khaledi and A. A. Abouzeid, “ADAPTIVE: A Dynamic Index Auction for Spectrum Sharing with Time-Evolving Values,” 12th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), Hammamet, Tunisia, May 12-16, 2014. [paper,slides]
Queuing Models of Wireless Networks
- D. Das, A. A. Abouzeid, “Delay Analysis of Multihop Cognitive Radio Networks Using Network of Virtual Priority Queues,” IEEE Wireless Communications and Networking Conference (WCNC), (to appear), Istanbul, Turkey, April 7-9, 2014. [paper, slides]
- N. Bisnik and A. A. Abouzeid. Queuing Network Models for Delay Analysis of Multihop Wireless Ad Hoc Networks. Ad Hoc Networks, 7(1): 79-97, January 2009. (A version of this work appeared in SECON 2006.) [paper, slides]
Optimal Scheduling
- D. Das, A. A. Abouzeid and M. Codreanu, “Opportunistic Scheduling and Relaying in a Cooperative Cognitive Network,” 12th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), (to appear), Hammamet, Tunisia, May 12-16, 2014. [paper]
Protocol Information and Scaling
- 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 Mobile Ad-Hoc Networks, 23(3): 547-560, March 2005. (A version of this work appeared in MobiCom 2003.) [paper, slides]
- A.A. Abouzeid and N. Bisnik, “Geographic Protocol Information and Capacity Deficit in Mobile Wireless Ad Hoc Networks,” IEEE Transactions on Information Theory, 57(8): 5133-50, August 2011. (A version of this work appeared in INFOCOM 2007.) [paper, slides ]
Sensor Networks Data Aggregation
- Z. Ye, A. A. Abouzeid and J. Ai, Optimal Stochastic Policies for Distributed Data Aggregation in Wireless Sensor Networks, IEEE/ACM Trans. on Networking, 17(5): 1494-1507, October 2009. (A version of this work appeared in INFOCOM 2007.)[paper, slides]
Mobile Sensing
- N. Bisnik, A.A. Abouzeid and V. Isler, “Stochastic Event Capture Subject to a Quality Metric,” IEEE Transactions on Robotics, 23(4), August 2007. (A version of this work appeared in MobiCom2006.) [paper, slides]
Sensor Networks Coverage
- J. Ai and A. A. Abouzeid, “Coverage by Directional Sensors in Randomly Deployed Wireless Sensor Networks” Journal of Combinatorial Optimization, Special Issue on Network Applications, 11(1): 21-24, February 2006. (A version of this work appeared in WiOpt 2006.) [paper, slides]
Weak State Routing for Dynamic Delay-Tolerant Networks
- U. G. Acer, S. Kalyanaraman, A. A. Abouzeid, Weak state routing for large-scale dynamic networks, IEEE/ACM Trans. on Networking, 18(5): 1450-63, October 2010. (A version of this work appeared in MobiCom 2007.) [paper, slides]
Cross-Layer Optimization
- J. Ai and A.A. Abouzeid, “Cross-layer Optimal Policies for Spatial Diversity Relaying in Mobile Ad Hoc Networks,” IEEE Transactions on Wireless Communications, 7(8): 2930-2939, August 2008. (A version of this work appeared in MASS 2006.) [paper, slides]
Randomized Algorithms & Random Walks on Graphs
- N. Bisnik and A.A. Abouzeid, “Optimizing Random Walk Search Algorithms in P2P Networks,” Computer Networks, 51(6): 1499-1514, April 2007. (A version of this work appeared in Hot-P2P 2005.) [paper, slides]
TCP and Internet Routing Performance
- A.A. Abouzeid, S. Roy and M. Azizoglu, “Comprehensive Performance Analysis of a TCP Session over a Wireless Fading Link with Queuing”, IEEE Transactions on Wireless Communications, 2(2): 344-356, March 2003. (A version of this work appeared in INFOCOM 2001.) [paper, slides]
- A.A. Abouzeid and S. Roy, “Modeling Random Early Detection in a Differentiated Services Network”, Computer Networks, 40(4): 537-556, November 2002. (A version of this work appeared in GLOBECOM 2001.) [paper, slides]
Distributed Image Processing
- H. Wu and A.A. Abouzeid, “Energy Efficient Distributed Image Compression in Resource-Constrained Multihop Networks,” Computer Communications, 28(14): 1658-1668, September 2005. [paper,slides]
Research Highlights(1999-2008):
Below is a description/motivation of some past (pre-2008) research directions grouped by theme. (refer to the first tab above for more recent research results )
1. Basic Limits on Protocol Information in Variable Topology Computer Networks
Since routing protocols need to adjust to topology change, an overhead is incurred due to the exchange of routing messages. For variable topology networks, such an overhead may impose a significant limit on scalability and effective capacity. For example, it has been noted from measurement data that in certain modern networks (e.g. a portion of the U.S. Air Force network), such overheads constituted 80% of the total traffic carrying capacity. Thus, it is important to understand how the overhead scales for various protocol-design choices.
We developed an information-theoretic framework for the characterization of bounds on the least overhead incurred by various classes of routing protocols under a uniform traffic pattern. The key departure point of the new framework is to treat the state (e.g. link state, node location, hybrid of both) as a random variable that exhibits random changes. The minimum protocol overhead is related to the minimum amount of information (i.e. effort) needed to identify the current state of the system, possibly within a distortion bound. The various state changes are derived from the probability distribution describing the cause of dynamism, e.g. the nodes mobility pattern. Thus the protocol overhead problem is brought into an information theoretic framework, and terms like entropy rate now yield new practical design guidelines and basic limits on the best possible protocol design. For example, we can now characterize the highest possible effective capacity of a network, by subtracting the lowest capacity deficit among all possible protocol designs.
We have also considered the routing protocol overhead problem from a different angle that has not been considered before in the literature. That is, we took into account the interdependence between the communication pattern, in terms of the distribution of number of hops between source destination pairs, and the routing overhead. Interestingly, it turns out that reactive routing protocols can operate efficiently for asymptotically large networks (even with an infinite number of nodes) if the traffic is sufficiently localized statistically. We have analytically characterized the sufficient conditions and validated them through extensive simulations of realistic protocol implementations.
Presentations:
"Entropy Measures of Routing: Towards a First Law of MANET Info-dynamics," DARPA ITMANET workshop March 7, 2006: .pdf
"Scaling Laws of Variable Topology Networks; Stochastic and Information Theoretic Approaches," Princeton ISS seminar, March 2, 2006 : .pdf, .pps
" Rate-Distortion Bounds on Location-Based Routing Protocol Overheads in Mobile Ad Hoc Networks," Allerton 2006 Conference, September 27 2006: .pdf
"NSF Project Link: Routing and Information Theory (2003-2006)
Some Key Publications:
-N. Bisnik, A.A. Abouzeid, Rate-Distortion Bounds on Location-Based Routing Protocol Overheads in Mobile Ad Hoc Networks, Proceedings of Allerton 2006, Sept 27-29, Allerton House, UIUC, Illinois, USA. .pdf
-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. (draft)
-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. (Conference version in IEEE INFOCOM 2005).
-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 Mobile Ad-Hoc Networks, vol. 23, no. 3, pp. 547-560, March 2005. (Conference version in MobiCom 2003).
-Huaming Wu and A.A. Abouzeid, Cluster-based Routing Overhead in Networks with Unreliable Nodes, Proceedings of IEEE Wireless Communications and Networking Conference (WCNC 2004), vol. 4, pp. 2557-2562, Atlanta, Georgia, USA, March 21-25, 2004.
- Efficient Coverage using Wireless Sensor Networks
Sensing coverage is a fundamental problem in wireless sensor networks. It reflects how well the environment is monitored, and serves as a basis for applications such as physical phenomenon or target detection, classification and tracking. Due to the increasing diversity of sensor network applications, the concept of sensing coverage includes a growing range of interpretations.
In this work, we consider coverage problems involving two new characteristics of emerging visual as well as mobile sensor networks. The solution approach to both problems utilizes tools from optimization theory and algorithmic complexity.
In the first problem, we study power-efficient coverage by randomly deployed directional sensors with tunable orientations on a set of discrete targets. This problem arises, for example, in networks of visual surveillance sensors (e.g. on-chip cameras with finite field of view). 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 (minimizing the number of targets missed) while maximizing network lifetime through mathematical analysis and extensive simulations. Furthermore, the topic has interesting synergies with the research interest of collaborators in the computer vision group from ECSE and CS.
In the second problem, we consider a network of sensors whose mobility is controlled by the designer (rather than random). The objective is to capture stochastic events appearing at points of interest with a minimum target quality. While mobile sensors cover more area over a period of time than the same number of stationary sensors, the quality of coverage achieved by mobile sensors depends on the 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. Applications of these results span a wide array of applications, from unmanned underwater vehicles to border control. Synergies also exist here with the robotics group.
We also considered the effect of packet loss on the quality of coverage in sensor networks. This is important since packet loss can not be avoided due to the use of wireless links. This issue has been considered in the context of a network of geotechnical sensors for monitoring landslides developed in collaboration with the Civil Engineering department (through NSF funding).
Presentations:
Some Key Publications:
-J. Ai and A. A. Abouzeid, Coverage by Directional Sensors in Randomly Deployed Wireless Sensor Networks, Journal of Combinatorial Optimization, Special Issue on Network Applications, vol. 11, no. 1, pp. 21-24, February 2006. (Conference version in WiOpt 2006.)
-N. Bisnik, A.A. Abouzeid and V. Isler, Stochastic Event Capture Subject to a Quality Metric, IEEE Transactions on Robotics, conditionally accepted in November 2006. (Conference version in ACM MobiCom 2006).
-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 Mobile Computing and Networking (MobiCom 2006), pp. 89-109, Los Angeles, California, USA, September 24-29, 2006.
- Queuing Theory Analysis of Random Access Ad Hoc and Mesh Networks
Wireless mesh networks, represented for example by the new IEEE 802.16 (WiMAX) standard, are emerging as a promising means of providing connectivity to communities in both affluent and poor parts of the world. They are also proposed as a solution for the last-mile problem, and extending network access to rural areas. They build on the concept of ad-hoc networks, but they also rely on the presence of relatively more capable backbone mesh routers forming a two-level hierarchy, thus allowing mesh networks to have better capacity than infrastructure-less multihop ad hoc networks.
In both types of networks, delay and throughput are two important performance metrics. In this work, we develop a queuing network model for characterizing the average end-to-end delay and maximum stable throughput (per source-destination pair) in ad-hoc and wireless mesh networks that employ random medium access (MAC) schemes. We analyze how the results obtained using the proposed queuing network framework compare against previous information-theoretic results on asymptotic capacity of infrastructure-less ad hoc networks.
Presentations:
Some Key Publications:
- N. Bisnik and A.A. Abouzeid, Delay and Throughput in Random Access Wireless Mesh Networks, Proceedings of 2006 IEEE International Conference on Communications (ICC 2006), Istanbul, Turkey, June 11-15, 2006.
-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), Vancouver, Canada, July 3-6, 2006.
4. Optimal Localized Decision Policies in Ad Hoc and Sensor Networks
In computer networks, each node makes decisions based on its local information (i.e. without global knowledge) under uncertain conditions. For example, a sensor network node may need to decide whether to send its local samples immediately, thus minimizing delay, or wait for more samples to aggregate before sending the data, thus minimizing communication energy consumption. Similarly, an ad hoc network node may need to decide whether to select a particular neighboring node to forward a packet to, or to keep searching for other neighbors with more favorable channel conditions.
These types of decision problems are quite common in wireless networks. In our work, we formally define them as stochastic decision problems, and derive optimal policies that maximize the expected reward. For the sensor network problem, we derive optimal threshold-type policies and analyze conditions for the optimality of these simple-to-implement policies. We also design model-free learning algorithms for situations where the conditions for optimality of threshold-based policies do not hold. For the ad-hoc network problem, the problem can be formulated as an optimal stopping problem in a cross-layer design context. We implement the policies in a protocol stack composed of IEEE 802.11 MAC and geographic routing. The simulation results show significant improvements compared to state-of-the-art cross-layer forwarding protocols.
Presentations:
-MASS 2006 (includes voice annotation)
-INFOCOM 2007
Some Key Publications:
-Z. Ye, A.A. Abouzeid and J. Ai, Optimal Policies for Distributed Data Aggregation in Wireless Sensor Networks, to appear, Proceedings of 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, Alaska, USA, May 6-12, 2007.
-J. Ai, Z. Ye and A.A. Abouzeid, Cross-layer Optimal Decision Policies for Spatial Diversity Forwarding in Wireless Ad Hoc Networks, Proceedings of Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2006), October 9-12, 2006, Vancouver, Canada.
5. Randomized Algorithms for Overlay and Disconnected Networks
Locating a resource/ service or a peer efficiently is one of the most important issues related to unstructured decentralized 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. 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 called Equation Based Adaptive Search (EBAS). We also propose a method for maintaining popularity estimates of the resources in the network. The work is based on an important recent observation regarding the relationship between random walk and uniform sampling. The work is currently being extended to utilize location information. This extension is specifically useful for delay tolerant networks (DTNs).
Presentations:
Some Key Publications:
- N. Bisnik and A.A. Abouzeid, “Optimizing Random Walk Search in P2P Networks,” Computer Networks, in press, available online (ScienceDirect) 18 September 2006. (Conference version in HoTP2P 2005).
6. Image Communication in Resource Constrained Networks
Wireless Visual Sensor Networks is a promising new type of sensor network in which nodes are equipped with cameras. It presents several challenges beyond those common to low data rate sensing, such as temperature or pressure. We develop several schemes which enable efficient image compression and transmission in wireless sensor networks. The first scheme addresses the problem of minimizing the energy dissipation for transmitting compressed images over a multi-hop network subject to a specific image quality constraint. The second scheme considers distributed image compression as a means to overcome the resource limitations of individual nodes by sharing the processing tasks. It has the additional benefit of extending the overall lifetime of the network by distributing the computation load among otherwise idle processors. Finally, the third scheme provides resiliency against packet losses in wireless networks by allowing nodes to perform “in-network” diversity combining. The schemes provide significant energy savings and improved image quality.
Some Key Publications:
-H. Wu and A.A. Abouzeid, Error Resilient Image Transport in Wireless Sensor Networks, Computer Networks, vol. 50, no. 15, pp. 2873-2887, October 2006.
-H. Wu and A.A. Abouzeid, Energy Efficient Distributed Image Compression in Resource-Constrained Multihop Networks, Computer Communications, vol. 28, no. 14, pp. 1658-1668, September 2005.
-H. Wu and A.A. Abouzeid, Error Robust Image Transport in Wireless Sensor Networks, Proceedings of 5th Workshop on Applications and Services in Wireless Networks (ASWN 2005), Paris, France, June 29 – July 1, 2005.
-H. Wu and A.A. Abouzeid, Energy Efficient Distributed JPEG2000 Image Compression in Multihop Wireless Networks, Proceedings of the 4th Workshop on Applications and Services in Wireless Networks (ASWN 2004), pp. 152-160, Boston, Massachusetts, August 9-11, 2004.
-H. Wu and A.A. Abouzeid, Power Aware Image Transmission in Energy Constrained Wireless Networks, Proceedings of the 9th IEEE Symposium on Computers and Communications (ISCC 2004), vol. 1, pp. 202-207, Alexandria, Egypt, June 28- Jul 1, 2004.
- Transport and Congestion Control in Hybrid and Wireless Networks
TCP is the predominant Transport Control Protocol in the Internet, reportedly responsible for carrying 95% of Internet traffic. However, the wireless mobile network environment introduces two new components that were not considered in the design of TCP [30] for previous traditional wired networks; mobility and wireless communications. The problems that hinder TCP performance over wireless mobile networks can be traced to a mismatch between the inherent assumptions in the design of TCP and actual conditions of operation in the wireless mobile network environment. I have worked extensively on TCP-related problems. The work can be categorized depending on the attributes of the networking environment to (i) Wireless Access: situations where a possibly mobile user accesses an infrastructure network using a last-hop wireless link. (ii) Wired Infrastructure Network: Analysis of the interaction between multiple competing TCP and non-TCP flows over a network of traditional as well as Active Queue Management routers, with multiple transport-layer differentiated service classes. (iii) Mobile Wireless Network: Analysis of TCP with abrupt RTT changes. This work resulted in key new insights and analytical modeling contributions to the area of TCP modeling.
Some Key Publications:
- A.A. Abouzeid and S. Roy, Stochastic Modeling of TCP in Networks with Abrupt Delay Variations, Wireless Networks, vol. 9, no.5 pp. 509-524, September 2003.
A.A. Abouzeid, S. Roy and M. Azizoglu, Comprehensive Performance Analysis of a TCP Session over a Wireless Fading Link with Queuing, IEEE Transactions on Wireless Communications, vol. 2, no. 2, pp. 344-356, March 2003.
A.A. Abouzeid and S. Roy, Modeling Random Early Detection in a Differentiated Services Network, Computer Networks, vol. 40, no. 4 pp.537-556, November 2002.