Multicast Capacity Analysis for High Mobility Social Proximity Machine-to-Machine Networks

Abstract

Wireless machine-to-machine (M2M) networks enable ubiquitous sensing and controlling via sensors, vehicles, and other types of wireless nodes. Capacity scaling law is one of the fundamental properties for high mobility M2M networks. As for high mobility M2M networks, vehicular ad hoc networks (VANETs) are a typical case. Since vehicles have social property, their moving trajectory is according to the fixed community. With the purpose of transmitting packets to different communities of VANETs and further improving the network capacity, we study the multicast capacity of bus-assisted VANETs in two scenarios: forwarding scenario and routing scenario. All the ordinary vehicles obey the restricted mobility model. Thus, the spatial stationary distribution decays as power law with the distance from the center spot of a restrict region of each vehicle. In forwarding scenario, all the buses deployed in all roads as intermediate nodes are used to forward packets for ordinary vehicles. In routing scenario, buses and ordinary cars construct a highway path supported by percolation theory to transmit urgent packets. Each ordinary vehicle randomly chooses $k - 1$ vehicles from the other ordinary vehicles as receivers. For the two kinds of scenarios, we derived the upper bound and lower bound, respectively.

1. Introduction

In recent years, M2M networks have been a subject of intense interests due to the rapid evolution of wireless communication systems. M2M networks can be used to enable a wide variety of automated complex operations, which include advanced sensing, remote control, and monitoring technologies. M2M networks have many differences compared with conventional wireless networks because M2M is a machine-oriented networking technology. First of all, M2M networks commonly need to support a large number of devices. Second, power consumption of M2M devices is very important due to the limited battery capacity. Third, various data transfer delay requirements may exist depending on the M2M application being executed [1, 2]. Examples of M2M communications networks include vehicular ad hoc networks (VANETs) [3], underwater sensor networks (UWSNs) [4], wireless body area networks (WBANs) [5], and wireless mobile social networks [6–8].

Capacity scaling laws of wireless networks have attracted a lot of attention. Since Gupta and Kumar initiated the study of capacity scaling laws of ad hoc networks [9], the capacity of different types of wireless networks has been widely studied, such as sensor networks, ad hoc networks, cellular networks, vehicular networks, and so forth. Grossglauser and Tse showed how the mobility increases the capacity of ad hoc wireless network in 2002 [10], Li proposed a new method to calculate the multicast capacity of wireless ad hoc networks in 2009 [11], Garetto and Leonardi proved restricted mobility improves delay-throughput tradeoffs in mobile ad hoc networks [12], and Mao et al. calculated the multicast capacity for hybrid wireless networks [13] in 2012. There are also some people who work on the capacity of energy-constrained networks [14]; some people study the capacity of arbitrary networks [15] and inhomogeneous networks [16], some people let nodes cooperate with a hierarchical MIMO network [17], and some people use network coding [18] to improve the network capacity.

The capacity of vehicular ad hoc networks was first studied in 2007 by Pishro-Nik et al. [19]. They proposed a grid-like framework as shown in Figure 1 to demonstrate the streets of urban region. We have abstracted one real construction from the real urban map. However, we realized we also have to use statistic methods to calculate the capacity of high mobility social M2M networks. If the statistic methods were applied in the calculation, the detail of the real construction will be neglected in the calculation. Thus, there is no difference between real construction and grid-like construction. Furthermore, grid-like construction is easy to understand and convenient to be used in calculation. As a result, we choose the grid-like construction to be the geometrical construction in our calculation. Lu et al. extended their work and obtained the per-vehicle throughput $Ω (1 / \log (n))$ and delay $O (\log^{2} (n))$ [20]. However, Lu et al. only consider the scenario that source vehicles can only transmit packets to the vehicle which belongs to the same community as the source vehicle and they only consider the unicast transmission. There are rare studies that work on the calculation of capacity for different VANETs scenarios. The capacity of different typical ad hoc scenarios cannot be adopted for theoretical analysis for VANETs and cannot provide guidelines in designing VANETs. Therefore, we calculate the multicast capacity for bus-assisted VANETs in this paper.

Figure 1

The real map of urban area.

Assume that n ordinary vehicles and $n_{b}$ buses are deployed in a grid-like road framework. This construction is composed of m parallel lines with other intersected m parallel lines. Since the larger urban region means more number of vehicles, m increases linearly with n. Vehicles that have social proximity mobility always move in a localized area centered at the driver's home or work space and seldom move out. Thus, we let all the ordinary vehicles obey the restricted mobility model. As a result, the spatial stationary distribution of vehicles decays as the form of power law with the distance between the home point and each vehicle. Each ordinary vehicle randomly chooses $k 1$ vehicles from the other ordinary vehicles as receivers. The network can be considered as unicast when k is 2 and as broadcast when k is $n 1$ .

