Uncoordinated Cooperative Multihop Forwarding in 2D Highly Dynamic Networks

Abstract

This paper investigates cooperative forwarding in two-dimensional highly dynamic wireless networks. Unlike traditional coordinated cooperative forwarding schemes that require a large amount of neighborhood discovery and coordination information to be exchanged before making the forwarding decision, this paper proposes an uncoordinated cooperative forwarding scheme where each node determines whether or not to forward a received packet independently based on a forwarding probability determined by its own location, the locations of the destination, and the transmitter from which it receives the packet, without the costly or even impractical neighbor discovery and coordination process. Analytical results are derived for the successful transmission probability and the expected number of forwarding nodes involved in the cooperative forwarding process. On that basis, discussions are presented on the optimal forwarding probability design that meets a predesignated successful transmission probability target using minimum number of forwarding nodes. Simulations are conducted to evaluate the performance of the proposed scheme.

1. Introduction

This paper considers the problem of cooperative forwarding in large highly dynamic wireless networks, for example, vehicular ad hoc networks (VANET) or mobile ad hoc networks (MANETs). On a high level, the problem can be described as follows: when a node in a large highly dynamic wireless network overhears a packet belonging to a particular source-destination pair, with minimal information about its neighborhood and environment, how does the node make decision on whether it should collaborate to forward the packet?

Of course, if every node overhearing the packet forwards the packet with a high probability, the packet can be delivered to its destination with a high probability but it may cause a large number of redundant transmissions thereby wasting precious radio resources. On the other hand, if the forwarding probability is low, the packet may not eventually arrive at its destination. Therefore, tradeoff between three main factors is involved in the decision process: (1) the amount of information used in making the forwarding decision. The more information is used, the more overhead is incurred in collecting the information. It was reported that current military prototype MANETs routinely experience overhead on the order of even 99 percent of the end-to-end packet transmissions [1]. Therefore overhead involved in the cooperative forwarding decision is an important consideration; (2) the forwarding probability which determines the number of nodes (or equivalently transmissions) involved in the cooperative forwarding process; and (3) the successful transmission probability, that is, the probability that the packet eventually arrives at its destination within a designated amount of time.

A major challenge for routing and forwarding in dynamic networks is that the nodes are constantly moving and the network topology is highly dynamic. Therefore the traditional layered approach, where the route between a source and its destination is determined before the actual data transfer, is unsuitable for dynamic networks. There are two common approaches to end-to-end packet transmissions in highly dynamic networks: broadcast and cooperative communication. Broadcast remains to be the most reliable and possibly the most widely used approach for packet transmission in highly dynamic networks [2, 3]; however it is well known to cause a large number of redundant transmissions and significant wastage in radio resources. Cooperative communication on the other hand allows additional nodes in the vicinity of the route that overhear the transmitted packet to assist in delivering the packet to its destination, leveraging the broadcast nature of the wireless medium to provide diversity against time-varying link fades and outages [4].

A common feature in existing cooperative techniques is the coordination required among the participating neighbors. These coordinations typically include the discovery of neighbors in the vicinity, the collection of channel information to these neighbors, and the selection of the best neighbor(s) whose cooperation will maximize the performance improvement [3–7]. For the well-known opportunistic routing schemes [8], coordination is required at every hop to decide the node that will serve as the packet's next hop towards the destination. It was reported in [1] that the coordination overhead may account for 99 percent of the end-to-end packet transmissions. Due to associated coordination overheads, existing cooperative communication methods are suitable mostly for mesh or sensor networks with static or relatively stable topologies. They are not useful when the topology is very dynamic, due to either a high velocity (e.g., vehicular networks) or a high density of the nodes (e.g., networks of mobile devices carried by people on a busy street or in a conference hall). In fact, in highly dynamic networks, the coordination overheads are incurred too frequently to be practical even just to maintain an up-to-date view of the neighbor topology, let alone an up-to-date channel state information to the neighbor nodes.

Motivated by the above observations, in this paper we consider an uncoordinated cooperative forwarding scheme, where nodes overhearing a packet make forwarding decisions independently without prior coordination or measurement of real-time channel information to its neighbors and even without being aware of their existence (apart from the transmitter of the packet). Furthermore, forwarding decision at each node is only based on the location of that node, the locations of the destination and the transmitter from which it receives the packet, and some limited prior statistical knowledge about the local environment, namely, the spatial distribution of the nodes and radio propagation characteristics. A major challenge in the uncoordinated cooperative forwarding scheme is the design of the forwarding probability on the one hand minimizing the number of transmissions required to deliver the packet to its destination and on the other hand guaranteeing a designated transmission success probability. In the literature, the forwarding probability has been chosen to be a predefined fixed value [9], a linear function of the distance between the transmitter and the receiver [10], or to be determined jointly by the distance to the destination and nodes’ spatial distribution [3]. In [4], theoretical analysis was presented in the successful transmission probability using three uncoordinated forwarding schemes in two-hop scenario where the source and the destination are at most two hops away. Reference [5] further obtained the optimal forwarding scheme in the two-hop scenario. Despite the above advances in the field, design of optimal uncoordinated forwarding scheme for multihop scenarios, backed by solid theoretical analysis, remains an open challenge. It is a focus of this paper to tackle the challenge.

More specifically, the main contributions of this paper are as follows:

• (i)

Considering two-dimensional highly dynamic networks, this paper proposes an uncoordinated cooperative forwarding scheme, where each node receiving the packet makes forwarding decisions independently of other nodes, using its own location, the locations of the destination, and the transmitter from which it receives the packet and radio propagation characteristics only, without prior coordination with its neighbors and even without being aware of their existence.

(ii)

Performance of the proposed uncoordinated forwarding scheme is analyzed. For a pair of source and destination separated multiple hops away and with a known distance, the expected number of forwarding nodes and the successful transmission probability are obtained.

(iii)

On the basis of the analysis, discussions are presented on the design of the forwarding probability function and forwarding area to meet a predesignated target on the probability of successful transmission while using the minimum number of forwarding nodes.

