Dyanmic ad-hoc wireless networks (DAWN)

1. Overview
2. Research Agenda in 2005-2006
3. Research Agenda in 2006-2007
4. Participants
5. Major Publications
6. Funding Source

Overview

In the fiscal year of 2005-2006, we have striven toward two research thrusts. Along the theory thrust, we have

1. Studied the performance limits of wireless ad-hoc networks with respect to connectivity, lifetime, critical power, and their implication on protocol design.
2. Devised localized and distributed algorithms for power control (a.k.a. topology control) whose performance approaches derived theoretical bounds.

Along the simulation thrust, we have

3. Developed a number of optimization techniques to reduce the overheads for event processing in wireless network simulation.
4. Engaged in incorporating model checking in J-Simso as to enable network performance evaluation and verification in the same framework.

For the upcoming year, we plan to

5. Consider topology control under the physical model where the SINR determines the link quality (and hence the neighbor relation).
6. Study, through a tight, synergistic loop composing of measurements, modeling/analysis, and designed experiments for validation, how multi-path fading, interference, and signal attenuation due to terrain and obstacles affect the channel/link behavior in IEEE 802.11-based wireless networks, and
   1. Devise/incorporate channel models into simulators to provide high-fidelity simulation environments to the R&D community.
   2. Better characterize wireless links and its representation in virtual coordinates

Research Agenda in 2005-2006 (click here for details)

Research Agenda in 2006-2007 (click here for details)

Participants

• Chunyu Hu (partially supported by Motorola Center for Communications Fellowship, graduated in October 2006, and is currently a research scientist with Broadcom, Inc.).
• Ning Li (graduated in October 2005, and is currently a software engineer with the Operating Systems group of Microsoft Corporation).
• Jong-Kwon Lee (Postdoctoral research fellow 2003-2005; partially supported by Korean Research Foundation).
• Ting-Yu Lin (Postdoctoral research fellow 2005-2006; partially supported by Taiwan Ministry of Education Postdoctoral Fellowship).
• Ahmed Sobeih (Ph.D. candidate; partially supported by Vodafone Graduate Fellowship).
• Yong Yang (Ph.D. student).
• Zheng Zeng (Ph.D. student).
• Honghai Zhang (graduated in October 2005, and is currently a member of technical staff with Open Innovation Laboratories of Lucent Technologies, Whippany, NJ).

Major Publications