In the forwarding scenario, all the buses deployed in all roads as intermediate nodes are used to forward packets for ordinary vehicles. The buses of each road were considered as one bus trajectory. The bus forward scheme was proposed in [21]. Each transmission flow transmits packets via two-hop relay scheme proposed in [22]. All the forward processes of buses are considered as one-hop. The packets could be transmitted directly from source to destination or be transmitted to an intermediate vehicle or bus, then be forwarded to the destination. In the routing scenario, we use buses and ordinary cars to construct the highway system. We use percolation theory to prove that there are highway path clusters that cross through the network vertically and horizontally. Thus, based on a simple routing protocol, the highway system can ensure the packets can be transmitted to destination located in any place of VANET. Simultaneously, the urgent TTL requirement can be satisfied.

To schedule the interference in MAC layer of wireless transmission, we use the protocol model [6] as our interference model in this paper. We assume the bandwidth of wireless transmission is $W_{a}$ bits per time slot and the bandwidth of bus system is $W_{b}$ bits per time slot. For simplicity, we also assume that there is only one wireless channel in the bus-assisted forwarding and routing and all the vehicles and buses have enough memory to buffer all the packets.

Our Main Contributions. With the purpose of transmitting packets to different communities of VANETs and further improving the network capacity, in this paper we derive the upper and lower bound of the multicast capacity for bus-assisted VANET in two kinds of scenarios.

In the forwarding scenario, the per vehicle capacity of bus-assisted VANET is as follows:

\begin{matrix} O {\max [\frac{W_{a}}{k}, \min (\frac{W_{b} \sqrt{c}}{n \sqrt{k}}, \frac{W_{a} c}{k n})]} if k = O (c), \\ O {\max [\frac{W_{a}}{k}, \min (\frac{W_{b}}{n}, \frac{W_{a} c}{k n})]} if k = Ω (c) \end{matrix}

(1)

and

w . h . p

. scales of at least

Ω ((k - 1) / \log (n))

In the routing scenario, we construct the highway system to transmit the urgent packets. We also derive the capacity of per vehicle via bus‐assisted mode, it can achieve at most $O (1 / k d)$ and cannot be lower than $Ω (1 / \sqrt{k} d)$ .

The rest of the paper is organized as follows. In Section 2 we represent the network model in detail. The upper and lower bounds of multicast capacity by ad hoc forwarding are derived in Section 3. In Section 4 we calculate the upper and lower bounds of multicast capacity by bus forwarding. We combine the results of Sections 3 and 4 and obtain the multicast capacity for bus-assisted forwarding in Section 5. Section 6 constructs the highway path and derives the capacity of bus-assisted VANET in routing scenario. Section 7 discusses the results and the remaining challenges. Section 8 concludes this paper and reviews the results on multicast capacity for bus-assisted VANETs.

2. Network Model

2.1. Network Geometry

We use the grid-like construction (as shown in Figure 1) to represent the urban region. The construction comprises m parallel streets intersected with other m parallel streets. Each street considers a bus line. Let s denote the total number of road segments (street section between any two street lines) and let c denote the number of squares in the grid-like construction. Thus, $s = 2 c = 2 {(m - 1)}^{2}$ . The density of the network is $d = n / s = n / 2 (m - 1)^{2}$ . One has the experience that the center spots (such as workplaces, markets, and malls) always have high vehicular density than other locations. If we use a mathematical method to analyse this phenomenon, we can find out that the density of one location is steady. Furthermore, the density of the location would decrease as the distance from the center spot increases. Therefore, we can derive the density of one location according to its distance from the center spot. From Figure 1, we assume that Tier (1) is one of the center spots, so it has the highest vehicular density. According to the formulation calculated in [17], we can get the density of Tier (2) and Tier (3) based on their distance from Tier (1). Obviously, Tier (3) has lower vehicular density than Tier (2) due to its longer distance from Tier (1) than Tier (2). Larger urban region means the more number of vehicles, so we assume d is a constant to make the number of street segments s increase linearly with the number of vehicles n.

2.2. Mobility Model

Vehicles always move in a localized area centered at the driver's home or work space and seldom move out. Thus, we let all the ordinary vehicles obey the restricted mobility model. Each vehicle randomly selects one square as its home-point (as Tier $(1)$ which is showed in Figure 1). Tier $(2)$ was formed by the adjacent squares surrounding Tier $(1)$ . Tier $(3)$ was formed so forth. The restricted mobility region is Tier $(α), α \in {1,2, \dots, ω}$ , where Tier $(ω)$ is the outermost tier of the mobility region of a vehicle. The stationary distribution of vehicles on the road segments of Tier $(α)$ is denoted by $π_{α}$ . Thus, the steady-state location of vehicles is modeled by power law function $π_{α} = α^{- γ} π_{1}$ , where exponent $γ > 0$ . Moreover $π_{1} = 1 / \sum_{α = 1}^{ω} ‍ (16 α - 12) α^{- γ}$ is calculated in [17]. All the buses are deployed in all roads as intermediate nodes. They were used to forward packets for ordinary vehicles in the forwarding scenario and construct highway system with ordinary vehicles in the routing scenario. The buses of each road construct one bus line. Thus, there are $2 m$ bus lines in the network.

2.3. Communication and Interference Model

