Towards building a high-performance, interference-mitigated and robust wireless mesh network

1. Overview
2. Research Agenda
3. Participants
4. Major Publications
5. Funding Source
6. Related Links

Overview

The community wireless network, though still in its infancy, has gained tremendous attention and has been proposed to replace existing cable/dial-up based networks, with $15B to $16B projected revenue over the next few years. Although initial success has been reported in several city-wide wireless access projects, a number of performance related problems have also been identified, including excessive packet losses, unpredictable channel behaviors, inability to find stable and high-throughput routes, and throughput loss due to intra-flow and inter-flow interference. These problems are all rooted in the fact that the notion of a link no longer exists in wireless environments. In addition, the lack of an open, modular programming environment hinders the wide deployment of wireless mesh networks. -- Existing code distributions are often implemented in an ad-hoc manner, lack structural modularity, and do not come with well-defined APIs for experimentation and performance tuning. These problems present a major hurdle for networking researchers to neatly implement their research results in an efficient manner, and empirically assess the algorithm/protocol performance.

In this project, we take a bottom-up approach, and tackle issues with the better definition and characterization of wireless links and their implications for higher-layer protocol design and optimization. We would like to (i) understand how, and to what extent, wireless links are affected by PHY/MAC attributes and other environmental factors, (ii) characterize the behavior of wireless links in such a way that they become amenable to rigorous analysis and reasoning, and (iii) identify control knobs in the MAC/PHY layers with which the network capacity can be optimized. To make such a study with synergistic measurement, characterization, design components, we work with Champaign-Urbana Wireless Mesh Network (CUWiN), substantially extend/strengthen its operational software infrastructure, and lay a transparent device driver on top of firmware. The device driver includes several functional modules that enable dynamic tuning of control knobs to improve network capacity, and exports PHY/MAC attributes through well-defined APIs to facilitate cross-layer design and optimization.

Research Agenda (click here for details)

The project is composed of closely-related research activities carried out in several synergistic R&D steps: profiling (based on real-life measurements) and understanding predominating factors that affect the behaviors of wireless links, identifying control knobs and devising their corresponding control mechanisms based on a rigorous, analytical foundation, their validation and assessment with software system building and experimentation, and their deployment in a city-wide, operational network (and wide dissemination to the CISE community). The project also lays the software infrastructure for building a practical and high-performance wireless mesh network whose channel and system-wide behavior can be reasoned and predicted with accurate models. Building such a software infrastructure enables researchers to (in-)validate their research results through a tight, synergistic loop of measurement, analysis/modeling, and designed experiments for empirical evaluation.

Specifically, we are conducting research through a synergistic measurement-design-experimentation loop along the following closely-related R&D thrusts:

• (T1) Better characterization of wireless links and its representation in virtual coordinates.
• (T2) Capacity improvement through power control, carrier sense threshold tuning, data rate adaptation, and temporal/spatial diversity.
• (T3) Design and development of modular, transparent device driver.
• (T4) Improving administration, management, and monitoring capabilities of CUWiN.

• Jihyuk Choi (Ph.D. pre-candidate)
• Chunyu Hu (Ph.D. 2006, supported in part by Motorola Center for Communications Fellowship)
• Yan Gao (Ph.D. pre-candidate)
• Tae-Seok Kim (Postdoc 2005-2007, supported in part by Korean Research Foundation)
• Lu-Chuan Kung (Ph.D. pre-candidate)
• Ray Lam (Ph.D. pre-candidate, supported in part by R C Lee Centenary Scholarship)
• Hyuk Lim {Postdoc 2003-2006)
• Ting-Yu Lim (Postdoc 2005-2006, supported in part by Taiwan Ministry of Education Postdoctoral Fellowship)
• Kyung-Joon Park (Postdoc 2006-2008, supported in part by Korean Research Foundation)
• Yong Yang (Ph.D. pre-candidate, supported in part by Vodafone Graduate Fellowship)

Major Publications

Funding Source

NSF Network Technology and Systems Program, 2006-2009
NSF Computing Research Infrastructure Program, 2007-2010

Related Links

• Bay Area Wireless User Group
• Champaign Urbana Wireless Mesh Networks
• Microsoft Self-organizing Neighborhood Wireless Mesh Networks
• Mit RoofNet
• Seattle Wireless
• SFlan
• Southampton Open Wireless Network
• Technology for All Wireless
• Wireless Leiden
• Wireless Open-access Research Platform
  

Detailed Description of Research Agenda

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

As shown in Figure 1, the delivery ratio has little correlation with the distance, and the distance between two wireless nodes is no longer the definitive characterization of a wireless link. One question that arises is then what would be a better link characterization (or how to characterizes the neighbor abstraction) and whether or not one can still represent the network topology a coordinate system.

Figure 1: 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.

Different candidate attributes have been proposed to characterize the neighbor abstraction for different purposes. To determine the best route metrics for the purpose of routing, the RTT, the packet loss rate, the expected transmission time (ETX), and the weighted cumulative expected transmission time (WCETT) have been proposed to characterize the link/path quality. To determine the level of interference between nodes, the \emph{received signal strength (RSS)} has been proposed. 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 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 signals. Let's use the RSS measurement as an example.

Let M(n) denote the set of nodes that can directly communicate with n and n itself. Then, the RSS measurements between n and nodes in M(n) can be written in an p x p square matrix S = [s_ij] for , where s_ij is the (-RSS) measurement made in dBm by the i th node to j th node, s_ii = 0, and p = | M(n) | is the number of nodes. The columns of S can be considered as the coordinates of the corresponding nodes in a p-dimension space. There are, however, three issues to be considered: (i) the dimension p may be large; (ii) these coordinates are likely to be correlated with each other, and hence it becomes difficult to identify components that play an important role; and (iii) the coordinate system has to be properly augmented to include nodes that cannot directly communicate with node n.

To tackle these research issues, we construct, with principal component analysis (PCA), a virtual coordinate system that represents the neighbor abstraction with a smaller dimension. Figure 2 gives an example of applying PCA for two correlated variables, x₁ and x₂: with the use of PCA, we obtain two principal components, pc₁ and pc₂. The first principal component pc₁ represents the direction of the maximum variance. The one-dimensional linear representation is calculated by projecting the original data onto pc₁.

Figure 2: Example of the principal component analysis

We also use singular value decomposition (SVD) to determine principal components. Specifically, the SVD of S is obtained by , where U and V are column and row orthogonal matrices, , and 's are the singular values of S in the decreasing order (i.e., if i < j). Note that S^TS = (UWV^T)^T (UWV^T) = V(W^TW)V^T. This means that the eigenvectors of S^TS make up V with the associated (real nonnegative) eigenvalues of the diagonal of W^TW. Similarly, SS^T = U^T(WW^T)U. The columns of the p x p matrix U = [u₁, ..., u_p] are the principal components and the orthogonal basis of the new subspace. By using the first q columns of U denoted by U_q, we project the p-dimensional space into a new q-dimensional space:

where c_i is the new coordinate of the i th node, and s_i is the i th column vector of S.

After the coordinates of nodes in M(n) are determined, we need to further determine the coordinate of a node k that cannot directly communicate with n but can via node(s) in M(n). Conceptually, this can be done with the use of RSS measurements made between node k and relay nodes that can directly communicate with node n. For example, if , we may obtain the coordinate of k, x_k, by minimizing the objective function: . In some sense, construction of the virtual coordinate system proceeds in a ring-by-ring manner, starting from the innermost ring composed of nodes in M and proceeding outward.

We believe the coordinate system thus constructed can be used essentially in the same manner as the physical Euclidean coordinate system is used to analyze the wireline network. For example, we can select appropriate attributes that best account for the link/path quality and construct a global, virtual coordinate system in which the distance between two mesh nodes approximately represents the measured path quality. The virtual coordinate system can then be used as the underlying "topology" for unicast/multicast routing. In this case, a node computes its distance to gateway nodes in the virtual coordinate system, and selects the one with the smallest "distance." For another example, if the set of RSS measurements is used to characterize the neighbor abstraction, the virtual coordinate system constructed will capture the level of interference between nodes -- if two nodes are close to each other in the coordinate system, their transmissions will likely interfere with each other.

(T2) Capacity improvement through power control, carrier sense threshold tuning, data rate adaptation, and temporal/spatial diversity.

There are several control knobs that one can explore to control the sharing range of the wireless medium (and ultimately the degree of spatial reuse): the transmit power and carrier sense threshold each node uses, the spatio-temporal domain in which a node transmits, and the channel on which a node transmits. (Note that the carrier sense threshold specifies the received signal strength above which a node determines that the medium is busy and will not attempt for transmission.) While several researchers have explored the use of multi-radios and multi-channels to improve network capacity, the first three control knobs have not been explored. Both the transmit power and carrier sense threshold ultimately determine how many connections can simultaneously take place without significant interference, while the third control knob takes advantage of the spatial and temporal diversity to mitigate the adverse effect of interference. In this part of the project, we have carried out the following research activities:

Relationship between the transmit power, the carrier sense threshold, and the data rate

The importance of spatial reuse in wireless ad-hoc networks has been long recognized as a key to improving the network capacity. One can increase the level of spatial reuse by either reducing the transmit power or increasing the carrier sense threshold (thereby reducing the carrier sense range). On the other hand, as the transmit power decreases or the carrier sense threshold increases, the SINR decreases as a result of the smaller received signal or the increased interference level. Consequently, the data rate sustained by each transmission may decrease. This leads naturally to the following questions: (1) How can the trade-off between the increased level of spatial reuse and the decreased data rate each node can sustain (because of the decrease in the SINR) be quantified? In other words, is there an optimal range of transmit power/carrier sense threshold in which the network capacity is maximized? (2) What is the relation between the transmit power and the carrier sense threshold? Does increasing the transmit power have the same effect of increasing the carrier sense threshold?

We have attempted to answer the above questions in an analytical framework. Specifically,

(1) We have derived an analytical model that expresses the network capacity as a function of the transmit power P_tx and the carrier sense threshold T_cs, under the assumptions that the network is densely populated (so as to consider the worst-case interference scenario) and wireless nodes are uniformly and independently distributed in a region U:

where and are constants, and W is the channel bandwidth in hertz. Note that for ease of analysis, the Shannon capacity under the Additive White Gaussian Noise (AWGN) channel model is used to characterize the relation between the channel rate and the SINR.

As shown in Figure 3, spatial reuse depends only on the ratio of P_tx to T_cs. This implies that to improve the network capacity one can tune one parameter, while fixing the other at an appropriate value.

Figure 3: Existence of optimal carrier sense range

(2) While the analytical model assumes that the achievable channel rate is a continuous function of SINR (with the use of the Shannon capacity), there are only a number of data rates available in reality. Ideally given the SINR, a wireless node chooses the maximal data rate that can be sustained. We show that, under the case of a discrete number of channel rates, tuning the transmit power offers several advantages that tuning the carrier sense threshold cannot offer, provided that there is a sufficient number of power levels available. (The interested reader is referred to [4] for a detailed account.) We also analyze the number of power levels required to achieve the same control granularity as afforded by tuning the carrier sense threshold, and show a number of 5 power levels is sufficient.

(3) We have modeled the channel activities governed by IEEE 802.11 DCF in multi-hop wireless networks by extending Bianchi's and Kumar's models. In a multi-hop wireless network, it is difficult to obtain a consistent view for the entire network -- a node may detect the channel to be busy while another node senses the channel to be idle. As a result, we model the channel activities from the perspective of an individual sender, and categorize them as perceived by each sender into four types: idle, busy, collision and successful transmission. The effect of accumulated interference is also faithfully incorporated in the model. We obtain the throughput attained by each sender by deriving the probability that each activity occurs and its expected duration. Based on the analytical model derived, we have been able to identify a simple operating condition under which the network may attain the system throughput that is close to its optimal value (and based on which a distributed algorithm can be readily designed). Specifically, we find that high system throughput can be achieved when the area, SL_s, silenced by a sender s is reduced as much as possible under the premise that SL_s covers the interference area IN_r of its intended receiver r (Figure 4). This increases spatial reuse while not deteriorating collisions due to the hidden node problem.

Figure 4: An illustration of the desirable operational condition

(4) Based on the above findings, we devise a localized power and rate control algorithm, called PRC, that enables each transmitter to adapt to the interference level that it perceives and determines its transmit power and data rate [2]. The transmit power is so determined that the transmitter can sustain the highest possible data rate, while keeping the adverse interference effect on the other neighboring concurrent transmissions minimal. As shown in Figure 5, as compared to existing CST tuning algorithms, PRC gives higher network capacity (Figure 5 (a)). The better performance results from the fact that PRC uses a lower transmit power (Figure 5 (b)), which in turn induces lower interference, enables better spatial reuse, and achieves higher data rates.

Figure 5: Simulation results on random topology when the number of transmission pairs varies from 3 to 160

(T3) Design and development of modular, transparent device driver.

As mentioned above, the traditional notion of a link is no longer well-defined in wireless environments, because characteristics of wireless links are now determined by several PHY/MAC control knobs and environmental factors. This implies that in order to optimize network performance, PHY/MAC attributes should be exported to higher layer protocols in order to enable cross layer design and optimization, to promote spatial reuse through tuning of PHY/MAC parameters, and to allow implementation of new MAC functions other than those provided by IEEE 802.11. In particular, because new MAC functions may be in conflict with existing ones that have been implemented in the firmware of most IEEE 802.11 interface cards, there should be mechanisms for disabling selected MAC functionalities in the firmware and/or setting various parameters that are originally controlled by the firmware.

To deal with all the aforementioned issues, we have designed and implemented a transparent device driver (TDD) layer situated above the (proprietary) CUWin device firmware. We leverage the Atheros chipset, and the open-source Madwifi driver in Linux and similar device drivers in NetBSD. Although commodity 802.11 interfaces typically partition the MAC functionalities between hardware/firmware on the card and the software driver running in the kernel, the Atheros chipset does not require the loading of firmware. The chipset instead relies on a Hardware Access Layer (HAL) module provided in the binary form only. The HAL module operates between the hardware and the device driver to manage many of the chip-specific operations and to enforce required FCC regulations. It is similar to firmware, in that it prevents users from setting invalid operating parameters, but implements fewer 802.11 functionalities than other firmware. More desirably, it provides an interface for changing various device parameters, including the minimum and maximum contention windows.

Architecture and Major Components:

Figure 6 shows the architecture of the TDD. Different from the traditional layered approach, an extension-enabled device driver exports PHY/MAC parameters and events to higher-layer protocol modules. There are four major components in the TDD:

• (1) Extension-enabled device driver: The device driver has been extended to export a set of PHY/MAC attributes and events in the form of extension specification. The specification serves as a service agreement between the device driver and a higher-layer protocol module that uses it. To implements an extension, a device driver implements the get/set handlers of the PHY/MAC parameter(s). It also define events, provide the event information to the uniform extension manager, and notify the manager upon occurrence of events.
• (2) Cross-layer control module: A cross-layer control module implements a cross-layer design/optimization algorithm. As a client to the uniform extension manager, it registers itself with the uniform extension manager in order to use the facilities provided by the extension-enabled device driver. Through a generic interface, a control module can read and write PHY/MAC parameters exported by the driver. Also, it can subscribe to events of interest defined in an extension specification and provide the corresponding callback functions.
• (3) Uniform extension manager: The uniform extension manager is the major component of the TDD. Conceptually, the uniform extension manager is responsible for (i) loading and unloading extensions, (ii) providing an API for cross-layer control modules to register events of interest and callback functions; (iii) allowing control modules to set/get PHY/MAC parameters via handlers registered by extensions; (iv) maintaining event definition and subscription, and (v) dispatching events to subscribing control modules.
• (4) Kernel mode proxy: For user-space programs to gain access to the TDD in the kernel, we introduce a kernel mode proxy that serves as a ``bridge'' between the two entities. Each uniform extension function exported is assigned an unique system call number. The kernel mode proxy is responsible for translating a TDD-related system call and invoking the corresponding uniform extension function, and (ii) delivering events to the handler in the user space.

Figure 6: The architecture of the Uniform Extension Framework

Internals of Uniform Extension Manager

Figure 7 shows the internals of the uniform extension manager and the data path in the event delivery mechanism. Table 1 lists the APIs exported by the uniform extension manager. An extension interface registers (unregisters) itself with the extension manager via RegisterExtInterface() (UnregisterExtInterface()). It also registers (unregisters) its set/get handlers with the extension manager via RegisterSetHandler() (UnregisterSetHandler()). A cross-layer module finds whether or not an extension interface exists via FindExtension(). It can also set/get the value of certain PHY/MAC parameters exported by an extension interface via GetExtParam() and SetExtParam(). The uniform extension manager maintains (i) the definition record of all the supported events in an event definition tree; and (ii) the list of subscribers of each event. An extension interface generates and delivers an event to the uniform extension manager (and subsequently cross-layer control modules that are interested in the event) by calling TriggerEvent(). A cross-layer control module (un-)subscribes to an event with a callback function by calling AddEventHandler() (RemoveEventHandler()).

Figure 7: Uniform Extension Manager and Event Delivery

Table 1: The APIs Defined in the Uniform Extension Manager