1. Ning Li and Jennifer C. Hou, “Localized topology control algorithms for heterogeneous wireless networks,” IEEE/ACM Trans. on Networking, Vol. 13, No. 6, pp. 1313–1324, December 2005. pdf
2. Ning Li and Jennifer C. Hou, ‘Localized fault-tolerant topology control in wireless ad hoc networks,” IEEE Trans. on Parallel and Distributed Systems, special issue on Localized communication and topology protocols for ad hoc networks, Vol. 17, No. 4, pp. 307–320, April 2006. pdf
3. Ning Li and Jennifer C. Hou, “A scalable, power-efficient broadcast algorithm for wireless networks,” ACM Springer Wireless Networks (WINET), Vol. 12, No. 4, pp. 495–509, August 2006. pdf
4. Honghai Zhang and Jennifer C. Hou, ”An algorithm for maximizing alpha-lifetime for wireless sensor networks”, International Journal of Sensor Networks (IJSNet), Vol. 1, No. 1, June 2006 (invited). pdf
5. Honghai Zhang and Jennifer C. Hou, “On deriving the upper bound of alpha-lifetime for large sensor networks,” ACM Trans. on Sensor Networks, Vol. 1, No. 2, pp. 272–300, November 2005. pdf
6. Honghai Zhang and Jennifer C. Hou, ”On the critical total power for asymptotic k-connectivity in wirelessnetworks,” Proc. IEEE INFOCOM, Miami, Florida, March 2005. pdf
7. Ahmed Sobeih, Wei-Peng Chen, Jennifer C. Hou, Lu-Chuan Kung, Ning Li, Hyuk Lim, Hung-Ying Tyan, and Honghai Zhang, “J-Sim: a simulation and emulation environment for wireless sensor networks,” IEEE Wireless Communications Magazine, Vol. 13, No. 4, August 2006. pdf
8. Ahmed Sobeih, Mahesh Viswanathan, Darko Marinov, and Jennifer C. Hou, “Finding bugs in network protocols using simulation code and protocol-specific heuristics,” Seventh International Conference on Formal Engineering Methods (ICFEM 2005), pp. 235–250, Manchester, UK, November 2005. pdf
9. Jennifer C. Hou and P. R. Kumar, “Network modeling and simulation,” editorial for the special issue of network modeling and simulation in Computer Networks Journal, Vol. 50, No. 12, pp. 1885–1886, August 2006. pdf
10. Honghai Zhang and Jennifer C. Hou, “On the asymptotic minimum energy and its implication on deriving the capacity of wireless networks,” ACM/IEEE Trans. on Networking, to appear (accepted in August 2006). pdf
11. Chunyu Hu and Jennifer C. Hou, “A reactive channel model for expediting wireless network simulation,” ACM SIGMETRICS, Banff, Alberta, Canada, June 2005. pdf
12. Chunyu Hu and Jennifer C. Hou, “Toward efficient and scalable wireless network simulation,” submitted to IEEE Wireless Communications Magazine, August 2006.
13. Hwangnam Kim, Hyuk Lim, and Jennifer C. Hou, “ Accelerating simulation of large-scale IP networks: an network invariant preserving approach,” Proc. of IEEE INFOCOM 2006, March 2006 (acceptance ratio = 18). pdf
14. Honghai Zhang and Jennifer C. Hou, “Is deterministic deployment worse than random deployment for wireless sensor networks,” Proc. IEEE INFOCOM, Barcelona, Spain, March 2006 (acceptance ratio = 18%). pdf
15. Jong-Kwon Lee and Jennifer C. Hou, “Modeling steady-state and transient behaviors of user mobility: formulation, analysis, and application,” Proc. of ACM 7th International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc’06), Florence, Italy, May 2006 (31/318, acceptance rate = 10%). pdf
16. Yong Yang, Jennifer C. Hou, and Lu-Chuan Kung, “Modeling of physical carrier sense in multi-hop wireless networks and its use in joint power control and carrier sense adjustment,” Proc. of IEEE INFOCOM 2007 miniconference, May 2007.
17. Ting-Yu Lin and Jennifer C. Hou, “Interplay of spatial reuse and SINR-determined data rates in CSMA/CAbased, multi-hop, multi-rate wireless networks,” Proc. IEEE INFOCOM 2007, May 2007.
    

Funding Source

Detailed Description of Research Agenda in 2005-2006

We have performed a rigorous, integrated study of performance limits for wireless networks with respect to network connectivity, lifetime, and critical power, and how they scale as the network size or density increases. All the above attributes are at heart linked by the power level each node chooses for its transmission and for its sensing tasks. The choice of power levels determines several node attributes: (i) the transmission range (as well as the interference caused by transmission), (ii) the node degree, and (iii) the sensing range. Consequently, it influences the physical layer through the quality of the received (sensing and communications) signal, the MAC layer through the interference and contention caused by communications, the network layer through the set of links that are formed (and hence the connectivity), the transport layer through the overall data transport capability (and hence the network capacity), and last but not least, the drain on battery energy. Indeed, choice of power levels is critical to several aspects of wireless network functionality. However, the relationship has not been fully investigated. It is not clear how asymptotic conditions for ensuring network properties relate to each other. It is also not clear how the asymptotic condition for ensuring one network property ultimately impacts the other node/network attributes and the overall network performance.

We have sought a structured way of understanding these issues in both analytical and practical settings: on the one hand, we have derived in an analytic framework the critical conditions, such as the transmission power (which, in turns, determines the transmission range and the node degree) and/or the node density, in order to ensure certain network property (e.g., connectivity) in the asymptotic sense and its impact on the other network attributes. For example, we have investigated the critical power required (in the almost surely sense) to maintain connectivity and how it scales as the network size or density increases [6, 14, 10]. We have also studied how much power is saved (in the asymptotic sense) if topology control is exercised (i.e., each node can transmit with power levels other than the maximal transmit power. Specifically, we derive lower and upper bounds on the critical total power and study how these bounds scale as the network density increase [10].

Once the power levels used by nodes are determined, their transmission range, neighbor relation, as well as the network lifetime are also determined. We have conducted similar studies to derive critical conditions (in terms of the node density required) to ensure network lifetime of certain span [5, 4]. With the above relationships derived, we have answered several fundamental questions such as: (i) how many wireless nodes (or the nodal density) have to be deployed in a region, in order to maintain a network lifetime of pre-determined duration; and (ii) given the number of wireless nodes (or the nodal density), what is the maximal possible lifetime that can be achieved by any algorithm.

(2) Localized and distributed algorithms for topology control

With the insight revealed from the above analytic study, we have designed distributed and localized algorithms (and their corresponding protocols) that minimize the total transmission power of all wireless nodes while maintaining connectivity [2, 3, 1]. By “localized,” we mean the algorithms do not rely on the global information that needs to be relayed by nodes multiple hops away. This feature is especially important in devising practical and readily deployable algorithms in wireless (sensor) networks. Specifically, we have devised a Local Minimum Spanning Tree (LMST) algorithm and its variations for topology control and management. In LMST, each node builds its local minimum spanning tree independently with the use of locally collected information, and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We have proved analytically that if every node exercises LMST, then the network connectivity is preserved (i.e., if the original topology in which each node uses the maximal transmit power is connected, then the topology derived under LMST is also connected). We have also analytically proved that (1) the node degree of any node in the resulting topology is bounded by 6; and (2) the topology can be transformed into one with bi-directional links (without impairing the network connectivity) after removal of all uni-directional links).

