Analysis of k-connectivity

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.


One of the research fields which have gained more attention by the scientific community in the last few years is that of self-organizing large-scale wireless networks, variously referred to as multihop, ad hoc or packet radio networks. Slightly aside, a growing interest is deferred to wireless sensor networks, which, while presenting peculiar features, possess at the same time many of the characteristics of ad hoc networks. According to this networks the cellular and mobile devices communicate with one another in peer to peer fashion they don't need any base station or any other existing network. Two devices which are far from each other cannot establish a link with each other so they act as a relay to transfer data from source to destination. By this, each device acts as a node of network and mobile terminal. The fact that multi hop networks can be established "on the fly" gave them the name "ad hoc networks." This kind of communication is useful to establish spontaneous networks among mobile computers sensor networks for environmental monitoring and car networks for telematics applications. One of the issues of more concern, for such networks, is that of limiting achievable performance, in terms of capacity, connectivity, delay and coverage. Most of the published works still rely on a simplistic model of channel propagation, where the randomness inherently present in radio communications is not considered. During the last couple of years, however, a growing interest has risen on investigation of channel randomness impact on limiting achievable performance of random networks. . In cellular system a mobile device is connected if it has a wireless link to one or other base station, this situation is more complicated in wireless multi hop network, each every single node in mobile device contribute to the entire network. Connectivity among devices depends on characteristics of wireless channel, apatial density and transmission and reception capability. In this work characterize the K-connectivity probability in the presence of shadow fading.

The wireless channel is characterized by:

  • Path loss (including shadowing)
  • Multipath delay spread
  • Fading characteristics
  • Doppler spread
  • Co-channel and adjacent channel interference

Wireless communications

In wireless communication systems the multi hop networks are formed by group of nodes that communicate with each other over a wireless channel. They operate in a decentralized and self-organizing manner and do not rely on fixed network infrastructure. Each and every node can act as a router to forward traffic to its destination point. In 1970s this was the fundamental idea of such packet radio networks, then in recent years there is tremendous increase in the research field.

The great advantage of mobile wireless multihop networks is that they can be formed in fast and spontaneous way, for this they are called as "ad hoc networks". There are several applications based on ad hoc communication such as mobile computers for conferences home networking, wireless sensor networks and network of the vehicles these are the recent developments in this field of wireless ad hoc networks. So it had a impact in the field of technology and sciences.

Well the progress has been made in the development of protocols (e.g., routing, medium access) which takes into account of the unique characteristics of ad hoc networks. But the development has been less in the field to investigate ad hoc networks in analytical manner and to find a convenient and exact mathematical description for modeling.

In wireless communication systems the very fundamental and important property is connectivity.

Whereas in wireless networks with fixed infrastructure (e.g., cellular telecommunication networks or wireless LANs), it is sufficient that each mobile node has a wireless link to at least one base station, the situation in a decentralized ad hoc network is more complicated.

There must be a wireless multihop path from each mobile node to each other mobile node in order to achieve a fully connected ad hoc network. Mainly the connectivity depends on the node density i.e.., number of nodes per unit area and their radio transmission range.

Each and every single node will contribute to the connectivity of the entire network.

The correct adjustment of the nodes' radio transmission 80 power is therefore an important system feature. As in cellular networks, power adjustment can reduce interference while maintaining a certain Quality of Service.

In ad hoc networks, it also allows the controlling of the topology of the network. If we increase the transmission power of a node; it will typically achieve a higher transmission range and therefore reach more other nodes via a direct link.

On the other hand, if we make the transmission power of a node very low, the node may become isolated without any link to other nodes.


Radio waves propagate from a transmitting antenna, and travel through free space they undergo reflection, refraction, absorption and diffraction. These radio waves are greatly affected by the atmosphere the ground terrain and the y get deflected due to some obstacles like buildings, trees, hills bridges etc..,. The received signal feature is based on the multiple physical phenomena.

According to mobile and cellular communication systems the height of the mobile is smaller than the surrounding structures. So the signal which is transmitted lost its line of sight path when it reaches to the receiver end. Thus, the existence of a direct or line-of-sight path between the transmitter and the receiver is not comparable.

In such cases the propagation of the wave is due to reflection and scattering from the surrounding or buildings and by diffraction over and/or around them.

The transmitted signal will be arriving at the receiver end via several paths with different time delays causing multipath.

The signal at the receiver end with multiple waves with different randomly distributed phase and amplitudes they combine to give a resultant signal according to time and space.

