Information Technology Journal

Year: 2013 | Volume: 12 | Issue: 12 | Page No.: 2433-2439
DOI: 10.3923/itj.2013.2433.2439

Multicast Capacity of UWB Wireless Ad hoc Networks with Power Constraint

Yongfa Hong, Xinzhen Bai and Binguo Wang

Abstract: This study discusses the multicast capacity of a large-scale random Ultra Wideband (UWB) wireless ad hoc network with power constraint. For different number of multicast destination, two different upper bounds of multicast capacity are given. When the number of multicast destination is , an upper bound of multicast capacity is when the number of multicast destination is , an upper bound of multicast capacity is . A strategy of MAC and routing which can achieve the lower bound of multicast capacity of power- constraint UWB wireless ad hoc networks is designed and the lower bound of multicast capacity is . These results extend the foregoing work on unicast capacity for UWB wireless ad hoc networks.

Keywords: routing, MAC, Multicast capacity, wireless ad hoc network and UWB

INTRODUCTION

Wireless ad hoc networks are a type of communication networks composed of a set of nodes with dynamical networking ability and without any infrastructure support. Each node has the double function for routers and hosts. The communication and cooperation between nodes are by virtue of wireless links. The characteristics of distributed structure, limited bandwidth, instability of link, dynamical topological structure make wireless ad hoc networks different to other communication networks. So, the research on capacity of wireless ad hoc networks is becoming more challenge. Gupta and Kumar (2000) initiated the research of asymptotic capacity of static wireless ad hoc networks. For wireless random networks whose nodes are randomly and uniformly deployed in a disc with unit area, they showed that the asymptotic capacity is:

under the protocol model and the upper bound and lower bound are and:

under physical model. Grossglauser and Tse (2002) and Diggavi et al. (2005) showed that the mobility of nodes, even one-dimensional mobility, can improve the asymptotic capacity of wireless random networks to O(n). Haddad et al. (2006) showed that the broadcast capacity of wireless random networks is:

where, Δ, dare the reference parameter and the dimension of space. For more general occasion, Shakkottai et al. (2007) derived an upper bound of multicast capacity of wireless random network and designed a multicast routing mechanism based “comb” structure which can make wireless random network attain the multicast capacity in the same order with the upper bound. Li et al. (2007) showed that the total multicast capacity is:

when the number of destination of each multicast source is:

and is Θ(W) when the number of destination of each multicast source is:

UWB (Ultra Wideband) is a technology for transmitting information spread over a large bandwidth (>500 MHZ). UWB has many advantages such as strong anti-interference performance, high transmission rate, very wide bandwidth, low energy consumption, small sending power etc. UWB technology has many applications such as indoor communication, high rate wireless LAN, home network, precision locating and tracking applications etc. Negi etc study the asymptotic capacity of power-restricted UWB wireless ad hoc networks. Negi and Rajeswaran (2007) showed an upper bound of capacity for single node of above networks is:

and an feasible lower bound of capacity for single node is:

With the theory of percolation, Zhang and Hou (2005) improve the above-mentioned lower bound to:

which is the same order with the upper bound. Otherwise, this study is confined to uni-cast capacity of networks. The object of the present study is to study the multicast capacity of power-restricted UWB wireless ad hoc networks.

NETWORK MODEL

Suppose that n nodes are randomly and uniformly deployed in a square with unit area, the set of all nodes is denoted as V = {v₁, v₂,þv_n}. Each node is a source of a multicast flow and each source randomly choose k-1 (2≤k≤n) different nodes as destinations of multicast flow from the remainder n-1 nodes. Each source v_i will send data to its all destinations with rate r_k(n). Since the restriction of transmission capability of wireless nodes, the data maybe by virtue of multi-hops and storage-and-forward to reach to all destinations. If there is a spatio-temporal scheduling strategy so that the data send by source with rate r_k(n) can be received by corresponding destinations with high probability, then the rate r_k(n) is called feasible multicast throughput.