We have shown in [1] that most of the topology control algorithms (including LMST) render sub-optimal performance or even fail when different nodes may have different maximal transmission ranges (Figure 1). The major problem is that the connection between a pair of nodes may not be bi-directional in the topology in the case of heterogeneous networks. This scenario is, however, typical in the battlefield where different warfare entities have dramatically different capabilities. To deal with this problem, we have devised localized topology control algorithms for heterogeneous wireless multi-hop networks with non-uniform transmission ranges.

Figure 1: An example that shows the algorithm in which each node builds a local directed minimum spanning tree and only keeps the one-hop neighbors may result in disconnectivity.

(3) Trade-off between topology robustness and performance

In spite of the many advantages of topology control and management, it eliminates redundant paths between sources and destinations. In a controlled topology, if a node fails (due to power depletion and/or malicious destruction) or moves away, the network is more susceptible to temporary disconnection. Obviously there exists a trade-off between route redundancy and the other performance aspects (power consumption, spatial reuse, MAC level interference, and network capacity). We have, on the one hand, study the fundamental trade-off between fault tolerance and throughput improvement in MANETs, and on the other hand, extend LMST to preserve k-connectivity and evaluate the resulting algorithm, FLSS_k via simulation and empirical studies with respect to the overall system throughput decrease caused by incorporating fault tolerance [2]. For example, as shown in Figure 2(a)–2(c), as k increases, FLSS_k renders topologies that have larger average degrees, longer average radii, and longer average maximum radii, and consume more power. However, the topologies are also more robust and are resilient to k-1 failures. We have also compared FLSS₁, FLSS₂ and FLSS₃ with respect to the total amount of data delivered (Figure 2(d)), the total energy consumption (Figure 2(e)), and the energy efficiency (Figure 2(f)). It can be observed that with the increase in the level of network connectivity (in the order of FLSS₁, FLSS₂, FLSS₃, NONE), the total throughput decreases, the total energy consumption increases, and the energy efficiency decreases. This result again demonstrates the trade-off between the robustness (or routing redundancy) and the network capacity/energy efficiency.

Figure 2: Comparison of FLSS₁, FLSS₂ and FLSS₃.

(4) Optimization techniques for expediting wireless network simulation

The major obstacle in realizing faster-than-real-time is the vast number of packets that have to be simulated in order to produce accurate results. Each packet will generate a number of events (e.g., arrival of a packet at the router, its departure, and its queuing, and buffer depletion, just to name a few) on its path from the source to the destination. In wireless environments where high-fidelity results can only be obtained with simulation at the signal level, the problem becomes even more pronounced. Due to the broadcast nature of a wireless channel, transmission of a signal has to be received and processed by all nodes operating on the same channel (and neighboring channels if co-channel interference is taken into account). This implies that one signal transmission event will generate numerous signal receipt events. As the CPU time required is roughly proportional to the number of events that have to be executed, packet-level simulation easily becomes computationally expensive, if not infeasible, when the network size and/or the traffic amount becomes large. In our profiling work [11], we have shown that to simulate a typical WiFi scenario in which nnodes operate in a 802.11-operated wireless LAN, each of which sends CBR traffic at the rate of 0.5 Mbps, it takes 17083 seconds (4.75 hours) in real time to carry out a 60-second simulation run in the case of n=10. Moreover, half of the execution time is spent on the event scheduling and handling activities.

