A.A. Abouzeid 2007 Publications

We consider the scenario of distributed data aggregation in wireless sensor networks, where each sensor can obtain and estimate the information of the whole sensing field through local data exchange and aggregation. The intrinsic trade-off between energy and delay in aggregation operations imposes a crucial question on nodes to decide optimal instants for forwarding their samples. The samples could be composed of the information from their own sensor readings or an aggregation of information with other samples forwarded from neighboring nodes. By considering the randomness of the sample arrival instants and the uncertainty of the availability of the multiaccess communication channel due to the asynchronous nature of information exchange among neighboring nodes, we propose a decision process model to analyze this problem and determine the optimal decision policies at nodes with local information. We show that, once the statistics of the sample arrival and the availability of the channel satisfy certain conditions, there exist optimal control-limit type policies which are easy to implement in practice. In the case that the required conditions are not satisfied, we provide two learning algorithms to solve a finite-state approximation model of the decision problem. Simulations on a practical distributed data aggregation scenario demonstrate the effectiveness of the developed policies, which can also achieve a desired energy-delay tradeoff.

Overheads incurred by routing protocols diminish the capacity available for relaying useful data over a mobile wireless ad hoc network. Discovering and understanding the lower bounds on the amount of protocol overhead incurred for routing data packets is important for development of efficient routing protocols, and for understanding the actual (effective) capacity available for network users. In this paper we use an information-theoretic approach for characterizing the minimum routing overheads of geographic routing in a mobile network. We formulate the minimum overhead problem as a rate-distortion problem. The formulation may be applied to networks with arbitrary traffic arrival and location service schemes. We evaluate lower bounds on the minimum overheads incurred for maintaining the location of destination nodes and consistent neighborhood information in terms of node mobility and packet arrival process. We also characterize the deficit caused by the routing overheads in the overall transport capacity of a mobile network.

The per-node throughput capacity of hybrid radio frequency and free space optics (RF/FSO) networks is studied and the benefit of using this hybrid network architecture over the pure RF wireless networks is evaluated. The hybrid RF/FSO network consists of an RF ad hoc network of n nodes, m of them (so called super nodes) are equipped with an additional FSO transceiver. Every RF and FSO transceiver is able to transmit at a maximum data rate of W₁ and W₂ bits/sec, respectively. All the super node are connected by the FSO links and thus can form a stand-alone FSO network. With a minimum transmit power objective, an upper bound on the per node capacity of √(1/n log n) + c₂W₂ √(m log m)/n is derived. In order to prove that this upper bound is achievable, we design a hybrid routing scheme in which the data traffic is divided into two classes and use different routing strategies: a portion of data will be forwarded with the (partial) support of super nodes in a hierarchical routing fashion, and the rest will be purely routed through RF links in a multi-hop fashion. By properly balancing the load between these two classes of traffic, it is shown that this upper bound is tight when the maximum data rate ratio of FSO and RF transceivers, W₂/W₁, grows slower than √n. Under such circumstances, the capacity improvement with the support of FSO nodes, as compared with the results for RF wireless networks in [1], is evaluated. A significant capacity gain will be achieved if W₂/W₁m log m = Ω(n). The results characterize the number of super nodes and/or the FSO data rate necessary in order to cause a non-trivial increase in the per-node throughput.

Mobile sensors cover more area over a fixed period of time than do the same number of stationary sensors. However, the quality of coverage (QoC) achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed, and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper, we consider the following event capture problem: the events of interest arrive at certain points in the sensor field and disappear according to known arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. We analyze how the QoC scales with velocity, path, and number of mobile sensors. We characterize cases where the deployment of mobile sensors has no advantage over static sensors, and find the optimal velocity pattern that a mobile sensor should adopt. We also present algorithms for two motion planning problems: 1) for a single sensor, what is the sensor trajectory and the <i>minimum speed </i>required to satisfy a bound on the event loss probability and 2) for sensors with fixed speed, what is the <i>minimum number of sensors </i>required to satisfy a bound on the event loss probability. When the robots are restricted to move along a line or a closed curve, our algorithms return the optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor of 2 of the optimal solution. For the case where the events occur at arbitrary points on a plane, we present heuristic algorithms for the aforementioned motion planning problems and bound their performance with respect to the optimal.

