Random Network Model [27]

Given Cluster head that form a dominant independent set in the network graph [64] [65] .

Provides Network connectivity with very high probability [66] .

Results are of theoretical interest and cannot be apply to real scenarios

Spatial Poisson Process and Percolation theory [28]

Considers mobile stations that are confirmed to a single dimensional line. At a particular instant in time it is assumed that stations spatial positions can be modeled as a one dimensional Poisson process.

Node’s broadcast message percolate, if the nodes are randomly distributed according to homogeneous Poisson point process on an infinitely large area

Work did not consider the actual distance between nodes.

Packet radio network model [29]

Ÿ Nodes in the network lie in bounded area.

Ÿ The homogeneous Poisson assumption.

Ÿ Each node is able to communicate with any other node that is at most R unit distance from it.

Ÿ All nodes generate Poisson streams of traffic at an identical rate.

No optimal number of nearest neighbor or magic number can exist.

Difficult to apply in real scenario. Also in disk based models, fading, interference and attenuation does not considerer.

Connectivity of radio networks [30]

Ÿ Transmitters are distributed according to one dimensional Poisson process of density d.

Ÿ Two transmitters are connected by an edge apart at most i distance of their communication range.

Solve s the problem of [29] in 1-dim. Studies uniform distributed nodes on 1-dim line segment and estimates critical transmitting range for Poisson distributed nodes

Difficult to be apply in real scenario, only the expected number of deployed nodes can be controlled

Critical power for asymptotic connectivity in wireless networks [31]

Nodes placed randomly in disc of unit area.

Estimates the critical power of a node, needed to transmit to ensure that the network connectivity.

Not applicable for real applications.

Connectivity in ad hoc and hybrid networks [33]

Ÿ Assumes a large scale wireless network with low density of nodes per unit area.

Ÿ Power constraints are modeled by a maximum distance above which two nodes are not directly connected.

Base stations significantly help in increasing the network connectivity only for large density

Findings restricted only to one dimensional case.

Number of neighbors needed for connectivity of wireless networks [34]

Ÿ In a network with n randomly placed nodes each node should be connected to Ө (log n) neighbors.

Ÿ N nodes are placed uniformly and independently in unit square region.

Ÿ Critical constant appear to be close to 1.

Ÿ Increasing number of nodes should not effect the number of nearest neighbor otherwise once obtained a disconnected network

Ÿ Asymptotic connectivity results when every node is connected to its nearest 5.1774logn neighbors, while asymptotic disconnectivity results when each node is connected to less then 0.074logn nearest neighbors.

Result is of theoretical interest and cannot be applicable to real scenario

Approximation algorithms and Connectivity Augmentation Problem [35]

Network is treated as undirected graph [67] and each possible link is either feasible or infeasible.

Determines a set of edges of minimum weight to be inserted so that so that the resulting graph is λ-vertex (edge) connected. The problem is NP hard for λ > 1

Does not consider the possibility of adding new vertices into the graph

A probabilistic analysis for the radio range assignment problem in ad hoc networks [37]

N nodes having same transmission range are distributed in d-dimensional region.

Estimates bounds for isolated nodes and connected nodes on a one dimensional line segment.

It is only for static networks. It does not incorporate the possibility of transient or permanent node failures in their model. That will lead to requirements for desirable topological characteristic to be harsher compared to theoretical prediction