For simplicity, we assume that there is only one wireless channel in the bus-assisted forwarding and during a time slot t the wireless channel can only transmit $W_{a}$ bits. The bandwidth of the bus system is $W_{b}$ bits per time slot. Due to the interference of wireless transmission, one vehicle cannot transmit with two other vehicles at the same time slot. Let r denote the transmission range. The length of one segment is equal to r to ensure the transmission range covers the entire road segment. Thus, $r = (1 / m - 1)$ . To schedule the transmission flows, we adopt the protocol interference model. Protocol interference model schedule is defined as follows.

At each time slot, a transmission from vehicle i to vehicle j is successful only if the following inequality stands:

\begin{matrix} ∥ X_{i} (t) - X_{j} (t) ∥ \leq r \end{matrix}

(2)

and for any other vehicle l that transmits at t:

\begin{matrix} ∥ X_{l} (t) - X_{j} (t) ∥ \leq (1 + Δ) r, \end{matrix}

(3)

where Δ is a guard factor defining a protection zone around the receivers and

x_{i} (t)

denotes the location of vehicle i at the time slot t; we will add the missing definition in the paper.

2.4. Traffic Model and Relay Scheme

We consider n multicast flows existing in the network concurrently. Each packet is transmitted to $k - 1$ destinations. Each vehicle is the source of one multicast flow and one of the destinations of another multicast flow. The network can be considered as unicast when k is 2 and as broadcast when k is $n 1$ . There are three different forwarding strategies in the bus-assisted VANETs: ad hoc forwarding, bus forwarding, and bus-assisted forwarding. With the first forwarding method, multicast flows transmit packets via two-hop relay scheme. With the application of two-hop relay scheme, a vehicle can transmit packets to a destination directly or relayed through one intermediate vehicle that has more contact opportunities with the destination vehicle and all the intermediate vehicles are ordinary vehicles. Since each vehicle has the restricted mobility region, the source and destination have the same home-point and k is less than or equal to the number of vehicles that have the same home-point. The second forwarding method uses bus as intermediate vehicle. The forwarding scheme of buses is discussed in [18]. In this forwarding method, the bus is used in intercommunity communication. Thus, the source and destination have different home-points. The third forwarding method combines the above two forwarding methods.

2.5. Definitions of Capacity

In this paper, capacity denotes the feasible throughput. The capacity of VANETs is defined as follows.

Definition 1 (feasible throughput).

A throughput of $λ (n)$ bits per second for each vehicle is feasible if there is a spatial and temporal scheme for scheduling transmissions, and every vehicle can send $λ (n)$ bits per second on average to its chosen destination.

Definition 2 (capacity of vehicle network).

The average capacity of vehicular network is of order $θ (g (n))$ (we use Knuth's notation: given two functions $g (n) \geq 0$ where $f (n) = O (g (n))$ means $\lim su p_{n \to \infty} f (n) / g (n) = c < \infty$ ; $f (n) = Ω (g (n))$ is equivalent to $f (n) = O (g (n))$ ; $f (n) = Θ (g (n))$ means $f (n) = O (g (n))$ and $f (n) = Ω (g (n))$ ) bits per second if there are deterministic constants $c > 0$ and $c < c^{'} < + \infty$ such that

\begin{matrix} \lim_{n \to \infty} Pr (λ (n) = c (g (n)) is feasible) = 1, \\ \lim_{n \to \infty} \inf Pr (λ (n) = c (g (n)) is feasible) < 1 . \end{matrix}

(4)

Definition 3 (throughput capacity).

Let $G (T)$ denote the amount of data received by all the vehicles during time T. A capacity throughput $λ (n)$ is feasible if there is a scheduling scheme for which the following properties hold:

\begin{matrix} \lim_{T \to \infty} Pr (\frac{G (T)}{T} \geq λ) = 1 . \end{matrix}

(5)

3. Bounds in Multicast Capacity by Ad Hoc Forwarding

Forwarding scenario has two parts: ad hoc forwarding parts and bus forwarding parts. In this section, we discuss the bounds of capacity for pure ad hoc forwarding for the forwarding scenario. All the packets are transmitted to destination directly or via an ordinary vehicle. Since source vehicle and destination vehicle have the same home-point, k is less than or equal to the number of vehicles that have the same home-point. Broadcast cannot be achieved only with this forwarding method.

3.1. Upper Bound in Multicast Throughput Capacity by Ad Hoc Forwarding

We first calculate the upper bound of multicast throughput capacity by ad hoc forwarding. The following lemma is used in the calculation of upper bound of throughput capacity of ad hoc forwarding. This lemma was proved in [17].

Lemma 4.

Let $p_{a}$ denote the probability of a road segment being active as follows:

\begin{matrix} p_{a} = \frac{1}{(2 ⌈ 1 + Δ ⌉ ⌈ 2 + Δ ⌉)}, \end{matrix}

(6)

where

⌈ x ⌉

represents the smallest integer number greater than or equal to x.

According to Lemma 4, we first derive the upper bound in multicast throughput capacity by ad hoc forwarding.

Theorem 5.

For the social proximity VANETs, with two-hop scheme, the average per-multicast throughput capacity by ad hoc forwarding cannot be better than $1 / (2 k d ⌈ 1 + Δ ⌉ ⌈ 2 + Δ ⌉)$ .

Proof.

