Optimal link constructions of network topology design using partitioning method in Ad Hoc environments

Reu-Ching Chen a,¤

Wei-Tsong Lee b

Jim-Min Lin a

a. Department of Information Engineering

Feng-Chia University

Taichung, Taiwan 407

R.O.C.

b. Department of Electrical Engineering

Tam-Kang University

Taipei, Taiwan 251

R.O.C.

Abstract

The performance guarantee aspects of ad hoc networks have attracted considerable interest. In networks of this type, establishing a network topology that may minimize the total number of link connections is a fundamental concern. Optimizing the network performance requires an accurate knowledge of the current network topology. Accordingly, the present study proposes a generic approach for estimating the prevailing system topology in ad hoc environments. Since in real ad hoc environments, the network topology pattern varies dynamically as individual nodes enter and leave the network, then, it is evenly impossible to keep the instant network topology information. However, the generic estimation approach presented in this study enables the dominant network topology to be determined. A fundamental contribution of the present study is based on using the system state transition probability to establish the dominant network topology. In our study, the associated link costs can be easily estimated when the network topology is determined. The proposed generic approach is more efficient than techniques in which the topology pattern is unknown. Furthermore, the approach can be widely applied to the topology design of modern ad hoc networks.

Keywords : Cluster, Ad hoc, link cost, bipartite graph, topology.