The receiver at different points which are only short distance from each other will have different signal as output because this is due to phase differences and relationship of the incoming radio waves. This causes significant fluctuations in the signal amplitude. Thus obtaining of different results at different points of the receivers causing fluctuations. This phenomenon of random fluctuations in the received signal level is termed as fading. Carrier modulated telecommunication signal which is propagated through certain media will undergo deviation or attenuation is defined as fading. The fading mainly varies with time, geographical position such as building, trees, bridges etc.., and radio frequencies so this is often modeled as random process. The fading channel is experienced in fading as a communication channel. This fading in wireless communications systems is due to multipath propagation referred to as multipath induced fading or some obstacles affecting the path of wave. The wave will not propagate properly it has to face the obstacles causing shadowing. The shadowing of the signal results in the signal loss and the receiver will not get the exact output form according to the transmitted signal. So fading results in the loss of the wave signal.

The environment surroundings have different reflectors due to this the transmitter and receiver create multiple paths that a transmitted signal can traverse. So the receiver output will have the superposition of the signal of transmitted wavelength which will have different paths. The signal will have experience in attenuation, delay and phase shift while travelling from transmitter (source) to receiver (destination). So the signal can result in constructive or destruction interference, attenuating or amplifying the signal power at the receiver. If the destructive signal is strong then it is referred as deep fade and which result in the temporarily failure. This temporary failure of the communication is due to severe drop in the signal to noise ratio(S/N ratio) of channel.

Fading refers to the time variation of the received signal power caused by changes in the transmission medium or path

Fading Types

  • This fading types have both slow and fast aspects.
  • Receives signal has different special variations based on narrowband excitation.
    • Fast Fading
    • Slow Fading
    • Range Dependence

    Fading Types

  • Fast fading is by the quick fluctuations in the signal over small areas.
  • Signal when it is moving from all the directions in the plane then fast fading can be observed in the motion of the waves.

    A rapid fluctuation takes place when there is response in the variation of the signal when it meets some obstacles in its way. In this case the fast fading will be observed due to the signal fluctuation by environmental changes.

    This middle scale over which the signal varies, which is on the order of the buildings dimensions is known as shadow fading, slow fading or log-normal fading. Slow Fading: The slow fading is caused when the mobile movements is met with the obstacles which are in the propagation of the signal in the environment.

    Ex: Shadowing or Large-Scale fading

    Fast Fading: This fading occurs with the small movements of a mobile.

    Ex: Multipath fading or Small-Scale

    There are two types of fading based on multipath time delay spread:

    In Flat fading where the bandwidth of the signal is less than the coherence bandwidth of the channel or the delay spread is less than the symbol period. Frequency selective fading, where the bandwidth of the signal is greater than the coherence bandwidth of the channel or the delay spread is greater than the symbol period.

    There are two types of fading based on Doppler spread:

    • Fast fading, which has a high Doppler spread, and the coherence time is less than the symbol period, and the channel variations are faster than baseband signal variations.
    • Slow fading, which has a low Doppler spread. The coherence time is greater than the symbol period and the channel variations are slower than the baseband signal variations

    Example for multiple path fading is when we stop at a traffic signal lights if we are hearing to FM then suddenly the signal becomes weak and then we cannot hear. So after we move some meter distance we will have the signal completely. This is due to vehicle stopping at a place where there is severe destructive interference. This may happens in the case of mobile phones.

    Fading channel models are often used to model the effects of electromagnetic transmission of information over the air in cellular networks and broadcast communication. Fading channel models are also used in underwater acoustic communications to model the distortion caused by the water. This fading is modeled as time varying random change in phase and amplitude of the transmitted signal as mathematically. This attenuation may vary medium to medium.

    Ad hoc networks

    Power: Radio transmission power is an important feature in the adjustment of the nodes. The power adjustment will reduce interference and it will maintain the quality of service this is in cellular networks. Whereas it controls the topology of the network in ad hoc networks. In ad hoc Networks, if the transmission power is high we can get higher transmission range and more and more connection of the nodes can be made. If we don't have enough transmission power then the node will be isolate without any link.

    Connectivity constraints: If there is a path between two nodes then the network is said to be connected. The network should have bi-connections, if one link breaks the other link should be there to keep the network communicate. These bi-connected topologies are responsible for the survival of the links between the individual nodes.

    The basic problem in ad hoc wireless sensor networks is that what happens if node is isolated or the connected network. In that case we can achieve the resources that

    • whether ad hoc network has at least n neighbours (n = 1)
    • an ad hoc network that will still be connected if any k - 1 nodes fail

    The special features of wireless ad hoc networks are

    • Energy conservation: In case of wired networks the units in ad hoc networks are provided with limited energy.

    so this limited energy should be used as efficiently as possible that the main and primary goal.

    Efficiency of energy is more important in the field of wireless sensor networks. Because replacing the sensor batteries in wireless sensor networks is not practical.

    If the energy in the network is conserved by some techniques at different levels of the wireless architecture by this preservation of the energy the lifetime of the individual units and the network can be furthered useful considerably.

    • Limited bandwidth: These wireless multi hop networks are characterized by limited bandwidth which is available to the nodes.
    • Unstructured and time-varying network topology: In wireless multi hop networks the nodes are arbitrarily placed in the deployment region .So the graph which we plot between the nodes will have usually unstructured.

    Based upon the node mobility and failure the network topology will be varying with time.

    • Low-quality communications: In wireless communication the data transfer will be more in compared to wired networks. The communication will be more dependent in wireless than wired networks. This quality of service is more influenced by the environmental factors, they are time varying. In bad environmental conditions the communication will be low and this affects the quality of service.
    • operation in hostile environments: These wireless sensor networks will be operated in hostile environment .Sensors in the networks should be designed explicitly to work under this extreme environment conditions, with may make individual unit failure a likely event.
    • data processing: because of the low energy and poor communication the data which is sensed must be compressed before sending them to the other neighboring nodes.
    • scalability: The sensors in the wireless sensor networks are made of thousands of sensors. So the sensor protocol should be stabilized, this is an important issue in the case of wireless networks.

    Lognormal shadow fading

    There has been many studies over multi path routing and the capacity in wireless ad hoc networks in which connectivity of the nodes is a fundamental property. Where as in k-connectivity the design must ensure the purpose of route diversity in multi hop networks and it should give the perfect quality of service and the reliability of data communication. The designer should practically implement whether the design is satisfying quality of service and reliability Now a day's connectivity problem is lot in the field of ad hoc and sensor networks. However, most existing work relies on a simplistic channel propagation model with the assumption that two nodes are connected if and only if their distance is less than a deterministic transmission radius. Path loss, shadowing and fading of multi path are the severe problem in the field of propagation of the signals. By this kind of problem the communication range cannot be implemented. It is better to reasonable to study the k-connectivity which deals with the channel impairment characteristics. This k- connectivity analyzes the connectivity of multi-hop radio networks in a log-normal shadowing environment and gives the tight lower bound for the minimum nodes density that is necessary to obtain an almost surely connected network. It also derives the probability of outcome of the shadowing. This k-connectivity investigates the isolation of probability of the disconnected cluster of nodes. Thereby coverage and the connectivity probability can be achieved by considering the shadowing and fading. All these are only for 1-connectivity (k=1). No one knows when k>1 connectivity. Recently the transmission range for minimal can be derived by k- connected network for a given density. In this they only consider the channel model (simplistic) and they will ignore the several channel impairments.

    Without having the channel characteristics that has direct bearing on the link connectivity, it is not complete. By capturing the channel impairments we have to develop a generic mathematical model in order to account realistic channel model then we will present an analytical procedure for k- connectivity computation in case of ad hoc network in presence of lognormal shadowing. By this argue that shadowing increases the successful probability of links of the nodes and there by k-connectivity. In Poisson point of view the nodes are distributed accordingly, so we have the probability that there are at least k-neighbors for each node in the network and we can get the probability of k-connectivity of the entire network. So the designer should have each and every idea that how a network should be connected and the probability of the entire should be known according the nodes present in the network.

    Connectivity Network

    In k-connectivity we have the graphs based on the applications in network reliability and network design problem.

    In this case, let's consider the set of vertices of nodes as V and set of edges of links as E. connected by edges E. So graph G can be expressed as

               G = (V,E)

    So all the points of nodes which are the vertices of nodes and the links which are connected between the nodes is edges.

    Consider two vertices v1 and v2 of a network, they are said to be connected if there is a path with the start vertex of v1 and end at v2. So there exist a path between two nodes then G is called connected. A graph that is not connected is called disconnected.

    K-connectivity means:

    • We can remove at most (k-1) vertices then also network is said to be connected. The network is said to be disconnected when k-vertices are removed.
    • There are at least k vertex-disjoints paths connecting between any node vi and vj that have no elements in common. Path are said to be edge disjoint if they have no edge in common.

    These are equivalent by MENGER's theorem.

    Thus, a k-connected wireless network can sustain the failure of k - 1 nodes. A graph is called k-edge connected if for each pair of vertices, there are k mutually edge disjoints paths connecting them.

    Related work

    In the literature, several studies have investigated 1-connectivity issue in multi-hop networks. The study in analyzes the connectivity in a log-normal shadowing environment and presents the tight lower bound of the minimum nodes density to obtain an almost surely connected network. Work in develops the connectivity by considering shadowing and fading simultaneously. The study in derives the minimal transmission range that can ascertain an almost surely K-connected network for a given density .The author investigates the probability distribution of the minimal number of nodes between a randomly-selected source and destination node, without considering the effect of fading, and assume that the radio range of all nodes is equal and fixed. An extensive literature survey showed that the impact of fading with superimposed shadowing on the K-connectivity of adhoc networks has not been addressed before in the literature. In this work, we develop an analytical model and formulate the K-connectivity with a generic channel model by taking into account both the large-scale lognormal shadowing.

    K-connectivity probability computation

    We assume that the nodes in an adhoc network are randomly distributed according to a homogeneous Poisson point process and let be the expected number of nodes per unit square. Let be two-dimensional stationary Poisson point process over.

    The numbers of nodes in disjoint (non-overlapping) areas are independent random variables. Given is an ad hoc network with nodes, and a homogeneous node densitynodes per unit area. The probability that each node has at least K neighbors is given by

    Where X is the mean of Poisson distribution and n is the total number of sensor nodes.

    Analytical evaluation of K-connectivity Probability

    In this section analytical expressions are derived for K-connectivity probability of a wireless adhoc network in the presence of shadow fading

    Lognormal shadow fading channel

    In this section, we will analyze the formula for K-connectivity probability taking into account of lognormal shadow fading channel.

    We assume the following:

    1. Attenuation with distance and shadow fading.
    2. The shadow fade attenuations between all pairs of source and destination nodes are i.i.d. log-normal.
    3. The shadow fade attenuation between any two nodes i and j is log-normally distributed and is the same regardless of which node is the transmitter and which the receiver.
    4. Node i has a connection to another node j if and only if the received power exceeds

    K-connectivity Probability Computation

    In this system we provide the numerical results corresponding to K-connectivity obtained from the analytical model using MATLB.


    1. C. Bettstetter and C. Hartmann, "Connectivity of wireless multihop networks in a shadow fading environment," Wireless Networks, vol. 11, no.5, pp. 571-579, May 2005.
    2. Daniele Miorandi, Eitan Altman, and Giuseppa Alfano, "The Impact of Channel Randomness on Coverage and Connectivity of Ad Hoc and Sensor Networks," IEEE Trans. on Wireless Communications, Vol. 7, no.3, March 2008.
    3. C. Bettstter, On the minimum node degree and connectivity of a wireless multihop network, ACM Proc. of MobiHoc, Jun. 2002.
    4. Irina Voarisoa Ramanandraitsiory on K-connectivity for Wireless Sensor Networks, 22 may 2008
    5. Christian Bettstetter "the Minimum Node Degree and Connectivity of a Wireless Multihop Network".
    6. B. M. Leiner, D. L. Nielson, and F. A. Tobagi, eds., Proceedings of the IEEE, Special issue on Packet Radio Networks, vol. 75, Jan. 1987.
    7. C. E. Perkins, ed., Ad Hoc Networking. Addison-Wesley, 2001.
    8. Z. J. Haas, M. Gerla, D. B. Johnson, C. E. Perkins, M. B. Pursley, M. Steenstrup, and C.-K. Toh, eds.,IEEE Journal on Sel. Areas in Comm., Special issue on Wireless Ad Hoc Networks, vol. 17, Aug. 1999.
    9. Paolo Santi. Topology control in wireless ad hoc and sensor network. pages ACM, 2005.
    10. James P.G Sterbenz and et al. Survivable mobile wireless network: Issues, challenges, and research directions. 2002.
    11. C. Bettstetter, "Mobility modeling in wireless networks: Categorization, smooth movement, and border effects," ACM Mobile Computing and Communications Review, vol. 5, no. 3, 2001.


    The analysis of k-connectivity in channel randomness makes the connectivity of nodes by using sensors to communicate with each other and to transfer the information . Spanning graph to see whether the k-vertex is connected. In k-connectivity, if value of k=1 the problem is same as to find the minimum connectivity and obtain a spanning tree. For 1-connectivity the system may fail when at least two vertices are not connected then the entire network is said to be disconnected network.

    In this k-connectivity we compute the k-vertex disjoint path between original sensors. We don't calculate that in case of added sensors.

    In case of 2-connetivity the graph is of 2- connected network, so that entire network has 2-vertex disjoints from vertex to vertex. In 2- connectivity disjoint paths between the original and additional or original nodes are more complicated. This is also more complicated in case of k>2. We discussed diverse applications of fault-tolerant in wireless sensor networks. In ad-hoc network, we discussed the topology control with minimizing the power assigned to each node and respect to k-connectivity. There are many applications in survivability, topology control, and the node placement.