(iv)

Simulations are conducted to validate the performance of the proposed uncoordinated cooperative forwarding scheme.

The technique and analysis presented in this paper can be useful for designing cooperative communication strategies in large and highly dynamic networks.

The rest of the paper is organized as follows. In Section 2, we give an accurate definition of the network models and explain the design of the uncoordinated cooperative forwarding scheme and the problem formulation. Section 3 presents performance analysis of the proposed uncoordinated cooperative forwarding scheme and on that basis discusses the design of the forwarding probability function and forwarding area. Section 4 presents simulations and discussions. Finally, Section 5 concludes the paper.

2. Network Model

In this paper, we consider a two-dimensional (2D) dynamic network with a single source-destination pair and the distance between them is a deterministic value L. Without loss of generality, we assume that the source is located at the origin (S) and the destination is located at D. We construct a 2D coordinate system using line $SD$ as x-axis. All other nodes apart from the source and the destination are distributed in a square with side length L (as shown in Figure 1), modeling as a homogeneous Poisson Point Process (PPP) Γ with known density ρ. The probability distribution function of the distance between a pair of randomly chosen nodes in a 2D network can be readily obtained. Therefore, it is straightforward to extend the results obtained in this paper to 2D networks with multiple source-destination pairs.

Figure 1

Scenario.

When we consider a transmission between the source and the destination, movement of nodes during the end-to-end transmission of the packet is not considered. That is, we consider a snap-shot of the network at a particular time instant. A typical end-to-end transmission can be completed in the order of milliseconds, during which the movement of nodes is comparatively small. Moreover, we consider that a pair of nodes are directly connected if and only if their Euclidean distance is smaller than or equal to R. That is, the well-known unit disk connection model is considered. The use of the unit disk model helps us to ignore the impact of physical layer details and focus on the impact of the topology aspect of the network, which is the main focus of our paper. Moreover, [11, 12] verify that the connectivity probability of a network is higher under a log-normal connection model (which can be considered a realistic connection model in real network) compared with that under a unit disk with the same expected number of connections of each node. Therefore, we can utilize the unit disk model to pursue the lower bound of successful transmission probability under other connection models, which can be considered the worst case for the general connection model.

We assume that each node knows its own location; this can be obtained easily either from an embedded GPS receiver, which is becoming increasingly ubiquitous in many mobile devices and vehicles [4, 5], or via one of the numerous wireless localization techniques available [13], the location of the transmitter from which the node receives the packet of interest and the location of the destination, which can be carried in the packet header. With the popularization of smart phones, it is easy to obtain the location information at low cost. Therefore, the requirement for the node location will not cause much additional cost.

Using the above information, the node makes forwarding decision independently without prior coordination with its neighbors and even without being aware of their existence. More specifically, the following rule is used in making a forwarding decision when a node overhears a packet.

• (i)

The node at v first judges whether it is in the forwarding area. If the node is in the forwarding area denoted by $u\in A$ , where A is the location set of the nodes in the forwarding area (we will explain the forwarding area later), it calculates the probability that it will forward the packet using its own location, the location of the transmitter denoted by z, and the forwarding probability function is $P_f(v-z)$ (the design of the forwarding probability function $P_f$ will be explained later). Otherwise, the node simply drops the packet.

(ii)

If the node decides to forward the packet, it first waits for a random backoff time t. Then three situations may possibly occur: (1) if it does not overhear any transmission during the backoff period, it will forward the packet as the new transmitter; or (2) the node at v overhears the transmission from a node located at u AND $‖v-D‖\ge ‖u-D‖$ . In this situation, the node simply drops the packet; or (3) the node at v overhears the transmission from a node located at u AND $‖v-D‖<‖u-D‖$ . In this situation, the transmission by the node at v may still help the packet to reach nodes that have not received the packet before. Therefore the node at v updates its forwarding probability using the node at u as the new transmitter and remakes decision on whether it will forward the packet, independently of its previous decision. If it decides to forward the packet, it starts a new backoff process. Otherwise, it gives up forwarding and discards the packet.

(iii)

The process naturally stops when the packet reaches its destination or there is no forwarding node.

The design of the uncoordinated cooperative forwarding scheme is intended to strike a balance among the amount of information and coordination required to make a forwarding decision, the transmission success probability, and the number of transmissions (or equivalently forwarding nodes) required to reach the destination.

A node at v is said to be a k -hop receiver if when the packet is received by the node for the first time, the packet has been transmitted k times by nodes whose distances to destination are larger than $‖v-D‖$ , including the transmission by the source. A node at v is said to be a k -hop transmitter if, by the time when the node transmits following the rules described in the last paragraph, the packet has already been transmitted k times by nodes whose distances to destination are larger than $‖v-D‖$ including the transmission by the source. Following the definition, the source is counted as the 0th hop transmitter. Note that, in our forwarding scheme, it is possible that a k-hop receiver is a m-hop transmitter for $m\ge k$ . Let $z_k$ be the location of the k-hop transmitter. For a fixed value of k, there can be at most one node that is a k-hop transmitter.

Let ${\varphi }_k(v)$ be the probability that a node at v is a k-hop receiver. Let $M(v)$ be the number of transmissions (or forwarding nodes) required to deliver the packet from the source to a node located at v distance away using our uncoordinated forwarding scheme. $M(v)$ is a random positive integer. Let $P_{\text{suc}}(v)$ be the probability that a packet transmitted from the source successfully reaches a node at v. We note the following relationship that will be used in the latter analysis:

$$\begin{array}{cc}& P_{\text{suc}}\left(v\right)={\displaystyle \sum }_{k=\mathrm{1}}^{\infty }‍{\varphi }_k\left(v\right),\hspace{1em}\hspace{1em}E\left[M\left(v\right)\right]={\displaystyle \sum }_{k=\mathrm{1}}^{\infty }‍k{\varphi }_k\left(v\right).\end{array}$$

(1)