To deal with the above problems, we have proposed the notion of reactive scheduling in which the signal arrival notification events (triggered by the signal transmission event injected by a node) are dispatched only to nodes in a recipient set V, where and V_L is the set of nodes located within the propagation limit L of the signal. The set of V is composed of two subsets: (i) V₁ is the set of nodes located within the communication range of the transmitter node; and (ii) V₂ is the set of nodes that are outside the communication range but explicitly register to receive signal arrival notification events. This set is determined based on whether or not a node needs to monitor the channel continuously. In a network operated with a CSMA-based MAC protocol (such as IEEE 802.11 MAC), this refers to when a node attempts to access the channel or is in reception of a signal (that is, when the backoff/defer timer is running). We have designed and implemented in [12] the reactive channel model (RCM, along with other optimizations) in such a manner that they are completely transparent to protocol models, implemented in the simulation kernel, and can be turned on by means of a set of appropriately defined compile-time flags. Fig. 3 gives the time consumption rate under RCM, LSCR, and the conventional channelmodel as (a) the node density, (b) the traffic load, (c) the field size, and (d) the propagation limit increases, respectively. The execution time under the conventional channel model increases drastically as either of the system parameters (node density, traffic load, field size, and propagation limit) increases. The performance of RCM is comparable to that of LSCR (except for Fig. 3(b)), and both of them achieve approximately an order of magnitude improvement in expediting simulation over the conventional channel model.

Figure 3: Simulation efficiency achieved by the conventional channel model, RCM, and LSCR with respect to node density, traffic load, field size and propagation limit. In (c) the field size is normalized to 500m x 500m. In (d) the propagation limit is normalized to distCST.

(5) Incorporating model checking into J-Sim

Another direction we have worked toward is to incorporate model checking into network simulation. Existing network simulation environments perform well in evaluating the performance of network protocols but lack the capability of verifying the correctness of protocols. In order to address this lacuna, we have extended J-Sim [7] with a model checking capability [8] to explore the state space of a network protocol in order to find an execution where a safety invariant is violated. We have exploited protocol-specific properties in the process of exploring the state space, to reduce the size of the state space and to guide the (best-first) search towards paths that can potentially locate errors in less time.

Design of special-purpose model checkers for network simulator code enjoys one attractive benefit, over using generalpurpose verification tools—it saves the protocol designer the task of building a special-purpose model of the protocol for verification and a separate model for performance analysis. Since building a formal model of a protocol is an onerous, time-consuming and error-prone task, by designing special-purpose model checkers for network simulator code, we not only ensure that verifying a protocol is easier for the designer, but also ensure that the model being verified is consistent with the implementation.

Detailed Description of Research Agenda in 2006-2007

Tuning the transmit power also has the effect of defining the network topology (as these operations determine the link quality). All the topology control algorithms in the literature (including ours) define the neighbor relation based on the protocol model, i.e., a link may exist between nodes i and j if their Euclidean distance d_ij <= d_max, where d_max is the maximum transmission distance). While the protocol model is simple, it ignores the effect of SINR. Instead, it is more appropriate to define a link under the physical model, i.e., a link exists between node i and j if and only if

(1)

holds, where G_ij is the antenna gain, P_t(i) is the transmit power of node i, is the path loss exponent, N(j) is the noise at node j, and  is the minimum acceptable SINR. In our preliminary study, we have devised a feasibility test that (in)-validates a given topology under the physical model. Specifically, given a topology T, an edge must satisfy Eq. (1). For every node i(1 <= i <= n), Eq. (1) can be rewritten as

(2)

As Eq. (2) is a linear function of P_t(i), we can formulate a linear program with respect to P_t(i), (1 <= i <= n). The linear problem has no objective function but has a set of n constraints expressed in Eq. (2). If the linear program has a solution, the given topology is valid under the physical model and the transmit power P_t(i), (1 <= i <= n), is a valid power assignment; otherwise, the topology is invalid with respect to SIR_min. Surprisingly in our preliminary study [16, 17], none of the topology control algorithms, e.g., LMST, CBTC and Yao’s algorithm, survive the feasibility test when they are put into the context of PHY/MAC characteristics.

