Title :
Minimum number of neighbors for fully connected uniform ad hoc wireless networks
Author :
Ferrari, Gianluigi ; Tonguz, Ozan K.
Author_Institution :
Dept. of Electr. & Comput. Eng., Carnegie Mellon Univ., Pittsburgh, PA, USA
Abstract :
Determining the minimum number of neighboring nodes required to guarantee full connectivity, i.e., to ensure that a node can reach, through multiple hops, any other node in the network, is an important problem in ad hoc wireless networks. In this paper, we consider reservation-based wireless networks with stationary and uniform (on average) node spatial distribution. Assuming that any communication route is a sequence of minimum length hops, we show that, in an ideal case without inter-node interference (INI) and on the basis of a suitable definition of transmission range, the minimum number of neighbors required for full connectivity is, on average, π. Full connectivity is guaranteed if the transmitted power (in the case of fixed node spatial density) or, equivalently, the node spatial density (in the case of fixed transmitted power) are larger than critical minimum values. In a realistic case with INI, we prove that there are situations where full connectivity cannot be guaranteed, regardless of the number of neighbors or the transmitted power.
Keywords :
ad hoc networks; telecommunication network routing; critical minimum values; full connectivity; minimum length hops; multiple hops; node spatial density; node spatial distribution; reservation-based wireless networks; transmitted power; uniform adhoc wireless networks; Binary phase shift keying; Computer networks; Electronic mail; Graph theory; Interference; Network topology; Peer to peer computing; Spread spectrum communication; Throughput; Wireless networks;
Conference_Titel :
Communications, 2004 IEEE International Conference on
Print_ISBN :
0-7803-8533-0
DOI :
10.1109/ICC.2004.1313365