Given the above definitions, the objective of the uncoordinated cooperative forwarding scheme design can be written analytically as follows:

$$\begin{array}{l}\underset{P_f\left(x\right)}{\min }\hspace{1em}E\left[M\left(L\right)\right]\\ \text{s}.\text{t}.\hspace{0.17em}\hspace{0.17em}{P}_{\text{suc}}\left(L\right)\ge \mathrm{1}-\varepsilon ,\end{array}$$

(2)

where ɛ is the a predesignated small positive constant.

3. Problem Analysis

In this section, we first introduce the definition of forwarding area and give three specific cases. Then, we analyze the performance of the uncoordinated cooperative forwarding scheme proposed in the last section where the performance is measured by two metrics: $P_{\text{suc}}(D)$ and $M(D)$ . On the basis of the analysis, we finally investigate the design of forwarding probability function $P_f(x)$ that minimizes the expected number of transmissions while meeting the performance objective that $P_{\text{suc}}(D)\ge \mathrm{1}-\varepsilon$ .

3.1. Forwarding Area

As we mentioned above, the only available information for an intermediate node is its own location, the location of the transmitter, and the destination from the packet header. Thus, a node can easily derive whether it is located within a specific area (called forwarding area) relative to the available locations. The forwarding area may be basically of any shape provided that each transmission should make a positive progress toward the destination and all nodes in this area are within the transmission range of each other. Note that one important design criterion of the forwarding area is to guarantee that all nodes in the forwarding area can overhear each other. Therefore, there is no hidden node problem in our scheme. Here we pick three specific forwarding areas due to their typicality and tractability in mathematics. Only the nodes within the forwarding area have opportunities to be a transmitter, whereas the other nodes outside this area just drop the received packet.

As the definition of forwarding area described in the previous paragraph, we may consider different areas that fulfill the requirement that more potential forwarding nodes are within the transmission range of other potential forwarding nodes. Obviously the forwarding area should be large in order to increase the probability of finding a potential forwarding node within the area. Furthermore, the shape and the location of the area should favor nodes that are near to the destination, thus minimizing the number of hops (number of transmissions) to the destination. In Figure 2, three possible areas are depicted, namely, circle, sector, and Reuleaux triangle, which all fulfill the requirement of being forwarding area [14].

Figure 2

Forwarding area.

(1) Maximum Communication Area (MCA). It is defined as the largest region within which any pair of nodes can hear each other. Thus, it is a circle with a diameter equal to the transmission range of a node. It is the circle with $SR$ as its diameter in Figure 2. Note that $SR$ should be colinear with $SD$ . Such arrangement of $SR$ maximizes the possible area within the circle progressing to the destination. The area of MCA is $S_{\mathrm{1}}^{\text{MC}}=\pi R^{\mathrm{2}}/\mathrm{4}$ .

(2) 60-Degree Radian Area (DRA). It is a radial region that includes a 30-degree radian area around the line connecting the transmitter and the destination on both sides. $B_{\mathrm{1}}$ and $B_{\mathrm{1}}^{\prime }$ are the corresponding intersection points. DRA is the sectorial region $S{B}_{\mathrm{1}}{B}_{\mathrm{1}}^{\prime }$ that is shown in Figure 2. Note that $SD$ is the angle bisector for this region. DRA is used in the beacon-less protocols, that is, IGF and BLR. The area of DRA is $S_{\mathrm{1}}^{\text{DR}}=\pi R^{\mathrm{2}}/\mathrm{6}$ .

(3) Reuleaux Triangle Area (RTA). It is constructed by a 60-degree radian area; the three arcs $\stackrel{⌢}{S{B}_{\mathrm{1}}}$ , $\stackrel{⌢}{S{B}_{\mathrm{1}}^{\prime }}$ , and $\stackrel{⌢}{B_{\mathrm{1}}{B}_{\mathrm{1}}^{\prime }}$ are determined by circles with radius R centered at $B_{\mathrm{1}}$ , $B_{\mathrm{1}}^{\prime }$ , and S, respectively, as shown in Figure 2. The area of RTA is $S_{\mathrm{1}}^{\text{RT}}=(\pi -\sqrt{\mathrm{3}})R^{\mathrm{2}}/\mathrm{2}$ .

3.2. Theoretical Analysis

In this subsection, we analyze the performance of the proposed uncoordinated cooperative forwarding scheme in detail. Recalling the definition of k -hop transmitter, we define $z_k$ is the location of the k-hop transmitter and $z_{\mathrm{0}}$ is the location of the source at origin in a 2D network. Let ${\phi }_k(v)$ be the probability that a node located at v (if exists) is a k-hop transmitter. In the rest of this section, we first obtain an analytical expression of ${\phi }_k(v)$ recursively for $k=\mathrm{1,2},\dots$ . On that basis, we obtain ${\varphi }_k(v)$ , $P_{\text{suc}}(D)$ , and $M(D)$ .

Now we start with $k=\mathrm{1}$ . A node at v is a 1-hop transmitter if and only if the following conditions are met:

• (i)

The node has received a packet from the source. This occurs with probability $g\left(v\right)$ , where $g\left(v\right)$ is the connection function. For the unit disk model, $g\left(v\right)=\mathrm{1}$ when $\mathrm{0}<‖v‖\le R$ and $g\left(v\right)=\mathrm{0}$ otherwise.

(ii)

The destination has not received the packet. This occurs with probability $\mathrm{1}-g\left(D\right)$ .

(iii)

The node is in the forwarding area. This occurs with probability $\tau (v,A_{\mathrm{1}})$ . $\tau (v,A_{\mathrm{1}})$ is an indicator function and is equal to 1 if $v\in A_{\mathrm{1}}$ . Otherwise, it equals 0. Define that $b(S,R)$ is a disk centered at S with radius R. $A_{\mathrm{1}}$ represents the location set of the 1-hop receivers in the forwarding area.