MAC protocols for wireless sensor networks employ periodic switching to low energy sleep state in order to enhance network lifetime. During the sleep state, the sensors do not perform energy consuming operations such as receiving and transmitting packets. During the normal state, CSMA based multi-access mechanism is the MAC protocol of choice in distributed, unsynchronized sensor networks. The energy conserving mechanism has a two-fold effect on delay in the network. On one hand it increases delay since many a times the intended receiver may be in sleep state and the transmitter has to delay the transmission to allow the receiver to wake up. On the other hand, since the sensors do not transmit in sleep state, the contention for channel is reduced which tends to improve delay. In this paper we present a queuing theoretic analysis of delay and capacity in sensor networks with uncoordinated sleep mechanism and characterize the energy-delay-capacity tradeoffs. We consider several sleep states which consume different levels of energy. We model sensor networks as queuing networks and evaluate closed form expressions for average packet delay and maximum achievable pernode throughput in terms of network parameters and sleep schedule. Comparisons with the performance of networks that do not employ any energy conserving mechanisms show that any of the energy conserving sleep states in the networks considered in this paper leads to considerable degradation in delay and capacity of the network.

Routing in communication networks involves the indirection from a persistent name (or ID) to a locator and delivering packets based upon the locator. In a large-scale, highly dynamic network, the ID-to-locator mappings are both large in number, and change often. Traditional routing protocols require high overhead to keep these indirections up-to-date. In this paper, we propose Weak State Routing (WSR), a routing mechanism for large-scale highly dynamic networks. WSR's novelty is that it uses random directional walks biased occasionally by weak indirection state information in intermediate nodes. The indirection state information is weak, i.e. interpreted not as absolute truth, but as probabilistic hints. Nodes only have partial information about the region a destination node is likely to be. This method allows us to aggregate information about a number of remote locations in a geographic region. In other words, the state information maps a set-of-IDs to a geographical region. The intermediate nodes receiving the random walk use a method similar to longest-prefix-match in order to prioritize their mappings to decide how to bias and forward the random walk. WSR can also be viewed as an unstructured distributed hashing technique. WSR displays good rare-object recall with scalability properties similar to structured DHTs, albeit with more tolerance to dynamism and without constraining the degree distribution of the underlying network. Through simulations, we show that WSR offers a high packet delivery ratio, more than 98The control packet overhead incurred in the network scales as O(N) for N-node networks. The number of mappings stored in the network appears to scale as Θ(N^3/2). We compare WSR with Dynamic Source Routing (DSR) and geographic forwarding (GPSR) combined with Grid Location Service (GLS). Our results indicate that WSR delivers more packets with less overhead at the cost of increased path length.

In this paper we analyze the average end-to-end delay and maximum achievable per-node throughput in random access multihop wireless ad hoc networks with stationary nodes. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model random access multihop wireless networks as open G/G/1 queuing networks and use the diffusion approximation in order to evaluate closed form expressions for the average end-to-end delay. The mean service time of nodes is evaluated and used to obtain the maximum achievable per-node throughput. The analytical results obtained here from the queuing network analysis are discussed with regard to similarities and differences from the well established information-theoretic results on throughput and delay scaling laws in ad hoc networks. We also investigate the extent of deviation of delay and throughput in a real world network from the analytical results presented in this paper. We conduct extensive simulations in order to verify the analytical results and also compare them against NS-2 simulations

In this paper we develop a model for random walk-based search mechanisms in unstructured P2P networks. This model is used to obtain analytical expressions for the performance metrics of random walk search in terms of the popularity of the resource being searched for and the random walk parameters. We propose an equation-based adaptive search mechanism that uses an estimate of the popularity of a resource in order to choose the parameters of random walk such that a targeted performance level is achieved by the search. We also propose a low-overhead method for maintaining an estimate of popularity that utilizes feedback (or lack there-off) obtained from previous searches. Simulation results show that the performance of the equation-based adaptive search is significantly better than the non-adaptive random walk and other straight-forward adaptive mechanisms