The above results prompt us to reconsider the definition of topology control. Let L(n) denote the set of node locations (usually defined in Euclidean distances in the local or global view), and T(n) the set of topologies that define the neighbor relations. Topology control under the protocol model is to devise the following function TC : L(n) -> T(n) with the objective of preserving network connectivity. However, under the physical model topology control is to devise the following function TC : L(n) x T(n) -> P(n), where C(n) specifies the node configuration (e.g., the minimal acceptable SINR , the minimal/maximal transmit power) and P(n) is the set of power assignment. Moreover, in addition to preserving network connectivity, increasing spatial reuse and maximizing network capacity can also be figured in as part of the objectives. The major difficulty is that validating whether or not the neighbor relation exists between a pair of nodes (i.e., a link satisfies the SINR constraint) depends not only on the power assignment on this link but also on that on all the other links. We will investigate the fundamental role between the (local) neighbor relation and the (global) power assignment.

(2) Better characterization of wireless links and its representation in virtual coordinates

Our preliminary profiling work on a local, city-wide wireless network, Champaign Urbana Community Network (CUWiN) has shown that a channel in real-life networks cannot be modeled as one with Additive White Gaussian Noise (AWGN). As shown in Figure 4, the relationship between the delivery ratio (the SNR) and the distance exhibits randomness and does not follow any of the existing channel models (which usually take into account of only one or two factors). This implies that the distance between two wireless nodes is no longer a good characterization of wireless links, and naturally leads to the questions of (i) what would be a better characterization and (ii) whether or not one can still represent the network topology a coordinate system.

We believe there may not be a single attribute that serves all the purposes, and at times a combination of several attributes may be the best. However, we believe a new coordinate system should be devised to appropriately characterize the neighbor abstraction with respect to one or more attributes. To this end, we propose to characterize the location of a node n in a virtual coordinate system, with the set of measurements it makes between itself and nodes whom it can receive (decodable) signals. The measurements among nodes whom node n can communicate with can then represented by a p x p square matrix S, where p is the number of nodes whom n can communicate with and each column can be considered as the coordinate of the corresponding nodes in a p-dimension space. There are again two issues associated: (i) the dimension p may be large; (ii) some of the entries in S may not be available, because two nodes whom node ncan directly communicate with may not within the transmission range of each other; and (ii) these coordinates are likely to be correlated with each other, and hence it is difficult to identify components that play an important role in determining the interferences.

To tackle the above research issues, we propose to construct, with principal component analysis (PCA), a virtual coordinate system that represents the neighbor abstraction with a smaller dimension. In a nutshell, PCA transforms a data set that consists of a large number of (possibly) correlated variables to a new set of uncorrelated variables, principal components so that the first several components have the most important features of the original attribute variables, and the kth principal component represents the direction of maximizing the variation of projections of measured attributes while orthogonal to the first (k-1)th principal components. We will investigate whether or not the coordinate system thus constructed can be used essentially in the same manner as the physical Euclidean coordinate system. The results, if empirically evaluated to be positive, will represent a major breakthrough in characterizing the neighbor abstraction in wireless environments.

Figure 4: The relationship between the distance and (a) the delivery ratio and (b) the SNR, for a 11 Mb/s network. Each dot represents a connection. Results for a 2 Mb/s network are similar.

(3) When network simulation meets the real-world

In spite of the fact that wireless links depend very much on the characteristics of PHY/MAC attributes and environmental factors, and their impact on higher-layer protocols has been shown to be quite significant, research activities for wireless networking and communications have been carried out, and results (in-)validated, most of the time via simulation with over-simplified PHY/MAC models. For example, ns-2 — one of the most widely used open-source simulation environments — contains only the free-space propagation model and the two-ray ground model in the PHY layer. The effect of accumulated interference (that affects physical carrier sense in the MAC layer) and the capture effect also have not been faithfully modeled. The situation has been further aggravated by the fact that accurate models that characterize channel behaviors in the the 2.4 GHz or 5 GHz industrial, science, and medical (ISM) frequency band in outdoor environments have been lacking and hence cannot be incorporated into simulators. To ensure network algorithms and protocols be designed/evaluated in realistic settings, a large-scale wireless network testbed situated in the same environments where production wireless networks will be deployed is strongly called for. Through partial sponsorship of NSF, we have been building a Champaign Urbana Wireless Mesh Network (CUWiN) testbed (http://www.cuwireless.net), and will study (through a tight, synergistic loop composing of measurements, modeling/analysis, and designed experiments for validation) how multi-path fading, interference, and signal attenuation due to terrain and obstacles affect the channel/link behavior. The channel models thus derived (as well as those derived by the DAWN team) will be incorporated into several widely-used simulation environments (e.g., ns-2 and J-Sim) to create more realistic simulation environments.