• (a)

  The constrain of MCA: $A_{\mathrm{1}}^{\text{MC}}=\{v\hspace{0.17em}|\hspace{0.17em}v\in \Gamma \cap v\in b(C_{\mathrm{1}},R/\mathrm{2})\}$ , where $C_{\mathrm{1}}$ represents the center of 1-hop MCA located at $(C_{\mathrm{1},x},C_{\mathrm{1},y})$ , where $C_{\mathrm{1},x}=R/\mathrm{2}$ and $C_{\mathrm{1},y}=0$ .

• (b)

  The constrain of DRA: $A_{\mathrm{1}}^{\text{DR}}=\{v\hspace{0.17em}|\hspace{0.17em}v\in \Gamma \cap v\in b(S,R)\cap -\pi /\mathrm{6}\le \angle vSD\le \pi /\mathrm{6}\}$ .

• (c)

  The constrain of RTA: $A_{\mathrm{1}}^{\text{RT}}=\{v\hspace{0.17em}|\hspace{0.17em}v\in \Gamma \cap v\in b(S_{\mathrm{1}},R)\cap v\in b(B_{\mathrm{1}},R)\cap v\in b(B_{\mathrm{1}}^{\prime },R)\}$ .

  The location of $B_{\mathrm{1}}$ is $(B_{\mathrm{1},x},B_{\mathrm{1},y})$ , where $B_{\mathrm{1},x}=\sqrt{\mathrm{3}}R/\mathrm{2}$ and $B_{\mathrm{1},y}=R/\mathrm{2}$ . The location of $B_{\mathrm{1}}^{\prime }$ is $(B_{\mathrm{1},x}^{\prime },B_{\mathrm{1},y}^{\prime })$ , where $B_{\mathrm{1},x}^{\prime }=\sqrt{\mathrm{3}}R/\mathrm{2}$ and $B_{\mathrm{1},y}^{\prime }=-R/\mathrm{2}$ .

(iv)

The node decides to forward the packet. This occurs with probability $P_f(v)$ .

(v)

The node is successful in the backoff competition and gets the opportunity to transmit. This occurs with probability $h(v)$ . The value of $h(v)$ will be analyzed shortly later.

Noting that the above five events are independent, it follows that

$$\begin{array}{cc}& {\phi }_{\mathrm{1}}\left(v\right)=g\left(v\right)\left(\mathrm{1}-g\left(D\right)\right)\tau \left(v,A_{\mathrm{1}}\right)P_f\left(v\right)h\left(v\right).\end{array}$$

(3)

Next we analyze $h(v)$ . Let $t^{\mathrm{\ast }}(v)$ be the (random) backoff timer of the node at v. Conditioned on $t^{\mathrm{\ast }}(v)=t$ , the node at v becomes successful in the backoff competition if all other nodes, which have received the packet from the source AND which are in the forwarding area $A_{\mathrm{1}}$ AND which decide to forward the packet, have a backoff timer greater than t. Note the backoff timer of the node at v depends on the location v and follows a uniform distribution $U(\mathrm{0,1}-P_f(v))$ , $f(t^{\mathrm{\ast }}(v))=\mathrm{1}/(\mathrm{1}-P_f\left(v\right))$ . With the increasing $‖v‖$ the maximum value of backoff timer $\mathrm{1}-P_f(v)$ increases. $\mathrm{Pr}\left(t^{\mathrm{\ast }}(u)<t\right)$ is the probability of the event that the node at u whose backoff timer is smaller than or equal to t. Because the backoff timer follows a uniform distribution $U(\mathrm{0,1}-P_f(u))$ , it readily follows that $\mathrm{Pr}\left(t^{\mathrm{\ast }}(u)<t\right)=t/(\mathrm{1}-P_f\left(u\right))$ .

Using the thinning theorem [15], the set of nodes, which receives the packet AND is in the forwarding area $A_{\mathrm{1}}$ AND decides to forward the packet AND has a backoff timer smaller than or equal to t, follows an inhomogeneous Poisson distribution with density $\rho g\left(u\right)\left(\mathrm{1}-g\left(D\right)\right)\tau (u,A_{\mathrm{1}})P_f(u)\mathrm{Pr}\left(t^{\mathrm{\ast }}(u)<t\right)$ . The number of such nodes follows an exponential distribution with mean ${\int }_{u\in A_{\mathrm{1}}}‍\rho g\left(u\right)\left(\mathrm{1}-g\left(D\right)\right)P_f(u)\mathrm{Pr}\left(t^{\mathrm{\ast }}(u)<t\right)du$ . The integral in different forwarding areas (i.e., MCA, DRA, and RTA) will be analyzed later. Therefore the probability that there is no such node is given by

$$\begin{array}{cc}& e^{-{\int }_{u\in A_{\mathrm{1}}}‍\rho g\left(u\right)\left(\mathrm{1}-g\left(D\right)\right)P_f\left(u\right)\mathrm{Pr}\left(t^{\mathrm{\ast }}\left(u\right)<t\right)du}.\end{array}$$

(4)

Further using the Slivnyak-Mecke theorem [15], the conditional event that there exists a node at v does not affect the above probability. Recall that the probability density function (pdf) of $t^{\mathrm{\ast }}(v)$ conditioned on the node at v is $f(t^{\mathrm{\ast }}(v))=\mathrm{1}/(\mathrm{1}-P_f\left(v\right))$ . Therefore using the total probability theorem

$$\begin{array}{ll}h\left(v\right)& ={{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}-P_f\left(v\right)}‍\frac{\mathrm{1}}{\mathrm{1}-P_f\left(v\right)}\\ & \hspace{1em}\hspace{1em}·e^{-{\int }_{u\in A_{\mathrm{1}}}‍\rho g\left(u\right)\left(\mathrm{1}-g\left(D\right)\right)P_f\left(u\right)\mathrm{Pr}\left(t^{\mathrm{\ast }}\left(u\right)<t\right)du}dt.\end{array}$$

(5)

Combining (3) and (5), it follows that

