Analysis Of K Connectivity Computer Science Essay

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.

This project work investigates K-connectivity characteristics of a wireless multihop network. K-connectivity refers to the property that a random node has at least k neighbors. The K-connectivity topology attributes depend on the spatial distribution of the nodes and their transmission range. We derive expression for the K-connectivity in the presence of channel impairments. We also conduct investigation into the effect of path loss exponent, lognormal shadowing and the spatial density on the K-connectivity is conducted. The numerical and simulation results are beneficial for the practical design of adhoc networks and give insight into the selection of various parameters required to achieve a fully connected network in the presence of channel impairments.


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. In such networks, the mobile devices communicate with each other in a peer-to-peer fashion without the need for base stations or any other pre-existing network infrastructure. If two devices cannot establish a direct wireless link-because they are too far away from each other-devices in between act as relays to forward the data from the source to the destination. In other words, each device acts as both a mobile terminal and a node of the network. The fact that multihop networks can be established "on the fly" gave them the name "ad hoc networks." This communication paradigm is especially 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. While a mobile device in a cellular system is "connected" if it has a wireless link to at least one base station, the situation in a wireless multihop network is more complicated, since each single mobile device contributes to the connectivity of the entire network. In fact, the level of connectivity among devices depends on their spatial density, transmission and reception capabilities, and the characteristics of the wireless channel. 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 multihop networks are formed by a 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 node can act as a router to forward traffic toward its

destination. While the fundamental idea of such packet radio networks goes back to at least the 1970s [1], recent years have shown a tremendous comeback of research in this area (see, e.g., [2,

3, 4]). A great advantage of mobile wireless multihop systems is that they can be formed in a spontaneous and fast way; this is why they are called "ad hoc networks." Several application scenarios, such as ad hoc communication between mobile computers for conferencing and home networking, wireless sensor networks [5], multihop extensions of cellular telecommunication systems [6], and networks of vehicles [7, 8] are in the minds of researchers and developers.

Good progress has been made in the development of protocols (e.g., routing, medium access) that take the unique characteristics of ad hoc networks into account, but less work has been done to investigate ad hoc networks in an analytical manner and to find a convenient and exact mathematical description for modeling. In this paper, we address the latter two issues.

We investigate a very fundamental and important property of wireless multihop networks, namely their 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. To achieve a fully connected ad hoc network, there must be a wireless multihop path from each mobile node to each other mobile node. The connectivity therefore depends on the number of nodes per unit area (node density) and their radio transmission range. Each single mobile node contributes 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 [9, 10]. 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.

In this context, this paper addresses the following questions: For a given number of nodes n per area A, what is the minimum radio transmission range r0 required to achieve

• an ad hoc network in which no node is isolated?

• a fully connected ad hoc network, i.e., a network in

which each node can reach each other node via a wireless multihop path?

This range assignment problem arises, for example, if we want to set the system parameters for network-level simulations of ad hoc networks. We investigate this question analytically and by simulation under typical modeling assumptions, namely a random uniform node distribution with

n nodes on a system area A and a simple channel model in which each node has the same transmission range r0. An equivalent problem must be solved in the system design of wireless multihop networks. For example, a large- scale sensor network should cover a certain area A to perform environmental monitoring. The used sensor type can transmit a range r0 in the given environment (e.g., free space). How many sensors of this type do we need to obtain a connected network (see also [11])?

In addition to the basic problems "no isolated node" and "connected network," we also consider a network design that is robust against node and link outages. That is, how can we achieve with minimized resources

• an ad hoc network in which each node has at least n0 neighbors (n0 ≥ 1)?

• an ad hoc network that will still be connected if any k − 1 nodes fail (k-connected network)?

Before we present the solutions to these problems, Section 2 describes the used network model in more detail, and Section 3 recalls some basic definitions of graph theory and introduces the terms used in this paper. The main contributions of this paper are presented in Sections 4 and 5.

In Section 4, we derive an expression for the probability that each node in the network has at least n0 neighbors (n0 = 0, 1, 2 . . .). For given parameters (n, ρ) we can state how to set the range r0 to achieve, with a certain probability p, a network with no isolated node. We also investigate these questions by simulations and thereby verify our analytical expressions. To solve the problem of a connected network (Section 5), we model an ad hoc network as a so-called geometric random graph. A recently published theorem in this mathematical research field allows us to make some interesting statements about the probability that a homogeneous ad hoc network is connected or even k-connected. Most important, we can calculate the range r0 and density ρ that is required to obtain an almost surely k-connected network. Again, we perform simulations for k = 1, 2, and 3. Section 6 discusses the impact of mobility on our results, and Section 7 outlines related articles and compares them to our contributions. Finally, Section 8 concludes this paper.


