Statement of Research

Liang Zhao

My research and publications are focused on topology control for mobile ad hoc networks (MANETs). In this statement of research, I first give a little background on topology control, followed by a statement of research requirements. Then I briefly describe my research and results achieved to date, along with a description of my current work.

A Little Background:

An ad hoc network consists of a collection of nodes equipped with transceivers. In an ad hoc network, where nodes are deployed without any wired infrastructure and communicate via multi-hop wireless links, the network topology is autonomously formed based on the nodes’ locations and transmission ranges. The nodes communicate through wireless links, with each node acting as a relay when necessary to allow multi-hop communications. In a mobile ad hoc network (MANET), every node may move and the nodes still can communicate with each other at any time throughout the movement.

The performance of the network can be impacted in a major way by the network topology. A dense topology may induce high interference, which, in turn, reduces the effective network capacity due to limited spatial reuse and may cause unnecessarily high energy consumption. In contrast, a sparse topology is vulnerable to network partitioning due to node or link failures. Topology control for ad hoc networks aims to maintain a specified topology, such as requiring that the network be connected. The desired effect of topology control is to reduce energy consumption, reduce MAC layer interference between adjacent nodes, and to increase the effective network capacity.

I study topology control as a problem of assigning power levels to the nodes of an ad hoc network so as to maintain a prespecified network topology while minimizing energy consumption. That is, either minimizing the maximum transmission power used by any node (MinMax), or minimizing the total (i.e. average) transmission power used by the nodes (MinTotal).

Motivated by the significant impact of topology control for an ad hoc network, intrigued by the beauty of the underpinning graph problems, and as required by the U.S. Army Research Laboratory under Collaborative Technology Alliance Program, my research involves both theoretical and experimental work on solving topology control problems.

Research Requirements:

The goal of my research is to meet some of the following research requirements excerpted from the program proposal of the Collaborative Technology Alliance in communications and networking by the U.S. Army Research Laboratory:

• Abstractions, models, mathematical frameworks, and tools to discover, describe, analyze, predict and control the behavior of complex dynamic communication networks. Development of appropriate metrics and establishment of fundamental information-theoretic limits of multi-hop ad hoc networks.
• Architectures and scalable protocols to enable auto-configuration of complex, adaptive network-of-networks with guarantees on performance; and models and tools for the formal study and analysis of such protocols.
• Energy-efficient protocol design for sensor networks.

My primary research interests and challenges come from topology control for mobility. When node movement is involved, every theoretical problem on topology control is open.

Research and Results Achieved To Date:

Many previous studies focused on solving topology control problems. Among them, centralized algorithms were typically proven to have specific bounds of their goodness relative to optimal, while distributed algorithms usually established their goodness using simulations.

My major research effort is devoted to theoretical work on topology control for mobile ad hoc networks. I established four standard mobile network models and specified four groups of topology control problems under these mobility models. The goal is to find the minimum power uniformly assigned to all nodes such that the resulting topology achieves a particular graph property – monotone property (such as connected). My research is trying to find, if there exist, polynomial time optimal algorithms for each group of mobility problems. This is a very challenging topic and has not previously been studied by any researchers. When moving nodes are allowed, earlier work simply re-runs the heuristics (for maintaining network connected) periodically, maintains the network connectivity by on-line algorithms, or simply let each node adjust its power level by monitoring its link qualities. Although those heuristics do work in practice to maintain network connectivity, none of them could achieve any optimality when nodes are moving. I solved the mobility problems by using either optimization or approximation algorithms/frameworks in polynomial time. Hence, although tons of papers studied topology control in MANETs, my study is a corner stone ever since the topology control problem was first proposed. Specifically, my theoretical contributions are:

• A basic framework for solving the topology control problems for all monotone properties in simple mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n⁴ log n).
• A faster framework improved upon the basic framework for all monotone properties in simple mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n³ log n).
• A fastest framework for local monotone properties in simple mobile networks. (Note that “connected network” is a local monotone property.) When the local monotone property is specified as “connected network”, the resulting algorithm runs in time O(n² log n).
• A framework for solving the decision version of topology control problems for all monotone properties in simple mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n²).
• A framework for solving the topology control problems for all monotone properties in constant rate mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n⁴ log² n).
• A framework for solving the decision version of topology control problems for all monotone properties in constant rate mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n² log² n).
• A framework for approximately solving the topology control problems for all monotone properties in disk mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n² log n).
• A polynomial time framework for approximately solving the topology control problems for all monotone properties in general mobile networks. When the monotone property is specified as “connected network”, the resulting algorithm runs in time O(n³ log n).
• A framework for optimally solving the topology control problems for all monotone properties in general mobile networks. If the framework halts, it produces the optimal solution. Unfortunately, it may run for ever (i.e. cannot find the optimal solution) in the worst cases. We are proving this problem is unsolvable, its counterpart decision problem is undecidable, and its simplest case is NP-hard.

In addition to the theoretical work on topology control, I also studied experimental work through simulations. My experimental study is mainly related to the CLTC (i.e. Cluster based Topology Control) framework and the distributed topology control algorithms. The CLTC framework is a hybrid of centralized and distributed algorithms for solving topology control problems. It utilizes any clustering algorithm to compute the transmission power levels assigned to the nodes in an ad hoc network. Hence, the performance of CLTC is determined by the clustering algorithms working in conjunction with it. I studied the impact of clustering algorithms on the performance of CLTC, and compared the performance of CLTC with that of existing distributed topology control algorithms. In contrast to my theoretical work, distributed topology control algorithms may be utilized in practice to achieve certain topology properties, though none of them can be used in mobile networks. I applied my disk mobile network model to adapt existing distributed algorithms for static networks to mobile networks, and I conducted an amount of quantitative research to measure the performances of CLTC with clustering algorithms and distributed topology control algorithms.

Ongoing Work:

Our current work is examining a general mobile network. Distinguished from the other standard mobility models, the general mobile network model assumes that every node in the network moves on a straight line segment. Associated with each moving node are its starting and ending positions on its line segment. Nothing is assumed about the rate at which nodes are moving. The goal is to minimize the maximum power uniformly assigned to any node such that the network is connected at any time throughout the movement. We believe this problem is unsolvable, its counterpart decision problem is undecidable, and its simplest case is NP-hard. My current work is writing the formal proofs of unsolvability and NP-hardness. The main structures of the proofs are constructed, but there are still a few confusions needed to be straightened out. The algorithms, which I proposed to solve the topology control problems under the general mobile network model, can produce reasonable (not optimal) solutions. Further, I found an algorithm which produces the optimal solutions if it halts. However, it may run for ever (i.e. cannot find the optimal solution) in the worst cases.