$$\begin{array}{ll}{\phi }_{\mathrm{1}}\left(v\right)& =g\left(v\right)\left(\mathrm{1}-g\left(D\right)\right)P_f\left(v\right)\tau \left(v,A_{\mathrm{1}}\right)\\ & \times {{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}-P_f\left(v\right)}‍\frac{\mathrm{1}}{\mathrm{1}-P_f\left(v\right)}\\ & \hspace{1em}\hspace{0.5em}·e^{-{\int }_{u\in A_{\mathrm{1}}}‍\rho g\left(u\right)\left(\mathrm{1}-g\left(D\right)\right)P_f\left(u\right)\mathrm{Pr}\left(t^{\mathrm{\ast }}\left(u\right)<t\right)du}dt.\end{array}$$

(6)

Finally, we analyze the integral in forwarding area. We divide the circular triangle into many small lattices $\Delta v$ approximated to $\Delta v\approx \Delta x\Delta y$ .

• (i)

For MCA, the lower and upper bound of $\Delta x$ are 0 and R; the lower bound and upper bound of $\Delta y$ are $-\sqrt{(R/\mathrm{2}{)}^{\mathrm{2}}-(R/\mathrm{2}-x{)}^{\mathrm{2}}}$ and $\sqrt{(R/\mathrm{2}{)}^{\mathrm{2}}-(R/\mathrm{2}-x{)}^{\mathrm{2}}}$ . The exponential term in (6) can be written as

$$\begin{array}{cc}& e^{-{\int }_{u\in A_{\mathrm{1}}}‍(·)du}=e^{-{\int }_{\mathrm{0}}^R‍{\int }_{-\sqrt{(R/\mathrm{2}{)}^{\mathrm{2}}-(R/\mathrm{2}-x{)}^{\mathrm{2}}}}^{\sqrt{(R/\mathrm{2}{)}^{\mathrm{2}}-(R/\mathrm{2}-x{)}^{\mathrm{2}}}}‍\left(·\right)dx\hspace{0.17em}dy}.\end{array}$$

(7)

(ii)

For DRA, the forwarding area is divided into two parts: in the first part the lower and upper bound of $\Delta x$ are 0 and $\sqrt{\mathrm{3}}R/\mathrm{2}$ ; the corresponding lower bound and upper bound of $\Delta y$ are $-x/\sqrt{\mathrm{3}}$ and $x/\sqrt{\mathrm{3}}$ ; in the second part the lower and upper bound of $\Delta x$ are $\sqrt{\mathrm{3}}R/\mathrm{2}$ and R; the lower bound and upper bound of $\Delta y$ are $-\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}$ and $\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}$ . The exponential term in (6) can be written as

$$\begin{array}{cc}& e^{-{\int }_{u\in A_{\mathrm{1}}}‍(·)du}=e^{-({\int }_{\mathrm{0}}^{\sqrt{\mathrm{3}}R/\mathrm{2}}‍{\int }_{-x/\sqrt{\mathrm{3}}}^{x/\sqrt{\mathrm{3}}}‍+{\int }_{\sqrt{\mathrm{3}}R/\mathrm{2}}^R‍{\int }_{-\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}}^{\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}}‍)(·)dx\hspace{0.17em}dy}.\end{array}$$

(8)

(iii)

For RTA, the forwarding area is divided into two parts: in the first part the lower and upper bound of $\Delta x$ are 0 and $\sqrt{\mathrm{3}}R/\mathrm{2}$ ; the lower bound and upper bound of $\Delta y$ are $R/\mathrm{2}-\sqrt{R^{\mathrm{2}}-(\sqrt{\mathrm{3}}R/\mathrm{2}-x{)}^{\mathrm{2}}}$ and $\sqrt{R^{\mathrm{2}}-(\sqrt{\mathrm{3}}R/\mathrm{2}-x{)}^{\mathrm{2}}}-R/\mathrm{2}$ ; in the second part the lower and upper bound of $\Delta x$ are $\sqrt{\mathrm{3}}R/\mathrm{2}$ and R; the lower bound and upper bound of $\Delta y$ are $-\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}$ and $\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}$ . The exponential term in (6) can be written as

$$\begin{array}{cc}& e^{-{\int }_{u\in A_{\mathrm{1}}}‍(·)du}=e^{-({\int }_{\mathrm{0}}^{\sqrt{\mathrm{3}}R/\mathrm{2}}‍{\int }_{R/\mathrm{2}-\sqrt{R^{\mathrm{2}}-(\sqrt{\mathrm{3}}R/\mathrm{2}-x{)}^{\mathrm{2}}}}^{\sqrt{R^{\mathrm{2}}-(\sqrt{\mathrm{3}}R/\mathrm{2}-x{)}^{\mathrm{2}}}-R/\mathrm{2}}‍+{\int }_{\sqrt{\mathrm{3}}R/\mathrm{2}}^R‍{\int }_{-\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}}^{\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}}‍)(·)dx\hspace{0.17em}dy}.\end{array}$$

(9)

Now we proceed to the case that k takes more general values other than 1. Let $z_k$ , $k>\mathrm{1}$ , be the random location of the k-hop transmitter. Assuming that the pdf of $z_k$ , that is, ${\phi }_k(z_k)$ , is known, we will derive the pdf of $z_{k+\mathrm{1}}$ conditioned on the fact that $z_k=\vartheta$ or simplify referred to as conditioned on $z_k$ . Note that according to the design of our uncoordinated cooperative forwarding scheme, when the node at $z_k$ transmits as the kth hop transmitter, the node essentially replaces the role of the source in the system. Therefore, it readily follows that