Let $G_{d} (T)$ denote the amount of data transmitted through direct transmission from source to destination during the time interval $[0, T]$ and let $G_{r} (T)$ denote the amount of data transmitted through relay transmission during the time interval $[0, T]$ . According to Definition 3, throughput $λ (n)$ satisfies the following inequality:

\begin{matrix} \frac{G_{d} (T) + G_{r} (T)}{T} \geq k n λ (n) - ε, \end{matrix}

(7)

where

ε > 0

is an arbitrary and fixed number and

ε \to 0

T \to \infty

. Let

K (T)

denote the total transmit opportunities during

[0, T]

. The total number of transmitted packets must be less than the total number of transmit opportunities during a long time interval. Since the relay transmission needs the transmitting opportunities twice to transmit one packet, we have the following:

\begin{matrix} \frac{1}{T} K (T) W_{a} \geq \frac{1}{T} G_{d} (T) + \frac{2}{T} G_{r} (T) . \end{matrix}

(8)

Substituting (7) into (8), we have the following:

\begin{matrix} \frac{1}{T} K (T) W_{a} \geq \frac{1}{T} G_{d} (T) + 2 (k n λ (n) - ε - \frac{1}{T} G_{d} (T)) . \end{matrix}

(9)

Sorting (9), we have the following:

\begin{matrix} λ (n) \leq \frac{(1 / T) K (T) W_{a} + (1 / T) G_{d} (T) + 2 ε}{2 k n} . \end{matrix}

(10)

When

ε \to 0

T \to \infty

\begin{matrix} λ (n) \leq \frac{(1 / T) K (T) W_{a} + (1 / T) G_{d} (T)}{2 k n} . \end{matrix}

(11)

Due to the interference of wireless transmission, the total transmission must be less than the concurrent transmissions during time

[0, T]

. According to the law of large numbers, we have the following:

\begin{matrix} \lim_{x \to T} \frac{1}{T} K (T) W_{a} \leq s p_{a} W_{a} . \end{matrix}

(12)

Similarly, we have the following:

\begin{matrix} \lim_{x \to T} \frac{1}{T} G_{d} (T) \leq s p_{a} W_{a} . \end{matrix}

(13)

The two equalities hold when there is always a transmission flow exits on each unit of a concurrent transmissions group during each time slot. According to Lemma 4, by substituting (12) and (13) into (11), we have the following:

\begin{matrix} λ (n_{v}) \leq \frac{s p_{a}}{k n} = \frac{p_{a}}{k d} = \frac{1}{2 k d ⌈ 1 + Δ ⌉ ⌈ 2 + Δ ⌉} . \end{matrix}

(14)

Thus, the theorem then follows.

3.2. Lower Bound in Multicast Throughput Capacity by Ad Hoc Forwarding

To obtain the lower bound of average multicast throughput capacity, we introduce the following lemma which was proved in [17].

Lemma 6.

The number of vehicles whose mobility region contains road segment i is denoted by N. Thus, N scales as $O (\log (n))$ , when $n \to \infty$ , the probability approaches 1.

With the two-hop relay scheme, a packet can be successfully transmitted only if there exists at least one source-destination pair or source-intermediate pair when the road segment is active. Since sources and destinations have the same home-point, there is one source-destination pair or source-intermediate pair with probability $(k - 1) / 2 N$ . According to Lemma 6, the probability of success transmission is at least $Ω ((k - 1) / \log (n))$ . Therefore, we derive the following theorem.

Theorem 7.

The throughput capacity of average per-multicast flow can be scaled at least $Ω ((k - 1) / \log (n)) w . h . p$ .

4. Bounds in Multicast Capacity by Bus Forwarding

In this section, we calculate the bounds of multicast capacity by bus forwarding for the forwarding scenario. All the packets are relayed by bus, and all the ordinary vehicles can be the destinations of any source vehicle. With the bus forwarding, k can be equal to n to achieve broadcast in the network.

4.1. Upper Bound in Multicast Throughput Capacity by Bus Forwarding

We first calculate the upper bound in multicast throughput capacity by bus-to-bus transmissions. We introduce the Euclidean tree to demonstrate the bus transmission process of multicast flows and each segment of the bus transmission process used is one edge of a multicast tree. Let $T_{i}$ denote the ith multicast tree and let $S (T_{i})$ denote the number of segments the tree $T_{i}$ will use. The total number of used segments of total transmissions in the network is denoted by $L = \sum_{i = 1}^{n} ‍ S (T_{i})$ . To obtain the value of L, we introduce the following lemma which was proved in [20].

Lemma 8.

Given n nodes randomly and uniformly distributed in a 2-dimensional cube, divide the cube into c cells as Voronoi diagrams with the same side length. Each node transmits packets to k destination concurrent via base-station. The base-station forwarding of a transmission is considered as a Euclidean tree. When $k = O (m)$ , with probability of at least $1 - 2 e^{- n θ^{2} / 32}$ , the total edge number of all Euclidean tree is $L \geq n θ \sqrt{k m} / 16$ . When $k = Ω (m)$ , with probability at least $1 - 2 e^{- n / 8}$ , then $L \geq n m / 4$ .

