On the k-Connectivity of Ad-Hoc Wireless Networks

In this paper, we consider k-connectivity problem which is one of the fundamental problems in the ad-hoc wireless network. Here we assume that the nodes are uniformly distributed on a unit square area [0, 1]². We define a random graph on unit square [0, 1]² and derive the critical range for transmission radius r_n to achieving k-connectivity of a randomly generated network in almost sure sense. We prove that if r_n is defined as r_n² := ¹/_nr (c log n + (k-1)log₂ n - logΓ(k)), where k, c>0 are constants and n be the number of node in the network, then for c>2 the network is a k-connected network in almost sure sense. Also we derive that for c>2 and critical transmission range C_n = √(^{clog n}/_nr) the network is connected.