$$\begin{array}{l}{\phi }_{k+\mathrm{1}}\left(v\hspace{0.17em}|\hspace{0.17em}{z}_k\right)\\ \hspace{1em}=g\left(v-z_k\right)\left(\mathrm{1}-g\left(D-z_k\right)\right)P_f\left(v-z_k\right)\times \tau \left(v,A_{k+\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}·{{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}-P_f\left(v-z_k\right)}‍\frac{{}_{\mathrm{1}}}{{}^{\mathrm{1}-P_f\left(v-z_k\right)}}\\ \hspace{1em}\hspace{1em}\hspace{1em}·e^{-{\int }_{u\in A_{k+\mathrm{1}}}‍\rho g\left(u-z_k\right)\left(\mathrm{1}-g\left(D-z_k\right)\right)P_f\left(u-z_k\right)\mathrm{Pr}\left(t^{\mathrm{\ast }}\left(u-z_k\right)<t\right)du}dt,\end{array}$$

(10)

where $A_{k+\mathrm{1}}$ represents location set of the nodes in the $(k+\mathrm{1})$ -hop forwarding area in $xy$ -coordinate system, determined by $z_k$ and the location of the destination.

The difficulty of $(k+\mathrm{1})$ -hop forwarding area is the asymmetric integral area of x and y according to x-axis in $xy$ -coordinate system. Therefore, we construct $x^{\prime }{y}^{\prime }$ -coordinate system using the line $z_{k}D$ as $x^{\prime }$ -axis due to the fact that $(k+\mathrm{1})$ -hop forwarding area only depends on $z_k$ and D, as shown in Figure 3. Therefore, the transmitters $z_{\mathrm{1}},z_{\mathrm{2}},\dots ,z_k$ lead to different $x^{\prime }{y}^{\prime }$ -coordinate systems. Luckily, the integral area of $(k+\mathrm{1})$ -hop forwarding area in $x^{\prime }{y}^{\prime }$ -coordinate system is symmetric according to the $x^{\prime }$ -axis. Therefore, the lower and the upper bound of the integral in $x^{\prime }{y}^{\prime }$ -coordinate system can be obtained easily.

Figure 3

Coordinate transformation.

Based on the angle ${\theta }_k$ (which can be calculated easily according to the location of the source S, the location of the destination D, and $z_k$ ) between two coordinate systems, we can obtain the relationship between the two coordinate systems:

$$\begin{array}{cc}& x=x^{\prime }\cos {\theta }_k-y^{\prime }\sin {\theta }_k+x_k,\\ y=x^{\prime }\sin {\theta }_k+y^{\prime }\cos {\theta }_k+y_k,\end{array}$$

(11)

where x and y are the location value in $xy$ -coordinate system while $x^{\prime }$ and $y^{\prime }$ are the location value in $x^{\prime }{y}^{\prime }$ -coordinate system. Thus, the $(k+\mathrm{1})$ -hop forwarding area and the choice of $(k+\mathrm{1})$ -hop transmitter only depend on $z_k$ and D. Therefore, we can first calculate the lower and the upper bound of the integral in $x^{\prime }{y}^{\prime }$ -coordinate system and then transform them into $xy$ -coordinate system using (11).

Using the property that, for a fixed value of k, there can be at most one node which is a k-hop transmitter, the unconditional probability can be obtained as

$$\begin{array}{l}{\phi }_{k+\mathrm{1}}\left(v\right)\\ \hspace{0.5em}\hspace{0.5em}={{\displaystyle \int }}_{z_k\in A_k}‍{\phi }_{k+\mathrm{1}}\left(v\hspace{0.17em}|\hspace{0.17em}{z}_k\right){\phi }_k\left(z_k\right)\rho \hspace{0.17em}d{z}_k\\ \hspace{0.5em}\hspace{0.5em}={{\displaystyle \int }}_{z_{\mathrm{1}}\in A_{\mathrm{1}}}‍\cdots {{\displaystyle \int }}_{z_k\in A_k}‍{\phi }_{k+\mathrm{1}}\left(v\hspace{0.17em}|\hspace{0.17em}{z}_k\right)\\ \hspace{0.5em}\hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\times {\phi }_k\left(z_k\hspace{0.17em}|\hspace{0.17em}{z}_{k-\mathrm{1}}\right)\cdots {\phi }_{\mathrm{2}}\left(z_{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}{z}_{\mathrm{1}}\right)\\ \hspace{0.5em}\hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}·{\phi }_{\mathrm{1}}\left(z_{\mathrm{1}}\right){\rho }^{k}d{z}_{\mathrm{1}}\cdots d{z}_k.\end{array}$$

(12)

Multidimensional integral in (12) must be performed in the same coordinate system due to the location correlation between multihop transmitters. Therefore, we analyze the upper and lower bound of integral areas $A_{\mathrm{1}},A_{\mathrm{2}},\dots ,A_k$ in the same coordinate system ( $xy$ -coordinate); details are shown in Section 5.

The destination is a k-hop receiver if and only if it can directly receive from a $(k-\mathrm{1})$ -hop transmitter. Note that the term $\mathrm{1}-g\left(D-z_k\right)$ in ${\phi }_{k+\mathrm{1}}\left(v\hspace{0.17em}|\hspace{0.17em}{z}_k\right)$ allows us to rule out the possibility that transmission continues after the packet has reached its destination. Further note that, for any fixed value of k, there is at most one node that can be a k-hop transmitter. Based on the above observations, it follows that when $k>\mathrm{1}$

$$\begin{array}{cc}& {\varphi }_k\left(D\right)={{\displaystyle \int }}_{v\in b(D,R)}‍{\phi }_{k-\mathrm{1}}\left(v\right)\rho g\left(D-v\right)dv\end{array}$$

(13)

and ${\varphi }_{\mathrm{1}}(D)=g\left(D\right)$ .

Equation (13), together with (1), allows us to determine the transmission success probability $P_{\text{suc}}(D)={\sum }_{k=\mathrm{1}}^{\infty }‍{\varphi }_k(D)$ and the expected number of transmissions required to reach the destination $E[M(D)]={\sum }_{k=\mathrm{1}}^{\infty }‍k{\varphi }_k(D)$ .

3.3. Special Case

When both forwarding probability function $P_f(v)$ and backoff function $h(v)$ are independent of node location v, denoted as $P_f$ and h, respectively, the integrals in (6) can be converted into multiplying the areas of corresponding integral domains. The corresponding areas $S_{\mathrm{1}}^{\text{MC}}$ , $S_{\mathrm{1}}^{\text{DR}}$ , and $S_{\mathrm{1}}^{\text{RT}}$ can be calculated according to Section 3.1. Consider