Radio waves propagate from a transmitting antenna, and travel through free space

Undergoing absorption, reflection, refraction, diffraction, and scattering. They are greatly

affected by the ground terrain, the atmosphere, and the objects in their path, like buildings,

bridges, hills, trees, etc. These multiple physical phenomena are responsible for most of the

characteristic features of the received signal.


In most of the mobile or cellular systems, the height of the mobile antenna may be

smaller than the surrounding structures. Thus, the existence of a direct or line-of-sight path

between the transmitter and the receiver is highly unlikely. In such a case, propagation is mainly

due to reflection and scattering from the buildings and by diffraction over and/or around them.

So, in practice, the transmitted signal arrives at the receiver via several paths with different time

delays creating a multipath situation as in Fig.1.

At the receiver, these multipath waves with randomly distributed amplitudes and phases

combine to give a resultant signal that fluctuates in time and space. Therefore, a receiver at one

location may have a signal that is much different from the signal at another location, only a short

distance away, because of the change in the phase relationship among the incoming radio waves.

This causes significant fluctuations in the signal amplitude. This phenomenon of random fluctuations in the received signal level is termed as fading.

Slow versus fast fading

The terms slow and fast fading refer to the rate at which the magnitude and phase change imposed by the channel on the signal changes. The coherence time is a measure of the minimum time required for the magnitude change of the channel to become uncorrelated from its previous value.

Slow fading arises when the coherence time of the channel is large relative to the delay constraint of the channel. In this regime, the amplitude and phase change imposed by the channel can be considered roughly constant over the period of use. Slow fading can be caused by events such as shadowing, where a large obstruction such as a hill or large building obscures the main signal path between the transmitter and the receiver. The amplitude change caused by shadowing is often modeled using a log-normal distribution with a standard deviation according to the log-distance path loss model.

Fast fading occurs when the coherence time of the channel is small relative to the delay constraint of the channel. In this regime, the amplitude and phase change imposed by the channel varies considerably over the period of use.

In a fast-fading channel, the transmitter may take advantage of the variations in the channel conditions using time diversity to help increase robustness of the communication to a temporary deep fade. Although a deep fade may temporarily erase some of the information transmitted, use of an error-correcting code coupled with successfully transmitted bits during other time instances (interleaving) can allow for the erased bits to be recovered. In a slow-fading channel, it is not possible to use time diversity because the transmitter sees only a single realization of the channel within its delay constraint. A deep fade therefore lasts the entire duration of transmission and cannot be mitigated using coding.

The coherence time of the channel is related to a quantity known as the Doppler spread of the channel. When a user (or reflectors in its environment) is moving, the user's velocity causes a shift in the frequency of the signal transmitted along each signal path. This phenomenon is known as the Doppler shift. Signals travelling along different paths can have different Doppler shifts, corresponding to different rates of change in phase. The difference in Doppler shifts between different signal components contributing to a single fading channel tap is known as the Doppler spread. Channels with a large Doppler spread have signal components that are each changing independently in phase over time. Since fading depends on whether signal components add constructively or destructively, such channels have a very short coherence time

Flat versus frequency-selective fading

As the carrier frequency of a signal is varied, the magnitude of the change in amplitude will vary. The coherence bandwidth measures the separation in frequency after which two signals will experience uncorrelated fading.

In flat fading, the coherence bandwidth of the channel is larger than the bandwidth of the signal. Therefore, all frequency components of the signal will experience the same magnitude of fading.

In frequency-selective fading, the coherence bandwidth of the channel is smaller than the bandwidth of the signal. Different frequency components of the signal therefore experience de correlated fading.

Fading (or fading channels) refers to mathematical models for the distortion that a carrier-modulated telecommunication signal experiences over certain propagation media. Short-term fading, also known as multipath induced fading, is due to multipath propagation. Fading results from the superposition of transmitted signals that have experienced differences in attenuation, delay and phase shift while travelling from the source to the receiver. It may also be caused by attenuation of a single signal.

The most common types of fading, known as "slow fading" and "fast fading", as they apply to a mobile radio environment, are explained below.

