Introduction:
Smartphones and smartpads are everywhere. They connect people together and let people surf the Internet anywhere anytime via wireless access points. Research on wireless communication is therefore timely and important. In this project, we consider a special kind of wireless networks – wireless ad-hoc networks (WAHNs). They are so called because they do not have a pre-defined infrastructure (like cellular base stations or WIFI access points). Instead, the wireless devices have to "discover" each other in a peer-to-peer fashion and then they can communicate. The study of WAHNs is meaningful because building an infrastructure can be expensive or impossible in emergency situations. Figure 1 gives a WAHN example composed by smartphones and laptops. Since a WAHN does not have commanding centralized processor, it has to rely on distributed algorithms.
Figure 1: A wireless ad-hoc network (WAHN) example: (1) no centralized administration; (2) nodes have limited transmission range; and (3) nodes act as routers.
Research Problems:
Problem 1 – Sorting in WAHNs. Sorting is one of the most fundamental tasks in computer science. Surprisingly, little is known about sorting in wireless networks, let alone WAHNs. In this problem, each processor (node) stores an item, and each node wants to know the rank of its own item in the sorted list of all the items. An illustrating example for Problem 1 is shown in Figure 2. A naive method to solve this problem is to let a selected node (called sink) collect all the items from all the other nodes and then apply one of the classical sorting algorithms. Unfortunately, this method incurs lots of message transmissions which consume energy. Since the nodes near the sink will deplete their energy significantly faster than the nodes farther away, the network might soon become disconnected.
Figure 2: An illustrating example for distributed sorting in WAHN: (1) the item under each node means its stored value; and (2) each node wants to know its rank in the sorted list of all the items.
Problem 2 – Multi-Message Broadcasting in WAHNs. Multi-message broadcast is a fundamental communication primitive in networks, which is to disseminate k pieces of information stored in k arbitrary nodes to the entire network (with n nodes) with the fewest timeslots. Figure 3 shows an example for this problem (k=2). The multi-message broadcast problem generalizes two well-known problems – broadcast (k = 1) and gossip (k = n). Previous work mostly assumed a radio network model which is overly simplified. We would like to design efficient distributed algorithms with good approximation ratios (i.e., the number of timeslots used is not too much worse than the optimal) while adopting a network model that is closer to the reality.
Figure 3: An illustrating example for multi-message broadcasting: the laptop and the smartphone need to disseminate their stored items (10, 18) to the entire network.
Design Issues:
Interference: Most of the previous work only considered interference from neighbors and ignored the accumulation effect of wireless interference. In our project, we assume instead the SINR (Signal-to-Interference-plus-Noise Ratio) model which takes into account all the cumulative interferences from simultaneously transmitting nodes, far and near. This leads to a big challenge in the design because nodes in a WAHN have only "local" knowledge about the network (they do not know the topology, nor even the number of their neighbors) whereas the SINR model imposes a global constraint.
Power Control: In radio transmissions, the power used attenuates with the distance. Increasing a sender’s power improves the receipt of the message by a designated node but at the same time causes more interference to other receivers.
Scheduling: Simultaneous transmissions are unavoidable. By some smart scheduling, it is possible to allow all or many of them to complete successfully. One intuitive idea is to let nodes that are sufficiently far away from each other talk or talk first, while keeping those that are close by in silence.
The above issues are inter-dependent to a certain degree, so they must be jointly considered when designing efficient distributed algorithms to solve the sorting and the multi-message broadcasting problem in WAHNs.
Our Results So Far:
(1) If we only need to output either the maximum or the minimum value, we have designed a distributed algorithm for the wireless sorting problem under the SINR interference model.
(2) If we restrict to the local broadcasting problem in which each node needs only to broadcast a message to its neighbors, we have designed both randomized and deterministic distributed algorithms with worst-case performance guarantees.
(3) For the (Δ+1)-coloring problem, which is to color all the nodes that are separated by some pre-defined distance with at most (Δ+1) colors, we have designed randomized distributed algorithms with worst-case performance guarantees.
Publications:
(1) H. Li, Q.-S. Hua, C. Wu, and F.C.M. Lau. Latency-Minimizing Data Aggregation in Wireless Sensor Networks under Physical Interference Model. Ad Hoc Networks, to appear.
(2) H. Li, Q.-S. Hua, C. Wu, and F.C.M. Lau. Minimum-Latency Aggregation Scheduling in Wireless Sensor Networks under Physical Interference Model. In Proc. MSWiM, 2010.
(3) D. Yu, Y. Wang, Q.-S. Hua, and F.C.M. Lau. Distributed (Δ+1)-Coloring in the Physical Model. In Proc. ALGOSENSORS, 2011 (to appear also in Theoretical Computer Science).
(4) D. Yu, Y. Wang, Q.-S. Hua, and F.C.M. Lau. Distributed Local Broadcasting Algorithms in the Physical Interference Model. In Proc. DCOSS, 2011.
Grant Support:
Distributed Data Queries in Wireless Sensor Networks under the Physical Interference Model (HK GRF, 9/2011, $454,130).
People:
F.C.M. Lau, C. Wu, Q.-S. Hua (Tsinghua & HKU), Y. Wang (Tsinghua), H. Li, and D. Yu