$$\begin{array}{ll}{\phi }_{\mathrm{1}}\left(v\right)& =g\left(v\right)\left(\mathrm{1}-g\left(D\right)\right)\tau \left(v,A_{\mathrm{1}}\right)\\ & \times P_f{{\displaystyle \int }}_{\mathrm{0}}^{\infty }‍e^{-\rho P_f\mathrm{Pr}\left(t^{\mathrm{\ast }}<t\right)S_{\mathrm{1}}}f\left(t\right)dt,\end{array}$$

(14)

where $f(t)$ is the pdf of the backoff time which is independent of the node location.

Similarly, the probability that the node at v is the $(k+\mathrm{1})$ -hop transmitter conditioned on the k-hop transmitter at $z_k$ can be expressed as

$$\begin{array}{ll}{\phi }_{k+\mathrm{1}}\left(v\hspace{0.17em}|\hspace{0.17em}{z}_k\right)& =g\left(v-z_k\right)\left(\mathrm{1}-g\left(D-z_k\right)\right)\tau \left(v,A_{k+\mathrm{1}}\right)\\ & \times P_f{{\displaystyle \int }}_{\mathrm{0}}^{\infty }‍e^{-\rho P_f\mathrm{Pr}\left(t^{\mathrm{\ast }}<t\right)S_k}f\left(t\right)dt.\end{array}$$

(15)

Then, using (12), together with (13) and (1), we can obtain the transmission success probability $P_{\text{suc}}(D)$ and the expected number of transmissions required to reach the destination $E[M(D)]$ in the special case.

3.4. Design of Forwarding Probability Function

As manifested in (13), (1), and our discussion in Sections 1 and 3.1, the forwarding probability function $P_f(x)$ and forwarding areas play important roles in determining the performance of the forwarding scheme. In this subsection we analyze the design of the optimal forwarding probability function for the optimization problem in (2).

The analytical expressions for $P_{\text{suc}}(D)$ and $E[M(D)]$ in their present form do not allow us to readily analyze the optimal functional form of $P_f(x)$ that solves the optimization problem in (2). However, for particular forms of $P_f(x)$ , for example, $P_f(x)=c$ and $P_f(x)=ax$ , the optimum parameters for $P_f(x)$ can be found using the method of Lagrange multipliers and solved numerically.

In the following analysis, we consider the simple case that $P_f(x)=c$ as an example. The optimization problem in (2) now reduces to find the value of $c_{\text{opt}}$ :

$$\begin{array}{l}{c}_{\text{opt}}=\underset{P_f\left(x\right)=c}{\arg \hspace{0.17em}\min }\hspace{0.17em}E\left[M\left(D\right)\right]\\ \text{s}.\text{t}.\hspace{0.17em}\hspace{0.17em}{P}_{\text{suc}}\left(D\right)\ge \mathrm{1}-\varepsilon .\end{array}$$

(16)

The Lagrangian of the optimization problem can be written as

$$\begin{array}{cc}& \ell \left(P_f\left(x\right)=c,\eta \right)=E\left[M\left(D\right)\right]+\eta \left(\mathrm{1}-\varepsilon -P_{\text{suc}}\left(D\right)\right).\end{array}$$

(17)

The optimum value of c can then be obtained by setting the partial derivative of $\ell (P_f(x)=c,\eta )$ with regard to c and with regard to η to $\mathrm{0}$ , respectively, and solving the equations. However in this paper, we resort to a simpler method by using numerical simulation. Thus, we can find that both $E[M(D)]$ and $P_{\text{suc}}(D)$ are nondecreasing function of c. Based on the observation, it follows that the optimum value of c is the solution to the equation $P_{\text{suc}}(D)=\mathrm{1}-\varepsilon$ , which can be found numerically.

4. Simulation

In this section, we use both simulations and numerical results to establish the performance of the proposed uncoordinated cooperative forwarding scheme and provide some intuitively digestible results. Considering a 2D axis, nodes apart from source and destination are deployed following a homogeneous density $\rho =2$ /m² [14]. The ratio γ of the distance between source and destination L to the transmission range R varies from 1 to 4. The backoff time follows the exponential distribution with rate $\lambda =1$ . The lower bound of successful transmission probability $P_{\text{suc}}^{\text{lower}}(D)$ is 0.94. The limit of maximum number of hops $K_m$ is 20. We build the random process by Monte Carlo method in Matlab to capture the realistic properties of the real wireless networks (e.g., producing random nodes’ locations according to the simulation parameters). Moreover, each point in the figures is the average value obtained from 50000 random simulations.

The following simulations first compare the performance of uncoordinated cooperative forwarding schemes, measured in the expected number of transmissions $E[M(D)]$ , using three different forwarding probability functions, that is, $P_f(x)=c$ , $P_f(x)=a‖x‖$ , and