Different from the base-station connected by fiber, the ones connected by bus carry packets and move to the destination along roads represented by segments in the grid construction. However, if we consider the intersections of road segments as the vertex of Euclidean tree and each intersection belonging to a unique square, we can obtain the same conditions with Lemma 8. Thus, the results are suitable for the Euclidean tree of bus-to-bus transmissions. According to the above analysis, we derive the following corollary.

Corollary 9.

In the grid-like construction, if one uses Euclidean tree which represents the bus-to-bus transmissions, one can have the following results. When $k = O (m)$ , with probability at least $1 - 2 e^{- n θ^{2} / 32}$ , the total edge number of all Euclidean tree is $L \geq n θ \sqrt{k m} / 16$ . When $k = Ω (m)$ , with probability at least $1 - 2 e^{- n / 8}$ , then $L \geq n m / 4$ .

Recall that there are s segments in the construction. Then according to Pigeonhole principle, when $k = O (c)$ , there is at least one cell that will be used by at least $(n θ \sqrt{k c} / 16) / c$ flows with probability at least $1 - 2 e^{- n θ^{2} / 32}$ and when $k = Ω (c)$ , there is at least one cell that will be used by at least $n_{s} / 4$ flows with probability at least $1 - 2 e^{- n / 8}$ . Let $W_{b}$ denote the packets number of transmission by bus during one time slot; then we have the following theorem.

Theorem 10.

When $k = O (c)$ , the per-multicast flow throughput capacity of bus-to-bus transmission is at most $W_{b} \sqrt{c} / n θ \sqrt{k} w . h . p$ . When $k = Ω (c)$ , the per-multicast flow throughput capacity of bus-to-bus transmissions is at most $4 W_{b} / n w . h . p$ .

Theorem 10 is the capacity of bus-to-bus transmissions; buses have to transmit packets to ordinary vehicles at last. Then we calculate the up bound of the transmission between buses and ordinary vehicles for bus forwarding method. Recall that the active probability of one segment is $p_{a}$ . The total transmission opportunities are at most $s p_{a}$ . Each packet firstly is transmitted to bus then is transmitted to ordinary vehicles by bus. One multicast flow totally has k links. Thus, according to Pigeonhole principle, at least one link of a multicast has at most $p_{a} / k n$ transmission opportunities. Then we derived the upper bound of the transmission between buses and ordinary vehicles for bus forwarding method.

Theorem 11.

The upper bound of the throughput capacity between bus and ordinary vehicles for bus forwarding is $W_{a} s p_{a} / k n = W_{a} p_{a} / k d$ .

Obviously, the minimum throughput of bus forwarding process and bus-to-vehicle process determines the throughput of whole bus forwarding. By summarizing Theorems 10 and 11, we derive the upper bound of multicast throughput capacity for bus forwarding.

Theorem 12.

The upper bound of the multicast capacity for bus forwarding is as follows:

\begin{matrix} O [\min (\frac{W_{b} \sqrt{c}}{n \sqrt{k}}, \frac{W_{a} c}{k n})] if k = O (c), \\ O [\min (\frac{W_{b}}{n}, \frac{W_{a} c}{k n})] if k = Ω (c) . \end{matrix}

(15)

4.2. Lower Bound in Multicast Throughput Capacity by Bus Forwarding

By using the bus forwarding method, a packet can be successfully transmitted by bus only if there exists at least one bus-destination vehicle when the road segment is active. Reference to the proof of Lemma 6, we can easily prove the following lemma.

Lemma 13.

The number of vehicles whose mobility region contains bus line i is denoted by $N_{b}$ . Thus, $N_{b}$ scales as $O (\log (n)) w . h . p$ .

According to Lemma 13, we know that in any segment there is one bus-destination vehicle pair with probability $(k - 1) / N_{b}$ and the probability of success transmission is at least $Ω (k / \log (n))$ . Therefore, we derive the following theorem.

Theorem 14.

The throughput capacity of average per-multicast flow can be scales at least $Ω ((k - 1) / \log (n)) w . h . p$ .

5. Capacity Bounds for Bus-Assisted Forwarding

In this section, we will analyze the throughput capacity for bus-assisted forwarding. The analysis is based on the results of ad hoc forwarding and bus forwarding derived above. With the purpose of transmitting packets to other communities that have different home-point and further improving the network capacity, both ad hoc forwarding and bus forwarding are used in bus-assisted forwarding. In particular, bus forwarding is the only way to transmit packets to other communities. According to the destination of packets, bus-assisted forwarding adaptively selects a better forwarding method. Therefore, the throughput capacity of bus-assisted forwarding cannot surpass the maximum capacity of ad hoc forwarding and bus forwarding. The maximum capacity of ad hoc forwarding and bus forwarding is optimum for bus-assisted forwarding. Similarly, bus-assisted forwarding has the same lower bound with ad hoc forwarding and bus forwarding. According to the analysis above, we can obtain the bounds of multicast capacity for bus-assisted forwarding as the following theorem.

Theorem 15.

The upper bound of the multicast capacity for bus-assisted VANET is as follows:

\begin{matrix} O {\max [\frac{W_{a}}{k}, \min (\frac{W_{b} \sqrt{c}}{n \sqrt{k}}, \frac{W_{a} c}{k n})]} if k = O (c), \\ O {\max [\frac{W_{a}}{k}, \min (\frac{W_{b}}{n}, \frac{W_{a} c}{k n})]} if k = Ω (c) \end{matrix}