Beforehand, it might be necessary to remind ourselves of a definition of fading:

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

Slow Fading: Shadowing or Large-Scale fading is a kind of fading caused by larger movements of a mobile or obstructions within the propagation environment.

Fast Fading: Multipath fading or Small-Scale fading is a kind of fading occurring with small movements of a mobile.

For example, consider the common experience of stopping at traffic lights and hearing a lot of static on your FM broadcast radio, which is immediately corrected if you move less than a metre. Cellular phones also exhibit similar momentary fades. The reason for these losses of signal is the destructive interference that multiple reflected copies of the signal makes with itself. To understand how a signal can destructively interfere with itself, consider the sum of two sinusoidal waveforms (which are similar to modulated carrier signals) with different phases.

The best way to combat fading is to ensure that multiple versions of the same signal are transmitted, received, and coherently combined. This is usually termed diversity, and is sometimes acquired through multiple antennas. Mathematically, the simplest model for the fading phenomenon is multiplication of the signal waveform with a time-dependent coefficient which is often modeled as a random variable, making the received signal-to-noiseratio a random quantity.

Fading channel models are often used to model electromagnetic transmission of information over wireless media such as with cellular phones, and in broadcast communications. However, even for underwater acoustic communications the notion of fading is useful in understanding the distortion caused by the medium.

Small-scale fading is usually divided into fading based on multipath time delay spread and that based on Doppler spread.

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

*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.

In addition to the small scale fading that is described above, for which the change in the signal strength occurs, for mobile phone frequencies, on the order of a fraction of a meter, the signal can also undergo shadow fading, or shadowing. This is due to the presence of obstacles between the transmitter and the receiver, and the scale of distance required to experience shadowing is about an order of magnitude larger than that of multipath fading.


Shadowing is the effect that the received signal power fluctuates due to objects obstructing the propagation path between transmitter and receiver. These fluctuations are experienced on local-mean powers, that is, short-term averages to remove fluctuations due to multipath fading.

Propagation is a crucial factor in the design and performance of wireless systems. There are several statistical methods to estimate propagation under different conditions, and most

of these methods are computationally intensive. 2D and 3D ray tracing methods, for example, are popular techniques with much effort devoted to enhance their computational viability

(see [2,7 and references therein]). Inaccuracies in modeling specific aspects of propagation, such as shadow fading, could lead to distorted capacity and performance estimates in simulations and approximate analytical calculations. Shadow-fading is the slowly varying component of

propagation that arises, as the name suggests, primarily from obstacles. Rayleigh fading, which is a propagation variation on a smaller scale, is also an important factor for stationary or

slow moving users of the wireless system, but we do not deal with it here.

For some applications, it is useful to have a statistical model of propagation with an empirical validity for the conditions of interest. It is in this spirit that the log-normal distribution, which is most widely used at the present, was proposed. In this model, the received power at each location

is assumed to be independent of other locations and lognormally distributed about a deterministic large-scale decay,

i.e.,P(r) = P0(r) es , (1)

where s is normally distributed with mean 0 and log P0(r) is the average value of log P(r) received at distance r from the transmitter after large-scale fading. Usual forms for this function

are P0(r) = A + B log(r) (the Hata model [5]) or simply the power law decay P0(r) = K/rd, where A, B, K and d are specific constants depending on the environment. While these models are simple and account for the observed marginal distributions, they fail to capture the spatial correlations inherent in shadow-fading, which cause its slowly-varying behavior. Simulations of wireless systems that ignore such spatial correlations could give seriouslymisleading results, as we illustrate below with an example of a call drop rate calculation. Our interest in generating realistic shadow-fading patterns arose in the context of a simulation study of a novel Interference-Based Dynamic Channel Assignment algorithm [1]. The proposed algorithm relies on periodic interference measurements on the inactive frequencies so as to

identify appropriate candidate channels. To obtain accurate estimates of the impact on system capacity and voice quality, we were confronted with the problem of generating shadowfading

values consistent with specified marginal distributions and correlation parameters. The issue of capturing correlations in shadow-fading has been addressed previously by Gudmundson [3,4] by means of an auto-regressive model that approaches the issue differently. The correlations considered there are between the shadow-fading values seen by a mobile as it moves in the

environment. In simulations, this would imply independent random processes for each mobile admitted to the network. Thus, one encounters anomalies such as the assignment of

completely different shadow-fading values for different mobiles at nearby locations or at different times at the same location. In this work, we take Gudmundson's empirical observations

about the marginal distribution and correlation structure as valid. We hence do not present any additional experimental data or measurements. Instead, we focus on the observation that the data obtained from measurements may be better fit by a 2-dimensional model, rather than the 1-dimensional one proposed by Gudmundson. One possible effect in a 2-dimensional model that may not be observed in a 1-dimensional model is increased call dropping in the former due

to mobiles that move randomly within shadowed regions for longer periods than the latter. We expand on this effect further in our numerical studies. Our approach is to precompute a static, spatially correlated shadow-fading pattern with the desired statistical characteristics.

The mobiles then acquire fading values as they move within the domain of the map, thus avoiding the inconsistencies mentioned above. The method is analytically tractable and computationally efficient. It is well suited for simulations that are aimed at obtaining performance characteristics not directly related to specific propagation aspects, but would benefit from using realistic fading models for generic environments. Finally, we describe a simulation experiment designed to study the effect of correlations on call dropping, an important performance criterion for wireless networks. The experiment adopts a simple random walk mobility model for mobiles moving within a pattern produced using our fading model

Related work

In the literature, several studies have investigated 1-connectivity issue in multi-hop networks. The study in [1] 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 [2] develops the connectivity by considering shadowing and fading simultaneously. The study in [3] 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.

In wireless communications, fading is deviation or the attenuation that a carrier-modulated telecommunication signal experiences over certain propagation media. The fading may vary with time, geographical position and/or radio frequency, and is often modeled as a random process. A fading channel is a communication channel that experiences fading. In wireless systems, fading may either be due to multipath propagation, referred to as multipath induced fading, or due to shadowing from obstacles affecting the wave propagation, sometimes referred to as shadow fading.

The presence of reflectors in the environment surrounding a transmitter and receiver create multiple paths that a transmitted signal can traverse. As a result, the receiver sees the superposition of multiple copies of the transmitted signal, each traversing a different path. Each signal copy will experience differences in attenuation, delay and phase shift while travelling from the source to the receiver. This can result in either constructive or destructive interference, amplifying or attenuating the signal power seen at the receiver. Strong destructive interference is frequently referred to as a deep fade and may result in temporary failure of communication due to a severe drop in the channel signal-to-noise ratio.

A common example of multipath fading is the experience of stopping at a traffic light and hearing an FM broadcast degenerate into static, while the signal is re-acquired if the vehicle moves only a fraction of a meter. The loss of the broadcast is caused by the vehicle stopping at a point where the signal experienced severe destructive interference. Cellular phones can also exhibit similar momentary fades.

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. Mathematically, fading is usually modeled as a time-varying random change in the amplitude and phase of the transmitted signal. Attenuation may vary in medium to medium.

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 [16].


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. Thus we have

Where is same for all i,j.

4. Node i has a connection to another node j if and only if the received power exceeds

Some given threshold. i.e., if and only if

Where is the distance-loss exponent, is the shadow fade between nodes i and j, r is the distance between the nodes, K is a constant. We have the probability density function (pdf) of the distance r between a transmitter-receiver pair,


The probability that there is a direct connection between these nodes is given by



The above equation (49) can be solved as follows


We have


From equation (50) and (51) we can write


Let be the random variable representing the number of nodes with which the node at (0, 0) has a direct connection. Then we may write the probability mass function of as follows:


Take m= k-n the above equation (53) will becomes


The above equation can be solved as follows


From equation (9) and (55) we can compute K-connectivity probability as follows


6.2. K-connectivity Probability Computation

In this system we provide the numerical results corresponding to K-connectivity obtained from the analytical model using MATLB. The system parameters are selected as follows: k=10dB, =1 mwatt, W=0.01 mwatt, =1 watt. The parameter are assumed as variable taking values in specific ranges.

Figure -1 corresponds to the variation of K-connectivity probability (K=3) with node density lambda for different value of sigma in lognormal shadowing channel. The plot shows that by increasing node density and sigma, K-connectivity probability will increase. The minimum node density required to achieve K-connectivity can be obtained from result.

Figure -2 corresponds to the variation of K-connectivity probability (K=3) with standard deviation sigma for different value of alpha in lognormal shadowing channel. The plot shows that larger alpha has negative influence on K-connectivity while larger value of sigma will always improve the connectivity.