$$\begin{array}{cc}& P_f\left(x\right)=\left\{\begin{array}{cc}\mathrm{0},\hfill & \mathrm{0}\le ‖x‖<bR,\hfill \\ \mathrm{1},\hfill & bR\le ‖x‖\le \mathrm{1}.\hfill \end{array}\right.\end{array}$$

(18)

In Figures 4–9, the three cases are labeled as Cases 1, 2, and 3, respectively. Then, we also provide the expected number of transmissions using some existing forwarding algorithms; for example, consider the following.

Figure 4

Probability that the destination at $\gamma R$ is a k-hop receiver using constant forwarding probability in MCA.

Figure 5

Probability that the destination at $\gamma R$ is a k-hop receiver using constant forwarding probability in DRA.

Figure 6

Probability that the destination at $\gamma R$ is a k-hop receiver using constant forwarding probability in RTA.

Figure 7

Expected number of transmissions using four forwarding functions under three forwarding areas.

Figure 8

Expected number of transmissions using three forwarding areas under three forwarding functions.

Figure 9

Expected number of transmissions using different forwarding algorithms.

(1) The shortest path routing [8], which is labeled as SP: obviously, the shortest path algorithm needs global knowledge of the network and assumes all nodes would like to forward a packet. It can serve as a benchmark for the best performance here.

(2) The greedy forwarding algorithm, which is labeled as GF: it chooses the node, which has received a copy of the packet and would like to forward, closest to the destination in each hop as the forwarding node. Greedy forwarding algorithm is comparatively easy to implement; however it relies on coordination between nodes to determine the set of nodes which have received packet and would like to forward and to determine which node among them is closest to the destination.

(3) The random selection forwarding algorithm, which is labeled as RS: it chooses one of the nodes randomly, which have received a copy of the packet and would like to forward in each hop. The coordination is required as well in order to avoid hidden node problem.

(4) The user-fair forwarding algorithm: the only one difference between the user-fair forwarding algorithm and our proposed algorithm is no forwarding area constraint.

The values of a, b, and c in Cases 1, 2, and 3 are determined assuming that $\gamma =4$ and $P_{\text{suc}}(D)=\mathrm{0.94}$ . Because the successful transmission probability increases with the decreasing γ which has been discussed in Section 3.4, the successful transmission probability is undoubtedly not less than 0.94 when γ varies from 1 to 4 conditioned on the value of a, b, and c corresponding to $P_{\text{suc}}(D)=\mathrm{0.94}$ , under the same regulated forwarding area and forwarding probability functions (listed in Table 1). With the same or similar successful transmission probability $P_{\text{suc}}(D)$ , we only need to compare the expected number of transmissions under three forwarding probability functions. Table 1 also justifies that the forwarding probability should be assigned higher to DRA which is of the smallest area value.

Table 1

Optimal values of c, a, and b conditioned on $$P_{\text{suc}}(D)=\mathrm{1}-\epsilon =\mathrm{0.94}$$ .

	MCA	DRA	RTA
c	0.5	0.7	0.53
a	0.33	0.3	0.32
b	0.62	0.59	0.67

The probability that the destination can be reached in k transmissions using constant forwarding probability (Case 1) under three forwarding areas (MCA, DRA, and RTA) is shown in Figures 4, 5, and 6. Unsurprisingly, there are slight discrepancies between the analytical results and the corresponding simulation results. The analytical results are always larger than the corresponding simulation results. The discrepancies are attributable to the boundary effect. For any k-hop transmitter which is close to the border, the corresponding forwarding area may be located partially outside the network area, which causes an error in computing ${\varphi }_k(D)$ . This effect is the boundary effect. The impact of the boundary effect will reduce as the network area becomes larger compared to R. The figures also show that the discrepancy between the analytical result and simulation result in MCA is larger than that of DRA or RTA due to the condition that the area of MCA is maximum among the three forwarding areas. Moreover, in the figures there is a spike for $k=2$ . That is because (1) when $\gamma >\mathrm{1}$ (i.e., $L>R$ ), the probability that the destination is 1-hop receiver is zero (i.e., ${\varphi }_{\mathrm{1}}(D)=0$ ), and (2) when L is slightly larger than R, it has a high probability that the destination is a 2-hop receiver. Thus, the relatively big difference between the value of ${\varphi }_{\mathrm{1}}(D)$ equaling to 0 and ${\varphi }_{\mathrm{2}}(D)$ approaching 1 given that L is slightly larger than R results in a spike for $k=2$ .

Then, we compare the expected number of transmissions using forwarding functions (Cases 1, 2, and 3 and SP) under three forwarding areas (MCA, DRA, and RTA). From Figure 7, we can see that all the three forwarding probability functions (Cases 1, 2, and 3) perform well. Interestingly, Case 3 where $P_f(x)$ is set as a step function provides the best performance among all three cases, as shown in Figure 7. This finding is consistent with our earlier work in [4] and it is part of our future work to dig into the findings and provide analytical support for the optimum choice of $P_f(x)$ .

From Figure 8, the expected number of transmission is positively related to the area of MCA, DRA, and RTA. But under the step function, the difference is negligibly small especially when γ is small, which verifies the benefit of the step function.

Finally, Figure 9 gives the comparison of the expected number of transmissions of our proposed algorithm with SP, GF, and RS. Due to the page limit, we only give the results using the linear forwarding probability function (Case 2). From Figure 9, we can see that the proposed uncoordinated scheme has a similar performance as the coordinated GF and SP algorithm but saving a large amount of coordination overhead. Moreover, recall that the user-fair forwarding algorithm is an uncoordinated forwarding scheme. Without the forwarding area constraint, it is likely that the transmission collision happens due to the hidden node problem. Therefore, it is hard to guarantee a high successful transmission probability under the same scenario parameters. When $\gamma =4$ and $\rho =2$ /m², the successful transmission probability only reaches 0.15 due to the transmission collision. Therefore, it cannot be compared with other algorithms under the same successful transmission probability constraint.

5. Conclusion and Future Work

This paper proposed an uncoordinated cooperative forwarding scheme for 2D highly dynamic networks. The performance of the proposed scheme, measured in terms of the transmission success probability and the expected number of transmissions, is analyzed. On that basis, design of the optimum forwarding probability function is discussed. Given a particular form of the forwarding probability function, our analysis can be used to numerically determine the optimum parameter settings for the forwarding probability function that minimizes the expected number of transmissions while meeting the performance target on the transmission success probability. Furthermore, the performance of the uncoordinated cooperative forwarding scheme employing three commonly used forwarding probability functions, that is, the constant forwarding probability, the linear forwarding probability, and the step function forwarding probability, is compared. Our preliminary study appears to suggest that, by choosing the forwarding probability function to be a step function, the best performance can be achieved. This finding is consistent with the work in [4] studying a two-hop scenario in two-dimensional networks where the source and the destination are separated by at most two hops. It is part of our future work plan to dig into the result and provide analytical support for the optimum choice of $P_f(x)$ .