An Approach Based on Random Graph Theory

We believe a multi-cluster, multi-hop packet radio network architecture for wireless system should be able to dynamically adapt itself with the changing network configurations. Due to the dynamic nature of the mobile nodes, the association and dissociation to and from clusters perturb the stability of the system and th reconfiguration of the system is unavoidable. Choosing clusterheads optimally, which act as the mobile base station, is an important issue since the clusterheads decide the topology of the network and are responsible for resource allocation. Frequent clusterhead changes adversely affect the performance of other protocols such as scheduling and resource allocation that rely on it. Most of the existing algorithms for choosing clusterheads, are greedy heuristics which do not include all the relevant optimization criteria into account.

We propose a graph theoretic approach and show how this problem can be tackled with the concepts of random graphs. Although, most related graph algorithms are NP-hard, it can be shown that with certain realistic assumptions the run time can be made polynomial. We propose to find an analytical model and validate that model by performing exhaustive simulations. The parameters of our model will be node-mobility, node-degree, and transmission range.

Routing is another critical component in any multi-hop wireless network. Traditional routing protocols and single hop protocols are not suitable for multi-hop mobile wireless networks since there is no fixed home agents to maintain routing information. Due to the mobility of the hosts and the limitations of the wireless channels, the problem of routing is complex. Inefficient routing protocols will degrade the throughput of channel access and increase the overhead as the number of hosts increase.

In addition to the conventional, cellular based applications, a number of new applications have evolved recently, which require wireless multi-hopping between remote users, without relying on the fixed wired network. These applications have stricter requirements than ordinary voice applications and hence, need to specify their expectations from the system as a whole. The applications show no degradation as long as they are in the wired domain. The issue of interfacing the wired network to the wireless one demands more stringent guarantees when the wireless section is multi-hop. One must guarantee the quality of service (QoS) not only over a single hop but over an entire wireless multi-hop path. The key component to such provisioning is QoS routing, which requires QoS information at each source to be propagated to the intermediate nodes. To address the issue of QoS routing, we propose to solve the following problems.

People

• Damla Turgut
• Mainak Chatterjee