Many researchers have adopted a cross-layer approach to solving wireless network problems. However, there have been arguments for and against cross-delay design in wireless networks. A fundamental problem in cross-layer design is the tradeoff between efficiency and modularity. In cross-layer control solutions, although the performance of the system can be optimized, the tight interaction between the layers could make the overall system highly sensitive to changes in each layer. A main objective of our work is to understand whether we can design cross-layer control solutions that only require a loose coupling between the layers. By loose coupling, we mean that the cross-layer solution should be robust to imperfect information or imperfect actions taken at various layers. If this is true, we then have the best of both worlds, i.e, we achieve both efficiency and modularity.
We have demonstrated this kind of loose coupling in certain cross-layer control problems. In particular, we have formulated and solved a cross-layer control problem that jointly allocates the end-to-end data rate to each user (i.e., the congestion-control problem) and computes the schedule and power/rate assignment for each link (which we will referred to as the scheduling problem). In the optimal solution, the congestion-control component and the scheduling component can be decomposed: they both act independently on the queue lengths of the system. The two components are then coupled by the update of the queue length at each link. Further, if one replaces the scheduling component by an imperfect scheduling policy that only computes suboptimal schedules at each time, we can still quantify the impact on the overall system performance fairly easily for a large class of imperfect scheduling policies.
It is usually preferable that the control algorithms can be implemented in a distributed fashion. This is particularly important for ad hoc and sensor networks. However, distributed algorithms add complexity to the cross-layer design. The reason is that distributed algorithms are unlikely to achieve optimality, hence the interaction between the layers become much harder to predict and control. Nonetheless, our work on cross-layer control with loose coupling provides us with some hope because it indicates that these imperfect distributed algorithms may still suffice. In fact, for certain simple interference models, we have already obtained fully distributed algorithms for cross-layer congestion-control and scheduling problems.
Our future work will extend this loose-coupling concept to other classes of cross-layer control problems. Some of the on-going directions that we are pursuing include: incorporating the routing layer into the cross-layer control framework; studying the interaction with MAC layers that use random access; studying the interaction with coding and modulation schemes at the physical layer; and dealing with delay sensitive applications.
Selected publications:
In a wireless cross-layer control problem, often the link scheduling component is the main source of computational complexity. This is because the scheduling problem is combinatorial and non-convex in nature (it determines whether to turn on/off each link). Although the optimal centralized scheduling algorithm has been well-known by the work of Tassiulas and Ephremides, its complexity often grows exponentially with the size of the network. In addition, for wireless ad hoc networks it is usually more preferable that the control algorithms can be implemented in a distributed fashion. A main emphasis of my work is to develop low-complexity and distributed scheduling algorithms for wireless ad hoc networks that can achieve provable performance bounds. We showed for the first time in the literature that the simple maximal matching algorithm can achieve at least a half of the optimal capacity in wireless ad hoc networks under suitable interference models. We also developed the first constant-time distributed scheduling algorithms whose computational complexity does not grow with the size of the network, and we developed the first provably-efficient and distributed channel-assignment and scheduling algorithms for multi-channel multi-radio wireless networks. In our INFOCOM 2008 paper, we developed much sharper techniques for characterizing the performance bounds of an important class of low-complexity scheduling algorithms called Greedy Maximal Scheduling. (This paper won the Best Paper Award in IEEE INFOCOM 2008.) In many of the above papers, we also demonstrated how these distributed scheduling algorithms can interact with other network components to achieve provable efficiency for the overall system. These results significantly improve our understanding of how to design practical distributed solutions for wireless ad hoc networks.
Selected publications: