Notes - The Connectivity: What is missing?

For the connectivity of wireless ad hoc network, we have the following results:

1. In 1D, we used the following techniques to obtain the results (from less accurate to exact result).

a) Isolated node: Analyse the probability of the existence of an isolated node.
b) Occupancy theory: subdivide the interval into "cells" of length r (the transmission range). If there exists an empty cell separating two cells that each contains at least one node, then the network is disconnected.
c) Random Interval Graph: The existence of the big spacings. (exact result)

2. In 2D, we do not have the exact result. Instead, the following techniques are used to obtain the asymptotic results.

a) Isolated node: The existence of an isolated node

From 1D results, we can predict that using occupancy theory may improve the results obtained under 2D networks. From observing the occupancy theory methodology, I assume there are two directions that we can look into the connectivity problem.

a) Divide the 2D area into cells and start from here.
b) Look at nodes lying within a certain sector of angle but are not directly connected.

I could not tell any further until I have more concrete ideas on that.

Notes - The Capacity of Wireless Networks

*This note is written based on [1].

Due to lack of any centralised control, the ad-hoc networks faces different problems at different layers. At the network layer, the main problem is routing. The choice of medium access scheme is also difficult in ad hoc networks, and random access appears to be the current favourite. At the physical layer, an important issue is that of power control. The transmission power should be high enough to reach the intended receiver while causing minimal interference to other nodes.

The direct connectivity between two nodes can be described in two models:
1. The Protocol Model
2. The Physical Model

The authors obtained the capacity based in these two models. In short, the capacity per node decreases as the number of nodes increases. Some implication of the results obtained.
1. The number of uses in a network should be small.
2. Nodes should only communicate with nearby nodes only.
3. A faster rate of decay of signal power with distance allows greater transport and throughput capacity.
4. Group nodes into clusters. Cluster heads are used as relay nodes.
5. Dividing the channels into sub-channels does not change any of the results.
6. To increase throughput, we can add in pure relays into the network (with extra cost).
7. To increase throughput, we can connect base stations by a wired network.

[1] P. Gupta and P. R. Kumar, "The Capacity of Wireless Networks," IEEE Transactions on Information Theory, vol. 46, pp. 388-404, 2000.

Notes - The Connectivity of 2D Ad-Hoc Networks

*This note is written based on [1].

Connectivity is one of the fundamental and widely studied properties of wireless multihop ad-hoc networks. The existing studies applied the theories in the following area:

1. Random Geographic Graph: E.g. for uniformly distributed nodes, the longest nearest-neighbour link and the longest MST (minimum spanning tree) edge have the same value as n goes to infinity. -> connectivity occurs (asymptotically) when the last isolated node disappears.

2. Continuum Percolation: Refer to [2] and [3].

However, as discussed in [1], the theories are only applicable to dense networks. The contribution of the results on dense networks may be limited as network capacity will be compromised. In order to circumvent this problem, the authors added the size of the deployment region as a parameter of the model, and characterise the critical transmission range as the size goes to infinity.

The following two theorems are obtained in [1] for 2D networks:




[1] P. Santi and D. M. Blough, "The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks," IEEE Transactions on Mobile Computing, vol. 2, pp. 25-39, 2003.

[2] P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, W.M. McEneaney, G. Yin, and Q. Zhang (Eds.), pp. 547-566, 1998.

[3] O. Dousse, et al., "Connectivity in ad-hoc and hybrid networks," in IEEE Conference on Computer Communications (INFOCOM), 2002, pp. 1079-1088.