(16)

and

w . h . p

. scales of at least

Ω ((k - 1) / \log (n))

6. Capacity of Highway Routing

The forwarding protocol can transmit packets with tiny delivery cost. However, the delay cannot be diminished by the protocol because it mainly depends on the velocity of the bus. For the urgent packets, the forward scenario cannot match the requirement. Thus, the capacity of forward scenario cannot satisfy the transmission of urgent packets. For the purpose of calculating the capacity of urgent packets transmissions in the bus-assisted VANET, we designed a basic routing protocol for the bus-assisted VANET. We call it the highway routing. Then we calculate the capacity with the highway routing.

6.1. Introduction of Percolation Theory

The highway system is constructed based on the percolation model on square lattice. Before we construct the highway, we first introduce the bond percolation of percolation theory.

Assume that some packets are generated on top of the network region. Will the packets be able to make their way from edge to edge and reach the bottom? This question is modeled mathematically as a two-dimensional network of $n \times n$ vertices, in which the edge between each two neighbors may be open (allowing the liquid through) with probability p or closed with probability $1 - p$ . For the purpose of transmitting packets all over the network, we have to derive the probability that an open path exists from the top to the bottom. For the regular square lattice, if there is an open path from the top to the bottom the open path from left to right of the network also exists.

The open probability p of the edge is independent. The probability of an open path existing is determined by p. The single open path is not enough to ensure the all over network transmissions. As the number of vehicles increases to infinity, the network construction increases to infinity. Thus, there must be infinite open path clusters to ensure all over network transmissions.

By Kolmogorov's zero-one law, in the regular square lattice, for any given p the probability that an infinite open path cluster exists is either zero or one. The probability of p is an increasing function that was proved in [19]. It increases sharply from approach zero to one in a short span of P. Therefore, there must be a critical p (denoted by $p_{c}$ ) determining the probability P that an infinite open path cluster exists in the regular square lattice. When p is below $p_{c}$ , the probability P is zero. When p is above $p_{c}$ , the probability P is one and an infinite open path cluster exists in the regular square lattice.

6.2. The Construction of Highway

As in Figure 2, we assume that the intersection is the center of a virtual square. The road between two intersections is one edge. The virtual square lattice is denoted by red dotted lines. The black lines denote the open paths. To calculate the $p_{c}$ in the square lattice of Figure 2, we introduce the definition of the coordination number which is denoted by z in this paper. It means the total number of neighbors of center intersection. Obviously in the regular square lattice in Figure 1, the coordination number is four. According to the result of Harry Kesten [20], the probability threshold $p_{c}$ is $1 / (z - 1)$ . Therefore, the open edge cluster exits only if the probability that the edge between two squares is open is larger than $1 / 3$ .

Figure 2

Construction of highway path.

Packets are forwarded by intermediate vehicles. In the network, each edge between two squares is open if the road between the two squares has at least one vehicle. Thus, the probability of each road having at least one vehicle must be larger than $1 / 3$ to make sure the open edge cluster exits in the network. For the regular road segment without buses, in any time slot the probability of not finding any vehicles is $\prod_{α = 1}^{ω} ‍ (1 - π_{α}) {N_{i}}^{α}$ , where ${N_{i}}^{α}$ denotes the road segment number of layer α. Thus, we have the probability that road segment i has at least one vehicle. It is also the open probability $p_{i}$ of edge i as follows:

\begin{matrix} p_{i} = 1 - \prod_{α = 1}^{ω} ‍ (1 - π_{α}) N_{i}^{α} . \end{matrix}

(17)

For any road segment,

p_{i} \geq π_{1}^{2}

. Obviously

π_{1}^{2}

is less than

1 / 3

. Thus, only ordinary vehicle cannot ensure the opening edge cluster in the network. The highway cannot be constructed by ordinary vehicles. However, the regular buses can significantly increase the probability that at any time slot the road segment has at least one vehicle. According to the real mobility trace collected by [21], we can know the probability

p_{b}

that in any time slot the road segment has a bus larger than

1 / 5

. Adding

p_{a}

and

p_{b}

, we can derive the probability that the edge between two squares has at least one vehicle is bigger than

1 / 3

. Therefore, with the bus-assisted roads, we can construct the highway path to transmit the urgent packets in the VANET.

6.3. Highway Routing Protocol

Based on the open edge cluster derivation above, we use basic routing protocol to transmit packets in VANETs. Following the protocol, all source vehicles upload packets to the highway path and then packets are transmitted through the highway path until they approach the destinations. Destination vehicles will download packets from highway path. Time slots will be well arranged to ensure the highway path has priority to occupy transmit opportunity.

Upload. Source vehicles upload the packets to highway path when there are some transmission opportunities. Otherwise, the source vehicle can add the packets to highway transmission flow when it is chosen as the intermediate vehicle of the highway path.

Routing. Packets are forwarded along the shortest highway path to the destination or the intermediate vehicle besides the destination. If the shortest bus path has a closed edge, then highway path will detour to avoid the closed path.