Suppose all physical links are point-to-point links which use UWB impulse wireless transmission technology and support the rate of Shannon capacity. Each node adopt binary PPM modulation with additive white Gaussian noise, the power spectrum density of noise is N₀. The signal attenuation is in proportion to the α power of the distance between the sending and receiving nodes, where α≥2 is the path loss index. So, the power loss h_ij between node v_i and node v_j can be expressed as h_ij = |v_i-v_j|G^α, where |v_i-v_j| is the Euclidean distance between node v_i and node v_j. So, the SINR (signal-to-interference and noise ratio) at the receiving node can be expressed as:

where, P_ij is the sending power of node v_i on the link v_i→v_j, P_k is the total transmit power of node v_k, W is signal bandwidth, M is the number of collided packets since there are M nodes simultaneously send data, a_k is orthogonal factor. For homogenous networks, a_k = a, ∀k∈{1, 2,…n}. The first term ηW of denominator in the SINR is the Gaussian noise power and the second term is Multi-user Interference (MUI). If AWGN noise power is far larger than MUI, then MUI can be ignored with respect to AWGN noise. So, the SINR can be simplified as SINR = P_ijh_ij/(N₀W). By the formula of Shannon capacity, the Shannon capacity C_ij of each link can be expressed as:

When node v_i use power P_ij to send data on the link v_i→v_j, the transmission rate on the link v_i→v_j, is:

which means:

AN UPPER BOUND OF MULTICAST CAPACITY

This section will derive an upper bound of Power-constraint UWB wireless ad hoc networks. Firstly, a square with unit area is divided into smaller square with area by use of straight line paralleling to the side of square. Thus the length of side of smaller square is:

The set of all smaller squares is denoted as V(n, ρ(n)). The number of nodes inside region s is denoted as N(S). The following Vapnik-Chervonenkis theorem will be used in the next discussion:

Vapnik-Chervonenkis theorem (Vapnik and Chervonenkis, 1971): Suppose is a set with finite VC-dimension VC-d(), {X_i} is a sequence of independently random variables with a common distribution P, then for any ε, δ>0, when:

is valid.

By use of the above-mentioned Vapnik-Chervonenkis theorem, the following lemma can be proved:

Lemma 1: For a smaller square S (S∈V(n, ρ(n)), the number N(S) of nodes which lie inside S satisfies 50 log n≤N(S)≤150 log n with high probability.

Proof: It is easy to verify that the VC-dimension VC-d(v(n, ρ(n))) of set V(n, ρ(n)) is 3. Let:

when n is large enough, by Vapnik-Chervonenkis theorem:

That is:

Thus:

This means that the number N(S) of nodes which lie inside S satisfies 50 logn≤N(S)≤150 logn with high probability.

For the set T_i of all multicast trees which connect the multicast source v_i and corresponding k-1 multicast destinations, if ||t_i|| denotes the sum of side of multicast tree t_i∈T, Li et al. (2007) prove the following lemma.

Lemma 2 (Li et al., 2007): For any t_i∈T_i, when k→∞, then ||t_i|| satisfies , where, τ is a constant.

For two multicast trees t_i and t_i* in T_i, if r_i(k) and r_i*(k) denote the multicast rate of multicast source, ||t_i||^α, ||t_i*||^α denote the sum of α power of each side’s Euclidean length for multicast trees t_i and t_i*, where t_i* is the multicast tree with minimum sum of α power of each side’s Euclidean length, that is . t_i* is called the minimum power multicast tree. The total power used by two multicast trees are P(t_i) = r_i(k)N₀||t_i||^α and P(t_i*) = r_i(k)N₀||t_i*||^α, respectively. In order to derive the upper bound of multicast capacity, an upper bound of the number of the smaller squares which intersect with minimum power multicast tree t_i* is needed.

Lemma 3: The number N_max of the smaller squares which intersect with minimum power multicast tree t_i* satisfies:

Proof: With a similar method used by Li et al. (2007), a region C(t_i*) in the plane is defined as:

where, Z, Y are the points lie in square with unit area. If |C(t_i*)| denotes the total area of the region |C(t_i*)|, then |C(t_i*)| satisfies:

Since the area of each smaller square is , so, the number N_max of the smaller squares which intersect with minimum power multicast tree t_i* satisfies:

Since each smaller square contain at most 150 log n nodes with high probability, so N_max satisfies:

with high probability. Since the total consumed power of each multicast tree depend on the rate of multicast source and the length of multicast tree, then:

Because the total power can be availed by all nodes is nP₀ and there are n minimum power multicast trees in the network. By the symmetry of deployment of nodes, the expectation of the consumed power for each minimum power multicast tree t_i* must be less or equal to P₀, this means:

The following two kinds of situations are discussed:

since , as n is large enough, then .

Thus there are constants c, c₁>0 such that:

So:

That means that:

Theorem 1: The multicast capacity of the above-mentioned power-constraint wireless ad hoc networks satisfies:

When:

Then:

When:

Then:

Especially, when k = 2 which is the situation of unicast, then by the above theorem 1:

That is the same order with the upper bound of pernode unicast throughput of Power-constraint UWB wireless ad hoc networks which is derived by Negi and Rajeswaran (2007).

A LOWER BOUND OF MULTICAST CAPACITY

In this section, a lower bound of multicast capacity is derived by virtue of the constructive method. Since each multicast source can randomly choose different k-1 (2≤k≤n) nodes from n-1 nodes, so, a node maybe the destination for multiple multicast flows. According to Li et al. (2007), a node is the destination for at most:

multicast flows with high probability. With a Similar method of Li et al. (2007), a square with unit area is divided into smaller square with area by use of straight line paralleling to the side of square, thus there are 1/a(n) smaller square in the square with unit area. For this partition, Li et al. (2007) prove the following lemma.

Lemma 4 (Li et al., 2007): If:

then each smaller square contain Θ(na(n) nodes with high probability.

Since:

satisfies the condition of the above lemma, so each smaller square will contain Θ(na(n)) = Θ(log n) nodes with high probability. Next, a multicast tree which connects multicast source and all multicast destinations is constructed based on the Manhattan multicast routing algorithm by Li et al. (2007). Such construction make the number of multicast flow through a smaller square be with high probability. As discussed earlier, each smaller square contain Θ(log n) nodes with high probability. In order to balance the number of multicast flows in each smaller square. The following multicast flow allocation mechanism is adopted:

Since each smaller square contain Θ(log n) nodes with high probability and the number of multicast flows through a smaller square is at most . By the above-mentioned multicast flow allocation mechanism, the number of multicast flows relayed in a smaller square is at most:

with high probability, so the number of assigned multicast flows for a node in a smaller square is at most:

with high probability.

Since, the transmission of node is limited to the adjacent smaller squares, the rate d(n) which is transmitted by a node in a smaller square satisfies:

and the number of assigned multicast flows for a node in a smaller square is at most:

with high probability. So if chosen multicast rate r(n) satisfies:

Then it is ensured that r(n) is a feasible multicast rate.

Thus multicast rate of Power-constraint UWB wireless ad hoc networks satisfies:

Above all, the following conclusion is attained:

Theorem 2: A feasible lower bound of multicast capacity for Power-constraint UWB wireless ad hoc networks is:

Especially, when k = 2 which is the situation of unicast, then the result of the above theorem 2 is reduced to:

The above feasible lower bound is higher on order than the feasible lower bound:

which is given by Negi and Rajeswaran (2007).

CONCLUSION

The present study discusses the multicast capacity of power-constraint large scale random UWB wireless ad hoc networks. According to the number of the multicast destinations, two different upper bound of multicast capacity are derived. When the number of multicast destinations satisfies:

an upper bound of multicast capacity for Power-constraint large scale random UWB wireless ad hoc networks is:

When the number of multicast destinations satisfies:

an upper bound of multicast capacity:

where, α≥2 is path loss index, n is the number of network nodes, k is the number of multicast destinations. On the other hand, a strategy of MAC and routing which can attain feasible throughput:

is designed, at the same time, a feasible lower bound of multicast capacity for power-constraint UWB wireless ad hoc networks is obtained.

REFERENCES