Depending on the type of events, there are two possible paths for delivering an event to the manager. A synchronous event is an event for which the device driver requires feedback from its subscribers. When a synchronous event is triggered, it is delivered by the dispatcher (in the uniform extension manager) immediately and the device driver that triggers the event waits until all the subscriber handlers are finished. An example of a synchronous event is a transmit query, in which prior to the transmission of a frame, the device driver may query the cross-layer control modules for recommendations on the transmit power, the channel on which the frame will be transmitted, or the data rate at which the frame will be transmitted. This facilitates realization of, for example, per-packet power control. Synchronous events make it possible for cross-layer control modules to make decisions upon occurrence of certain events. An asynchronous event, on the other hand, is a notification message sent by the device driver to the subscriber(s) of that event. Upon reception of an asynchronous event, the event trigger inserts the event into the event queue and wakes up the dispatcher. The dispatcher then delivers the event to the corresponding callback functions.

In principle, one can design any type of extension interfaces that export PHY/MAC attributes and events of interest in the TDD framework. The interested reader is referred to [13] for a detailed account. For demonstration purposes, we list PHY/MAC parameters exported in our wireless extension (grouped into per-device, per-neighbor, and per-packet categories) in Table 2. Note that for the benefit of space, only the set commands (but not the get commands) are shown. Note also that several of the per-device parameters are related to network configuration and thus can also be set by ifconfig via ioctl() calls.

Table 2

Features of the TDD

The TDD has the following salient features:

1. Controlled transparency: The TDD provides a transparent and generic interface for higher-layer protocol modules to access, through well-defined APIs, a rich set of PHY/MAC attributes and functionalities in the device driver. Specifically, the following PHY/MAC attributes are available: (i) the transmit power level, (ii) the carrier sense threshold, (iii) the data rate, (iv) the receive signal strength index (RSSI), and (v) the channel used to transmit a frame/upon which a frame is received, and (v) the time instant at which a frame is scheduled for transmission/receive. Through an event subscription mechanism, higher-layer protocol modules can also receive timely update of channel status, without directly inserting callback functions in various places of the device driver.
2. Flexibility: The design philosophy of the TDD (and at heart the uniform extension manager) is to provide minimum but crucial functionalities that enable implementation of complicated cross-layer design/control algorithms. The event subscription mechanism is simple, elegant, and allows multiple higher-layer protocol modules to subscribe, and be alerted of, PHY/MAC events of interest. They can also register with the event subscription mechanism their callback functions, allowing adequate actions to be taken upon event occurrence. Moreover, the TDD allows the time granularity at which PHY/MAC properties are controlled to be on a per-packet or per-connection basis, or permanently (i.e., until the property is reset).
3. Easy Integration and Portability: Existing upper-layer protocol modules (e.g., routing daemons) can be extended to subscribe events of interest (e.g., frame reception status upon frame arrival), and figure in the information in their decision making. Through dynamic module loading and extension registration, an upper-layer protocol can realize cross-layer optimization if an extension has been implemented, and it falls back to the normal operation if the required extension is not supported by the TDD. This ensures portability.

(T4) Improving administration, management, and monitoring capabilities of CUWiN.

We are in the phase of improving the network administration, monitoring, and management capabilities of CUWiN, by managing use of the testbed (e.g., user accounts, experiment schedules, and data output packages), providing technical support for testbed users, employing an automatic module distribution and upgrade mechanism, and designing configuration/monitoring tools to facilitate network maintenance and experimentation. In particular, we are designing and deploying a network monitor composed of local node engines and a remote monitoring/management engine (located on the Internet). Information will be collected across the protocol stack at the local node engines and sent to the remote monitoring engine. The latter then displays information for all specified nodes on a web interface. The APIs exposed by the transparent device driver will be used to collect PHY/MAC attributes by local node engines to facilitates measurement and monitoring. We are also developing a web-based CUWiN monitor GUI that allows viewing of the current network status (in terms of current network topology & connectivity and various link qualities), problem history, and log file (/var/log/daemon, /var/log/messages).

Access to the CUWiN testbed will come in two stages based on conformation (by the CUWiN staff) of the stability of applications to be experimented. Initially, a researcher is allocated to a management and development server through which the researcher can gain access (through secure shells) to a group of in-door CUWiN nodes. Application(s) will be built first in this native CUWiN environment. After the application(s) are stabilized, the researcher will be assigned (upon request and availability of wireless resources) access to his/her requested number of nodes on the outdoor UIUC/Purdue campus testbeds. Using a customized push-based upgrade script provided by CUWiN, researchers will be able to easily apply customized software to their assigned nodes.

Figure 8: The current node distribution in CUWiN