Download. Packets are forwarded to the destination vehicle through the highway path. The destination vehicle downloads the packet from the highway path when it has opportunity to access the link. Otherwise, the destination vehicle can get the packets from highway transmission flow when it is chosen as the intermediate vehicle of the highway path.

Figure 3 is used to show a simple routing process. Source vehicle S can be assumed as the highway path and transmit packets to destination vehicle D. When road a has no vehicle, the highway path detours to avoid road a. Then, packets will achieve the destination vehicle or the neighbor of destination D. Destination vehicle will get the packets or download them from its neighbor which is in the highway path.

Figure 3

Construction of highway path.

6.4. Calculation of Capacity

When vehicle upload or download packet from the highway path, one packet occupies one transmission opportunity. That process is equivalent to transmit one packet through one edge. Thus, the upload and download process can be assumed as the first edge and the last edge of the highway path. The transmission opportunities are arranged by protocol, and thus an interference group can fully use the transmission opportunities. Each packet will cost one transmit opportunity to pass through one edge. The network has total $s p_{a}$ transmission opportunities. When packets can be transmitted to each destination, they only pass through one edge. The capacity of each vehicle can achieve at most $(s p_{a} / k n) W_{a}$ . The upper capacity bound of VANET with highway is identical with the forward scenario. However, the lower capacity bound of VANET with highway is different from forward scenario. To calculate the upper capacity bound, we introduce a lemma proved by Neely and Modiano in [22].

Lemma 16.

Given a square b in the lattice, the probability that a random highway path will be routed via the square s is at most $c \sqrt{k} \cdot (r / a)$ , where c is a constant number.

Therefore, a square b can be used by at most $n c \sqrt{k} \cdot (r / a)$ packets. We consider the protocol can give the opportunity to the busier square. Thus, the busiest square will have more transmission opportunities than other squares in the same interference group. Thus, the opportunities of the busiest square b must be more than the average. Thus, we can easily derive the lower capacity bound in each vehicle as follows:

\begin{matrix} λ (n) \geq \frac{p_{a} W_{a}}{n^{2} c \sqrt{k} \cdot (r / a)} = \frac{W_{a}}{2 c n^{2} \sqrt{k} ⌈ 1 + Δ ⌉ ⌈ 2 + Δ ⌉} . \end{matrix}

(18)

The above analysis is summarized by the following theorem.

Theorem 17.

With the application of highway protocol, the per-vehicle capacity of VANET can be achieved at most $O (1 / k d)$ and cannot be lower than $Ω (1 / \sqrt{k} d)$ .

7. Discussion

Notice that $c = Θ (m^{2})$ and we did not use $Θ (m^{2})$ in the capacity results of bus routing method. The reason is that we use m to denote both road and bus lines in the grid-like construction in this paper, and the roads number is equal to the number of bus lines. However, the cell used in bus routing is constructed by bus lines not roads. If we use a different number of bus lines, the cell number will be different from the number of squares in the grid-like construction. Thus, for the capacity of scenarios with different bus lines, we only need to replace the value of c.

To calculate the bounds of multicast for the bus-assisted VANET, we assume that the TTL (time to live) of packets is infinite. However, in the realistic VANET, TTL is one of the most important characteristics of the packets in any kind of ad hoc network. Therefore, if we can tolerate the delay of transmission, the study of achievable capacity is also essential for the bus-assisted VANET. We will focus on the tradeoff between capacity and delay in the future work. Similarly, applying more real interference model is also essential such as physical interference model and Gaussian interference model. All of our results are derived under grid-like construction. A more realistic framework may close the gap of capacity between theoretic results and real value. We will consider all the remaining challenges in the future work.

We calculate the achievement per-vehicle capacity for the forwarding scenario and routing scenario of bus-assisted VANETs. The forwarding scenario can save lots of energy and transmission coasts to diminish the overhead of bus-assisted VANETs. The routing scenario can transmit packets within very little time to satisfy the urgent packets by sacrificing the overhead of the network. We just derive the performance. The selection of transmission scenario needs an additional protocol.

8. Conclusion

The capacity scaling law of high mobility M2M networks has been considered as one of the most fundamental issues. In this paper, we derive the upper and lower bounds of multicast capacity for high mobility social proximity M2M networks via bus-assisted forwarding method. In the routing scenario, we use buses and ordinary cars to construct the highway system for VANETs, which is a typical case of high mobility M2M networks. We use percolation theory to prove that there is a highway path cluster cross through the network vertically and horizontally. Therefore, the highway system can ensure the packets can be transmitted to destination located anywhere in VANETs. The per-vehicle capacity of routing scenario is also derived. At last we discussed how the different forwarding processes influence the results of capacity scaling law for high mobility M2M networks. Our work provides new insights for the design of bus-assisted VANETs as intermediate vehicle to relay packets.

Footnotes

Acknowledgment

This work is supported by Heilongjiang Province Education Department Foundation 12531Z007.

References

Zhang

Xie

Yao

Xiao

Guizani

Home M2M networks: architectures, standards, and QoS improvement

IEEE Communications Magazine 2011 49 4 44 52

2-s2.0-79953778099

10.1109/MCOM.2011.5741145

Zhang

Nekovee

Liu

Xie

Gjessing

Cognitive machine-to-machine communications: visions and potentials for the smart grid

IEEE Network Magazine 2012 26 3 6 13

10.1109/MNET.2012.6201210

Hartenstein

Laberteaux

K. P.

A tutorial survey on vehicular ad hoc networks

IEEE Communications Magazine 2008 46 6 164 171

2-s2.0-45749099297

10.1109/MCOM.2008.4539481

Akyildiz

I. F.

Pompili

Melodia

Underwater acoustic sensor networks: research challenges

Ad Hoc Networks 2005 3 3 257 279

2-s2.0-13944252629

10.1016/j.adhoc.2005.01.004

Hanson

M. A.

Powell

H. C.

Jr. Barth

A. T.

Ringgenberg

Calhoun

B. H.

Aylor

J. H.

Lach

Body area sensor networks: challenges and opportunities

Computer 2009 42 1 58 65

2-s2.0-59849115600

10.1109/MC.2009.5

Nan

Mao

Zhang

Gjessing

Wang

Guizani

Distributed resource allocation in cloud-based wireless multimedia social networks

IEEE Network Magazine. In press

Nan

Mao

Wang

Zhang

Stackelberg game for bandwidth allocation in cloud-based wireless live-streaming social networks

IEEE Systems Journal 2013 99

10.1109/JSYST.2013.2253420

Palomar

Alcaide

Molina

Zhang

Coalitional games for the management of anonymous access in online social networks

Proceedings of the 11th International Conference on Privacy, Security and Trust (PST '13)

July 2013

Tarragona, Spain

1 10

10.1109/PST.2013.6596030

Gupta

Kumar

P. R.

The capacity of wireless networks

IEEE Transactions on Information Theory 2000 46 2 388 404

2-s2.0-33747142749

10.1109/18.825799

10.

Grossglauser

Tse

D. N. C.

Mobility increases the capacity of ad hoc wireless networks

IEEE/ACM Transactions on Networking 2002 10 4 477 486

2-s2.0-0036670170

10.1109/TNET.2002.801403

11.

X.-Y.

Multicast capacity of wireless ad hoc networks

IEEE/ACM Transactions on Networking 2009 17 3 950 961

2-s2.0-67650114837

10.1109/TNET.2008.927256

12.

Garetto

Leonardi

Restricted mobility improves delay-throughput tradeoffs in mobile ad hoc networks

IEEE Transactions on Information Theory 2010 56 10 5016 5029

2-s2.0-77956697218

10.1109/TIT.2010.2059510

13.

Mao

X.-Y.

Tang

Multicast capacity for hybrid wireless networks

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '08)

May 2008

Hong Kong

189 198

2-s2.0-57349135219

10.1145/1374618.1374645

14.

Zheng

Asymptotic bounds of information dissemination in power-constrained wireless networks

IEEE Transactions on Wireless Communications 2008 7 1 251 259

2-s2.0-38349166400

10.1109/TWC.2008.060474

15.

Goussevskaia

Wattenhofer

HalldórssoN

M. M.

Welzl

Capacity of arbitrary wireless networks

Proceedings of the 28th Annual IEEE International Conference on Computer Communications (INFOCOM '09)

April 2009

Rio de Janeiro, Brazil

1872 1880

2-s2.0-70349680585

10.1109/INFCOM.2009.5062108

16.

Alfano

Garetto

Leonardi

Capacity scaling of wireless networks with inhomogeneous node density: lower bounds

Proceedings of the 28th Conference on Computer Communications (INFOCOM '09)

April 2009

Rio de Janeiro, Brazil

1890 1898

2-s2.0-70349668666

10.1109/INFCOM.2009.5062110

17.

Jiang

Shi

Hou

Y. T.

Kompella

On the asymptotic capacity of multi-hop MIMO ad hoc networks

IEEE Transactions on Wireless Communications 2011 10 4 1032 1037

2-s2.0-79955467996

10.1109/TWC.2011.020111.100528

18.

Lau

L. C.

A constant bound on throughput improvement of multicast network coding in undirected networks

IEEE Transactions on Information Theory 2009 55 3 1016 1026

2-s2.0-62749169985

10.1109/TIT.2008.2011516

19.

Pishro-Nik

Ganz

The capacity of vehicular ad hoc networks

Proceedings of the Annual Allerton Conference

september 2007

20.

Luan

T. H.

Wang

Shen

Bai

Capacity and delay analysis for social-proximity urban vehicular networks

Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM '12)

25-30 March 2012

Orlando, Fla, USA

1476 1484

10.1109/INFCOM.2012.6195514

21.

Lai

W. K.

Yang

K.-T.

M.-C.

Bus assisted connectionless routing protocol for metropolitan VANET

Proceedings of the 5th International Conference on Genetic and Evolutionary Computing (ICGEC '11)

September 2011

Xiamen, Cihna

57 60

2-s2.0-80455137227

10.1109/ICGEC.2011.22

22.

Neely

M. J.

Modiano

Capacity and delay tradeoffs for ad hoc mobile networks

IEEE Transactions on Information Theory 2005 51 6 1917 1937

2-s2.0-20544449224

10.1109/TIT.2005.847717