Sage Journals: Discover world-class research

Abstract

With GPS devices spreading, more mobile nodes are guided by the navigation systems to select better paths. The performance of mobile networks can be improved with the navigation information in nodes. In this paper, we propose a trajectory-based network coding (TBNC) method to disseminate data in mobile wireless sensor network (MWSN). It is designed according to the characteristics of MWSN and is appropriate for the mobile nodes that share anonymously its GPS pretrajectory for the higher bandwidth. Data are disseminated in the topology that is predicted on the basis of the trajectory information. Network coding is used to adapt for the dynamics velocity of mobile nodes. Simulation results show that TBNC is able to cut down 1/2 overhead messages of PRoPHET when mobile nodes share GPS trajectory. It improves the reliability and scalability of MWSN.

1. Introduction

Wireless sensor network (WSN) is composed of a large number of sensor nodes, which collect the information of surrounding changes. Many researches on WSN are based on the assumption that the sensor node is static. However, the sensor node is mobile in many applications of WSN, such as target tracking, traffic monitoring, urban microclimate, and disaster monitoring [1]. Mobile WSN (MWSN) can simply be defined as the WSN in which the sensor nodes are mobile. It is a wireless ad hoc network that consists of many sensor nodes communicating with each other [2]. The nodes are either equipped with motors for active mobility or attached to mobile objects for passive mobility [3]. The nodes move so fast, and it is difficult to find a path between a pair of nodes using ordinary WSN routing protocol [4].

Mobile nodes can exchange data with each other through Ad-hoc communication networks. But the ordinary ad hoc routing protocols will produce a huge number of overhead messages, which can consume too much energy and add the network load [5]. With GPS devices spreading, more and more mobile nodes are guided by the navigation systems. The prepath and destination of every mobile node are created and stored in its navigation system [6]. The trajectory of mobile node is able to be predicted and shared in the networks. So every node can also predict the topology change of networks according to the pre-path and velocity of other mobile nodes. It doesn't need to send data to all nodes using broadcast such as Epidemic [7] and only forwards data to the nodes moving at the direction of destination.

The researchers have already paid attention to the works applying GPS devices to WSN [8–12]. Many applications of WSNs require the positions where data was sensed, and the former researches are only focused on locating the sensor node in GPS device. These proposed schemes do not require GPS on all sensor nodes, taking into the consideration that GPS units increase the costs of sensor nodes at that time. In this case, only a fraction of the nodes has GPS units, and every node transmits its coordinates to the rest of the sensors to localize themselves [13]. Nowadays, the GPS units are popular to the mobile devices, and they are upgraded from the positioning to navigation. Our work uses the pre-trajectory of mobile nodes to improve the routing protocol of MWSN, and it is different from the researches just positioning nodes.

In this paper, we present a trajectory-based network coding (TBNC) method to disseminate data in MWSN. Mobile nodes are navigated by GPS devices and share their navigation information with the others. Data are divided into short fixed-size blocks in source node and disseminated to the other mobile nodes. The source implements network coding and sends the coding blocks to the destination according to the pretrajectory of other nodes. The blocks are recoded by the nodes on the cross roads. The experiments show that TBNC is able to reduce overhead messages, and enhance the reliability of transmission. TBNC is appropriate for the MWSN systems that mobile nodes are navigated by GPS devices.

The remainder of this paper is organized as follows. In Section 2, we discuss the related work. Section 3 presents the description and implementation of the TBNC. The evaluation and analysis of the TBNC are shown in Section 4. The paper is concluded in Section 5.

2. Related Works

The GPS devices are only used by mobile nodes of WSN to determinate their locations in many studies. Parts of mobile nodes are equipped with GPS devices to get their coordinates. GPS-equipped node is called a landmark, anchor, or seed [13]. It helps the other nodes without GPS devices to estimate their positions. The landmark moves throughout WSN providing sensor nodes with its location [14]. It either transmits its coordinates to help the other nodes to estimate their positions or receives messages sent by the other nodes and estimates their positions. In recent years, more and more studies have looked at positioning the nodes without any GPS devices in WSN [15, 16]. LIS [17] is a novel localization algorithm. As nodes run a fuzzy logic algorithm for processing the information, it was considered that nodes were provided with some kind of intelligence. They can implement in the area where GPS does not work correctly, such as the interior of buildings [18, 19]. GPS devices are not necessary to determin the location of mobile nodes.

A few studies have been attracted on utilizing GPS information for VANETs [20]. More and more vehicles are equipped with satellite navigation systems. With increased usage of smart phones like Apple iPhone or Android phones, navigation systems based on smart phones are popular. Vehicle trajectory information has become a valuable input for data forwarding. In [21], a protocol is proposed to enable efficient multihop routing capabilities. It fully supports two way communications between mobile vehicles and APs. Vehicular mobility is predicted from the information offered by the navigation system in terms of final destination and path. TSF [22] considers a reliable, efficient APs-to-vehicles data delivery by minimizing the packet delivery delay. Data delivery is performed through the computation of a target point based on the destination vehicle's trajectory information. Roadside APs can be selected as relays where destination vehicle is expected to pass by. Selecting AP optimally minimize the packet delivery delay. TBD [23] utilizes vehicle trajectory information to improve communication delay and delivery probability for vehicles-to-APs destination communications. A delay model of packets routing along roads is set up. The path with minimum delay can be found with the help of the real-time traffic condition information. VANETs can be regarded as a class of MWSN. Our work will extend the successful application of GPS trajectory in VANETs to MWSN.

It is not reliable to forward data among mobile nodes. Improving the reliability is another requirement of WMSN. Network coding has been proven to be a promising approach that can improve the reliability of communication and reduce overhead by combining packets [24]. The technique is well-suited for WSNs due to the broadcast nature of their communications. In [25], network coding is combined with multipath routing to deliver the message. The advantage of the algorithm is that the same reliability is guaranteed with significantly reduced energy consumption. In [26], an adaptive network coding is proposed to enhance reliability in WSN by considering redundancy. However, the algorithm is not suitable for the broadcast scenario. AdapCode [27] is proposed to reduce broadcast traffic in the process of code updates for the reliable data dissemination. In [28], a competitive approach to network coding is proposed to reduce the network traffic and prolong the lifetime of the network. In [29], network coding algorithm is combined with duty-cycling for saving energy in wireless sensor networks. In former researches, network coding is combined with few algorithms for MWSN. They achieve the improvement on reliability, reduce overhead, and save energy. Routing data according to the pre-trajectory can also improve the reliability. In the following work, we will combine network coding with the pre-trajectory of mobile nodes for the improvement of the scalability and reliability of MWSN.

3. Implementing TBNC on MWSN

In this section, we present the method of TBNC and its implementation on MWSN. It firstly composes navigating information and network coding in MWSN.

3.1. Conditions and Assumptions

In our work, mobile nodes have to satisfy the three restrictive conditions while using TBNC. (1)

The movements of nodes are constrained to roads. If ground node can go to any location without regard to the objects on surface, it is usually low-speed. Node's high-speed movement has a great influence on data dissemination of WSN, and it is also a characteristic of mobile WSN. The road is generically paved for the purpose of enhancing the speed of transportation. High-speed nodes on the ground usually move along the roads. Mobile nodes can go to anywhere in the specific area according to the definition of MWSN, but they only move along the roads in many applications of MWSN such as VANET, mobile IP, and passive localization. It is reasonable to constrain the high-speed nodes on roads in former applications.

(2)

Mobile node installs GPS receiver for navigation. GPS became a very popular technology after being adopted for navigation. Many vehicles have installed GPS receivers. Navigation systems are also used widely in smart phones like Apple iPhone or Android phones. Navigation system extends GPS to the usage of ordinary passenger. The interface of GPS has been reserved in the embedded systems such as ARM, PowerPC, and MIPS. New products will be developed easily to support the functions of position and navigation. It is also reasonable to navigate for mobile node using GPS.

(3)

Mobile node shares its GPS navigation data to the others for reducing the delay of data dissemination. Passengers do not mind to disclose their destinations to the providers of transportation. Similarly, mobile node can share anonymously its pre-path for the higher bandwidth. The node must inform the other nodes near the path to prepare data dissemination and make sure that the navigation data is only used in communications. The information opened by the node is similar to P2P mode. The success of P2P software indicates that network users accept to share its IDs and routes to the others. User privacy can't be invaded when nodes share their pre-path. It is also reasonable to share the GPS navigation data in MWSN.

All of the former conditions are reasonable in part of applications of MWSN. In order to construct the problem model, we give the following two assumptions. (1)

All of nodes remain in a uniform linear motion. When the nodes i and j move in a same straight line with constant velocity, the packet can directly be transmit between them if their distance satisfies

\begin{matrix} \max (| {\vec{d}}_{i j} (t) |, | {\vec{d}}_{i j} (t + t_{s}) |) \leq R, \\ {\vec{d}}_{i j} (t + t_{s}) = {\vec{d}}_{i j} (t) + ({\vec{v}}_{i} - {\vec{v}}_{j}) * t_{s}, \end{matrix}

(1)

where R is the coverage radius of the node, ${\vec{d}}_{i j} (t)$ is the distance vector between nodes i and j at time t, $| {\vec{d}}_{i j} (t) |$ is the norm of ${\vec{d}}_{i j} (t)$ , ${\vec{v}}_{i}$ and ${\vec{v}}_{j}$ are the velocities of nodes i and j. $t_{s}$ is the time to send packet from i to j and can be computed by

\begin{matrix} t_{s} = \frac{L_{p}}{B}, \end{matrix}

(2)

where $L_{p}$ is the maximum length of the packets transmitting among nodes and B is the bandwidth between i and j.

(2)

There are enough mobile nodes as the relay to forward data between the source and destination. We define the direction of data destination as positive and reverse direction as negative. There may be many nodes within the radio range of node. The node selects the farthest node in positive direction as its next hop. While data are forwarded completely from i to next hop, the distance between them $D (i, t + t_{s})$ is computed as

\begin{matrix} D (i, t + t_{s}) = \overset{n_{i}}{\max_{j = 1}} (| {\vec{d}}_{i j} (t + t_{s}) | * O (i, j)), \end{matrix}

(3)

where $n_{i}$ is the number of nodes within the radio range of i and $O (i, j)$ is the orientation of the node j in i. $O (i, j)$ can be denoted as

\begin{matrix} O (i, j) = {\begin{cases} + 1, & {\vec{d}}_{i j} (t + t_{s}) > 0, \\ - 1, & {\vec{d}}_{i j} (t + t_{s}) < 0, \\ 0, & \min (| {\vec{d}}_{i j} (t + t_{s}) |, | {\vec{d}}_{i j} (t + t_{s}) |) > R . \end{cases} \end{matrix}

(4)

The nodes continue to move when data are forwarded. The length of hop i can be computed by

\begin{matrix} l (i) = {\vec{v}}_{i} * t_{s} + D (i, t) . \end{matrix}

(5)

If data can arrive at destination through n hop, the distance from the source to destination L can be denoted as

\begin{matrix} L = \sum_{i = 1}^{n} l (i) . \end{matrix}

(6)

The former two assumptions are not reasonable in any of the applications of MWSN. The following section will give the method to put away the assumptions in TBNC.

3.2. TBNC

In fact, the movement of any node is not uniform. Its velocity changes in a region. The node is only able to estimate the approximate location of neighbors. Neighbors may move out of their radio range while forwarding data. It is unreliable to forward data between two nodes moving with unpredictable velocity. TBNC forwards encoded data to multiple neighbors according to their trajectories. It improves the reliability of data dissemination using linear network coding.

3.2.1. Network Coding in the Source

Data are encoded in the source. K is its local encoding matrix with $υ \times ω$ dimension. ω is the number of rows in matrix K and also the dimension of encoding vectors. In order to reduce the complexity of decoding operation as ω is taken a fixed value. υ is the number of columns in matrix K and also the number of encoding vectors. υ can be computed by

\begin{matrix} υ = int (ω * β * \frac{Δ v + 1}{Q} * 2^{C}), \end{matrix}

(7)

where

int ()

is the integral function, ω is the number of rows in matrix K, β is the constant adjusting υ to proper value,

Δ v

is the velocity standard deviation of mobile nodes on the road, Q is the nodes density on this road, C is the pause frequency of data transmission, and

Δ v

and Q are computed by the following equations:

\begin{matrix} Δ v = \sqrt{\frac{1}{N} * \sum_{i = 1}^{N} {(v_{i} - \bar{v})}^{2}}, \\ Q = \frac{N}{(L / R)}, \end{matrix}

(8)

where N is the number of mobile nodes and

\bar{v}

is the average speed of mobile nodes on the road. If the distance between the node and its next hop is greater than the coverage radius R, data transmission will be paused until a node is in positive direction. C is the number of the pauses during a packet delivery to destination. The parameter C is estimated according to the detection fixed on the roadside (such as speed camera, traffic monitoring). Consider

\begin{matrix} C = {\begin{cases} C + 1, & if \frac{R}{\bar{v}} < Δ t < T_{m}, C < 5, \\ C, & if \frac{R}{\bar{v}} < Δ t < T_{m}, C > 5, \\ \infty, & if Δ t > T_{m}, \end{cases} \end{matrix}

(9)

where

Δ t

is the interval time between the two mobile nodes passing the detection. The available maximum value of C is 5.

T_{m}

is the specified maximum value of

Δ t

. If

Δ t > T_{m}

C = + \infty

, and

υ = + \infty

, it represents that the path cannot reach the destination, and data transmission and encoding are terminated.

A row vector contains ω consecutive data blocks sent by the same source. The blocks IDs in the vector i are from $(i - 1) * ω + 1$ to $i * ω$ , where $i = 1,2, 3, \dots$ . All of the elements in the matrix K originate a pseudorandom sequence produced according to the vehicle ID. $Seq k$ denotes the pseudorandom sequence and is given by

\begin{matrix} Seq k_{i} = \frac{S k_{i}}{υ}, i = 1,2, 3, \dots, \\ S k_{i} = (S k_{i - 2} + S k_{i - 1}) \mod υ, \\ S k_{- 1} = {ID}_{source} \mod υ, \\ S k_{0} = {ID}_{destination} \mod υ, \end{matrix}

(10)

where mod is the modulus operator and ID is the unique identification of the mobile node. The element

k_{i j}

in the matrix K is gotten from Seqk and given by

\begin{matrix} k_{i j} = Seq k_{i * ω + j} . \end{matrix}

(11)

The local coding matrix K with

υ \times ω

dimension can be denoted as follows:

\begin{array}{l} k = [\begin{array}{l} k_{11} & k_{12} & \dots & k_{1 ω} \\ k_{21} & k_{22} & \dots & k_{2 ω} \\ \dots & \dots & \dots & \dots \\ k_{ʊ 1} & k_{ʊ 2} & \dots & k_{ʊ ω} \end{array}] \\ = [\begin{array}{l} {Seqk}_{1} & {Seqk}_{2} & \dots & {Seqk}_{ω} \\ {Seqk}_{ω + 1} & {Seqk}_{ω + 2} & \dots & {Seqk}_{2 * ω} \\ \dots & \dots & \dots & \dots \\ {Seqk}_{(ʊ - 1) * ω + 1} & {Seqk}_{(ʊ - 1) (ω + 2)} & \dots & {Seqk}_{ʊ * ω} \end{array}], \end{array}

(12)

where ω data blocks to the same destination are assembled and encoded together in the source. If

x_{i}

denotes data blocks i, ω data blocks are denoted by a data vector X:

\begin{matrix} X = (x_{1}, x_{2}, \dots, x_{ω}) . \end{matrix}

(13)

Implementing linear network coding on the blocks from the source is formalized as computing the product of two matrixes. It is denoted by

\begin{matrix} Y = K \cdot X^{T} . \end{matrix}

(14)

The encoded vector is denoted by Y, and its dimension is υ. The elements in Y can be computed by

\begin{matrix} y_{i} = \sum_{j = 1}^{ω} k_{i j} * x_{j} = \sum_{j = 1}^{ω} Seq k_{i * ω + j} * x_{j}, \end{matrix}

(15)

where υ encoded elements in Y are sent out from the source.

3.2.2. Recoding on the Cross Road

If the angle between destination and next hop directions is less than 90 degrees, the forwarding direction is positive. When data are forwarded to the mobile nodes on the cross road, there is more than one positive direction, as depicted in Figure 1. The node may select multiple next hops on different roads to forward data. It must measure the road status (such as the nodes flow and direction) to decide which nodes are next hops. The nodes flow on the road is computed by

\begin{matrix} f = \frac{N}{(Δ v + 2^{C}) * L} . \end{matrix}

(16)

f > 1 / R

, the nodes on the road can deliver data to destination.

Figure 1

Forwarding data on the cross road.

The angle α between destination and next hop directions is computed by

\begin{matrix} α = | arccos (\frac{Δ l a_{dst} * Δ l a_{nxt} + Δ l o_{dst} * Δ l o_{nxt}}{\sqrt{Δ {la}_{dst}^{2} + Δ {lo}_{dst}^{2}} * \sqrt{Δ l a_{nxt}^{2} + Δ l o_{nxt}^{2}}}) |, \\ Δ l a_{dst} = l a_{dst} - l a_{0}; Δ l o_{dst} = l o_{dst} - l o_{0}, \\ Δ l a_{nxt} = l a_{nxt} - l a_{0}; Δ l o_{nxt} = l o_{nxt} - l o_{0}, \end{matrix}

(17)

where

l a_{0}

and

l o_{0}

are the latitude and longitude of mobile node position;

l a_{dst}

and

l o_{dst}

are the destination positions;

l a_{nxt}

and

l o_{nxt}

are the position of next hop.

We suppose that $α_{1}$ and $α_{2}$ are the angles between destination and next hops in the directions 1 and 2, respectively, and $f_{1}$ and $f_{2}$ are the nodes flows in the directions 1 and 2, respectively. While both $α_{1}$ and $α_{2}$ are less than 90 degrees, the next hops are selected as the following two rules: (1)

if $(α_{2} - α_{1}) > 6 0^{\circ}$ or ( $3 0^{\circ} \leq (α_{2} - α_{1}) \leq 6 0^{\circ}$ and $f_{1} \geq 1 / R$ ), data are only forwarded to the next hops in the direction 1;

(2)

if ( $3 0^{\circ} \leq (α_{2} - α_{1}) \leq 6 0^{\circ}$ and $f_{1} < 1 / R$ ) or $0^{\circ} \leq (α_{2} - α_{1}) < 3 0^{\circ}$ , data are recoded and forward to the next hops in the directions 1 and 2, respectively.

The encoded vector Y is recoded with the global recoding matrix, denoted by P. The matrix P is a lower triangular matrix with $μ \times υ$ dimension, and its number of rows $μ$ is given by

\begin{matrix} μ = int (υ * \frac{γ * (α_{1} + α_{2})}{(α_{1} f_{1} + α_{2} f_{2}) * R}), \end{matrix}

(18)

where

γ

is the constant adjusting

μ

to proper value and

γ > 2

. If the value of

f_{1}

f_{2}

is more than

1 / R

, it is replaced by

1 / R

in (18).

The matrix P is unique and constant to the mobile node, need not be transferred to destinations. All of elements in P originate another pseudo-random sequence. $Seq p$ denotes the pseudo-random sequence and is given by

\begin{matrix} Seq p_{i} = \frac{(\arcsin S p_{i})}{π} + 0.5, i = 1,2, 3, \dots, \\ S p_{i} = 1 - 2 * {S p}_{i - 1}^{2}, S p_{i - 1} \in (- 1,0.5) \cup (0.5,1), \end{matrix}

(19)

where

S p_{i}

is an intermediate variable to produce the sequence.

S p_{0}

can be designated by the administrator, and its default value is equal to 0.3.

S p_{- 1} = 0

. The element

p_{i j}

in the matrix P is gotten from

Seq p

and given by

\begin{matrix} p_{i j} = Seq p_{a}; \\ a = {\begin{cases} - 1 & j > i; \\ j + \sum_{k = 1}^{i - 1} k & j \leq i . \end{cases} \end{matrix}

(20)

Implementing recoding on the coding blocks is formalized as computing the product of matrixes. It is denoted by

\begin{matrix} Z = P \cdot Y^{T} = P \cdot {(K \cdot X^{T})}^{T} . \end{matrix}

(21)

If mobile node in the range of the cross road needs forward data to multiple directions, it will buffer the encoded data, then recode them for delivery. We suppose that u is the number of buffered and recoded blocks and μ is its maximum number. $u_{1}$ and $u_{2}$ are the numbers of blocks sent to directions 1 and 2, respectively. $u = u_{1} + u_{2}$ . Pr is the proportion of the recoded blocks in two directions and can be computed by

\begin{matrix} Pr = \frac{u_{1}}{u_{2}} = (2^{(α_{2} - α_{1}) / 30}) * \frac{f_{1}}{f_{2}} . \end{matrix}

(22)

The node clears the buffered data until it moves out of the range of the cross road.

3.3. Implementing on MWSN

Mobile node presets the destination and automatically or manually pre-sets the path on GPS navigation. It shares the information of prepath to other nodes for the improvement of data dissemination. Then, the process of mobile node is formally shown in Figure 2. In this figure, initial data represent the uncoded data in the source nodes. If the number of next hops is more than 1, the mobile node is passing on the cross road and recoding the coded data for forwarding to different directions. Network coding algorithm on Figure 2 is described in Algorithm 1, and the recoding algorithm on Figure 2 is described in Algorithm 2.

Algorithm 1: Formal description of network coding on the source nodes.

Compute υ with (7)

$S k_{- 1} = {ID}_{source}$ mod υ, $S k_{0} = {ID}_{destination}$ mod υ

//Compute the local coding matrix K:

For $i = 1$ to υ

For $j = 1$ to ω

$S k = (S k_{- 1} + S k_{0})$ mod υ;

$S k_{- 1} = S k_{0}$ ; $S k_{0} = S k$ ;

$k [i, j] = S k / υ$ ;

//Compute the encoded vector Y:

For $i = 1$ to υ

$sum = 0$ ;

For $j = 1$ to ω

$sum = sum + k [i, j] * X [j]$ ;

$Y [i] = sum$ ;

Send $Y [i]$ to the next hop

If receiving Break Message exit.

Algorithm 2: Formal description of recoding on mobile nodes.

Compute $f, α_{1}$ and $α_{2}$ with (16), (17)

Compute $μ$ with (18)

$S p = 0.3$ ;

//Compute the recoding matrix P:

For $i = 1$ to μ

For $j = 1$ to υ

If $j < i$ then $p [i, j] = 0$ ;

Else

$S p = 1 - 2 * S p^{2}$ ;

$p [i, j] = \arcsin (S m) / π + 0.5$ ;

End If

//Compute and send the recoded vector Z:

Compute $Pr$ ;

For $i = 1$ to μ

For $j = 1$ to υ

$sum = 0$ ;

$sum = sum + p [i, j] * Y [j]$ ;

$Z [i] = sum$ ;

$P t = Pr / (1 + Pr)$ ;

If $i * P t - Int (i * P t) < P t$ then

Send $Z [i]$ to the next hops in direction 1;

Else

Send $Z [i]$ to the next hops in direction 2;

End If

Figure 2

The process flowchart of mobile node on MWSN.

Network coding is only implemented on the source node. Mobile node divides the packets into the short fixed-size blocks and generates the local coding matrix K, then encodes the blocks using linear network coding. It selects the farthest node within its radio range as the next hop in the time of a block to be forwarded. K is not sent out from the source. The destination can generate all elements of K for decoding according to source and its IDs.

The process of recoding on mobile node is described in Algorithm 2. The recoding algorithm is implemented by mobile node on the cross road, while the first element of encoded vector Y is received. Then, the mobile node is buffering the encoded blocks $y (i)$ and recoding them at the same time. The recoding matrix P is designed as a lower triangular matrix, and pseudo-random sequence is assigned to the elements whose column number is not less than row number. The recoded blocks are separated to the next hops in two directions according to the proportion of 1 : Pr. Because the matrix equations with triangular matrices are easier to solve, the decoding process is faster to implement. Destination node begins to decode initial data as long as it received $ω$ recoded blocks.

4. Simulations

In this section, we generate the mobile nodes on the ONE simulator [30] and evaluate the performance of our TBNC method in contrast with Epidemic [31] and PRoPHET [32] routing and generic Wi-Fi.

4.1. Simulations Setting

We use part of Helsinki city map in ONE simulator as the region of simulation. The area with the range of 4000 m × 3000 m from the map is extracted as the scenarios of node movement. There are 127 cross roads within the area. The density of roads is higher than general city. The mobile nodes move on the map at the speed of 5 to 50 km/h, which covers the movement from the walk to the vehicle on the urban areas. The mobile nodes choose random from sources to destinations on the map and move there following the shortest path. The radio range is configured as 50 m, and the MAC protocol is IEEE 802.11.

We compare TBNC with Epidemic PRoPHET routing and generic Wi-Fi. Epidemic and PRoPHET are two typical routing protocols for ad-hoc networks and have been implemented by the users of the ONE simulator as add-ons. Epidemic replicates messages to all encountered nodes that do not have them yet. PRoPHET only sends messages to the nodes that have the highest chances to deliver the messages to the destination. In generic Wi-Fi, vehicles data must be delivered by access points (APs) in the radio range, and the routing capability of vehicles is disabled. Many APs need to be deployed intensively in the area.

The other parameters of TBNC method are listed as following. Maximum number of hops is 10. Maximum value of $Δ t$ is 180 seconds. The dimension of encoding vector $ω = 10$ . The number of APs in the area is 20.

We measure the block loss rate, transmission delay, and overhead messages as the parameters to reflect synthetically the performance of TBNC. The 10 sources generate flows continuously to the 10 destinations for the evaluation. The simulation lasts for 30 minutes. The number of mobile nodes and the TTL of blocks are variable at the every test, but the sources and destinations follow the respective prescribed trajectory to move in the range of test area.

4.2. Simulation Results

The block loss rate, transmission delay, and overhead messages of 10 flows are collected in the simulations. Block loss rate is the ratio of lost blocks to the sending blocks from sources. Transmission delay is the time of a block delivered from the source to all destinations. Overhead ratio is the effective blocks as the percentage of all forwarding blocks among vehicles. The average values of the 10 flows about the 3 parameters are presented as the basis for evaluating the performance of TBNC.

The average blocks loss rate of TBNC is contrasted by three protocols in Figures 3 and 4. TTLs are changed in four data plots of Figure 3, but the number of mobile nodes remains 80. Blocks loss rate decreases in all plots as the value of TTLs increases. When TTL is equal to the simulating time (1800 s), blocks loss rate is 0 for all methods. Only 20 APs cannot cover the whole area, while generic Wi-Fi has highest loss rate and cannot be used. The loss rate of PRoPHET is more than 0.3, while TTLs are less than 10 minutes. Too many blocks are lost and packets can't be recoverd in destinations. Epidemic sends copies to all encountered nodes, and transmits successively in the greatest probability, so it has lest loss rate in all methods. TBNC is close to Epidemic in blocks loss rate. When TTL is 1 minute, the blocks loss rate of TBNC is less than 0.2, and it can reach the target of transmission reliability. If network coding is not used, our method is only close to PRoPHET in blocks loss rate. Network coding played a critical role in the improvement of reliability.

Figure 3

Blocks loss rate on the different TTLs.

Figure 4

Blocks loss rate on the different number of mobile nodes.

The number of mobile nodes N is changed in four data plots in Figure 4, but TTL remains 60. The values of N have no effect on the loss rate of generic Wi-Fi. The other methods decrease their blocks loss rate rapidly as the mobile nodes became denser. TBNC are still closer to Epidemic than PRoPHET. When there are more than 150 nodes moving in the area, the blocks loss rate of TBNC decreases to less than 0.1. If more than 300 nodes are evenly distributed in the area, all blocks can be delivered to their destinations. The increase of N has more influence on the transmission reliability than the increase of TTL.

Figures 5 and 6 show the average delay of blocks that are transmitted successively from sources to destinations. In Figure 5, the test conditions are same as Figure 3. The average delay of all methods grows with TTLs increase. Generic Wi-Fi only can deliver few blocks to destinations. Its delay is determined by time that nodes move into the radio range of APs. PRoPHET only takes one of encountering node as the next hop. Although the node has the highest chance to destinations, it maybe moves more time to send block. So, the delay of PRoPHET is more than the other methods. TBNC is close to Epidemic in delay on the different TTLs. The process of network coding adds a little delay to delivery blocks. When TTL is 1 minute, the delay of TBNC is 7% more than Epidemic.

Figure 5

Average transmission delay on the different TTLs.

Figure 6

Transmission delay on the different number of mobile nodes.

In Figure 6, the test conditions are same as Figure 4. The delay of generic Wi-Fi changes randomly and does not associate with the number of mobile nodes. All the other methods decrease the transmission delay with the increase of nodes. PRoPHET may select inaccurate next hops to delivery data. Its delay is more than TBNC and Epidemic. TBNC is still close to Epidemic in delay on the different N. The increase of N has also more influence on the delay than the increase of TTL. When the number of mobile nodes is more than 300, the delay of TBNC is less than 30 seconds, and it is only 7% more than Epidemic. It can reach the target of transmission real-time in the mobile networks.

The average overhead ratios of TBNC are contrasted by three protocols in Figures 7 and 8. In Figure 7, the test conditions are also same as Figure 3. Generic Wi-Fi does not generate overhead messages on any conditions, and its value is always 100% and the least in the four methods. Epidemic broadcasts data to any nodes and generates most overhead messages. Its overhead ratio rises rapidly with the increase of TTL. When TTL is 1 minute, its overhead ratio is more than 800%. Epidemic has too many overhead messages to be used in WMSN. PRoPHET produces overhead messages while it selects inaccurate next hops to delivery data. It also generates more overhead messages, while setting more TTLs. TBNC only produces overhead messages on the cross road. Its overhead messages also rise with the increase of TTL but are always less than PRoPHET. When TTL is 1 minute, TBNC has 68% less overhead ratios than PRoPHET.

Figure 7

Overhead ratio on the different TTLs.

Figure 8

Overhead ratio on the different number of mobile nodes.

In Figure 8, the test conditions are also same as Figure 4. The overhead ratio of Epidemic is too high to be used. PRoPHET grows in overhead message with the increase of N. The increase in the number of mobile nodes causes that more nodes select inaccurate next hops. Generic Wi-Fi still does not generate overhead messages. The TBNC does not change its overhead ratios with the increase of N. Overhead ratio relates to the number of cross roads rather than the number of mobile nodes. When N is 300, TBNC has 202% less overhead ratio than PRoPHET and it cuts down about 1/2 overhead messages. TBNC reduces the overhead message after network coding and improves the scalability of MWSN.

TBNC is able to achieve lower overhead ratios than both Epidemic and PRoPHET. Its blocks loss ratio and delay are tiny higher than Epidemic but lower than the other methods. TBNC reduces the overhead message after network coding and improves the scalability of MWSN.

5. Conclusion

MWSN can use the pre-trajectory of mobile nodes to improve its performance. We suppose that mobile nodes have to satisfy the three reasonable conditions. TBNC is implemented firstly on the source node. Encoded blocks are forwarded to multiple neighbors according to their trajectories. Then, they can be recoded on the mobile nodes on the cross road and delivered forwarded along multipath to the destination. TBNC combines network coding with the pre-trajectory of mobile nodes.

We evaluate the performance of our TBNC in contrast with Epidemic, PRoPHET routing, and generic Wi-Fi in the simulations. The results show that TBNC is able to cut down 1/2 overhead messages of PRoPHET when mobile nodes are shared by GPS trajectory. The blocks loss ratio and transmission delay of TBNC are tiny higher than Epidemic but lower than the other methods. Our work improves the reliability and scalability of MWSN when location and navigation systems are popular in mobile nodes.

Footnotes

Acknowledgments

The work is supported by the National Science Foundation of China under Grant nos. 61070169, 61202378, and 61070170, University Science Research Project of Jiangsu Province under Grant no. 11KJB520017, Natural Science Foundation of Jiangsu Province under Grant no. BK2011376, Specialized Research Foundation for the Doctoral Program of Higher Education of China No. 20103201110018, and Application Foundation Research of Suzhou of China no. SYG201238, SYG201118, and SYG201034.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

Indu

Bhattacharyya

Kesham

Chaudhury

Self deployment of mobile sensor network for optimal coverage

International Journal of Engineering Science and Technology 2010 2 7 2968 2975

Ahmed

A. A.

An enhanced real-time routing protocol with load distribution for mobile wireless sensor networks

Computer Networks 2013 57 1459 1473

Karim

Nasser

Reliable location-aware routing protocol for mobile wireless sensor network

Communications, IET 2012 6 14 2149 2158

Ahmed

A. A.

Fisal

A real-time routing protocol with load distribution in wireless sensor networks

Computer Communications 2008 31 14 3190 3203

2-s2.0-49649097884

10.1016/j.comcom.2008.04.030

Bulusu

Heidemann

Estrin

GPS-less low-cost outdoor localization for very small devices

IEEE Personal Communications 2000 7 5 28 34

2-s2.0-0034291601

10.1109/98.878533

Khabbaz

M. J.

Assi

C. M.

Fawaz

W. F.

Disruption-tolerant networking: a comprehensive survey on recent developments and persisting challenges

IEEE Communications Surveys and Tutorials 2012 14 2 607 640

2-s2.0-79956195734

10.1109/SURV.2011.041911.00093

Cheng

Thaeler

Xue

Chen

TPS: a time-based positioning scheme for outdoor wireless sensor networks

Proceedings of the IEEE Conference on Computer Communications 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04)

March 2004

2685 2696

2-s2.0-8344222870

10.1109/INFCOM.2004.1354687

Huang

Blum

B. M.

Stankovic

J. A.

Abdelzaher

Range-free localization schemes for large scale sensor networks

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03)

September 2003

81 95

2-s2.0-1542329081

10.

Savvides

Han

C.-C.

Strivastava

M. B.

Dynamic fine-grained localization in ad-hoc networks of sensors

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking

July 2001

166 179

2-s2.0-0034775930

11.

Shang

Ruml

Improved MDS-based localization

Proceedings of the IEEE Conference on Computer Communications 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04)

March 2004

2640 2651

2-s2.0-8344247710

10.1109/INFCOM.2004.1354683

12.

Pathirana

P. N.

Bulusu

Savkin

A. V.

Jha

Node localization using mobile robots in delay-tolerant sensor networks

IEEE Transactions on Mobile Computing 2005 4 3 285 296

2-s2.0-19944390963

10.1109/TMC.2005.43

13.

Koutsonikolas

Das

S. M.

Y. C.

Path planning of mobile landmarks for localization in wireless sensor networks

Computer Communications 2007 30 13 2577 2592

2-s2.0-34548449324

10.1016/j.comcom.2007.05.048

14.

Galstyan

Krishnamachari

Lerman

Pattem

Distributed online localization in sensor networks using a moving target

Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04)

April 2004

61 70

2-s2.0-3042819146

15.

Liu

Wang

Xiao

Topology control algorithm for underwater wireless sensor networks using GPS-free mobile sensor nodes

Journal of Network and Computer Applications 2012 35 6 1953 1963

16.

Chaurasiya

V. K.

Jain

Nandi

G. C.

A novel distance estimation approach for 3D localization in wireless sensor network using multi dimensional scaling

Information Fusion 2014 15 5 18

17.

Larios

D. F.

Barbancho

Molina

F. J.

León

LIS: localization based on an intelligent distributed fuzzy system applied to a WSN

Ad Hoc Networks 2012 10 3 604 622

2-s2.0-84856516006

10.1016/j.adhoc.2011.11.003

18.

Ren

A rapid acquisition algorithm of WSN-aided GPS location

Proceedings of the 2nd International Symposium on Intelligent Information Technology and Security Informatics (IITSI '09)

January 2009

Moscow, Russia

42 46

2-s2.0-67649383547

10.1109/IITSI.2009.16

19.

Heidemann

Estrin

Geography-informed energy conservation for ad hoc routing

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking

July 2001

70 84

2-s2.0-0034772133

20.

L. Z.

Zhang

S. K.

Zhu

Y. Q.

Yang

MCNC: data aggregation and dissemination in vehicular Ad-hoc networks using multicast network coding

International Journal of Distributed Sensor Networks 2013 2013 11

853014

10.1155/2013/853014

21.

Leontiadis

Costa

Mascolo

Extending access point connectivity through opportunistic routing in vehicular networks

Proceedings of the IEEE (INFOCOM '10)

March 2010

San Diego, Calif, USA

2-s2.0-77953311946

10.1109/INFCOM.2010.5462185

22.

Jeong

Guo

Trajectory-based statistical forwarding for multihop infrastructure-to-vehicle data delivery

IEEE Transactions on Mobile Computing 2012 11 10 1523 1537

23.

Jeong

Guo

D. H. C.

Trajectory-based data forwarding for light-traffic vehicular Ad Hoc networks

IEEE Transactions on Parallel and Distributed Systems 2011 22 5 743 757

2-s2.0-79953310708

10.1109/TPDS.2010.103

24.

Ahlswede

Cai

S.-Y. R.

Yeung

R. W.

Network information flow

IEEE Transactions on Information Theory 2000 46 4 1204 1216

2-s2.0-0034229404

10.1109/18.850663

25.

Shan-Shan

Pei-Dong

Xiang-Ke

Wei-Fang

Shao-Liang

Energy efficient multipath routing using network coding in wireless sensor networks

Ad-Hoc, Mobile, and Wireless Networks 2006 4104

Berlin, Germany

Springer

114 127

26.

T.-G.

Hsu

C.-C.

Chou

C.-F.

On reliable transmission by adaptive network coding in wireless sensor networks

Proceedings of the IEEE International Conference on Communications (ICC '09)

June 2009

Dresden, Germany

2-s2.0-70449514407

10.1109/ICC.2009.5199247

27.

Hou

I.-H.

Tsai

Y.-E.

Abdelzaher

T. F.

Gupta

AdapCode: adaptive network coding for code updates in wireless sensor networks

Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08)

April 2008

Phoenix, Ariz, USA

1517 1525

2-s2.0-51349100852

10.1109/INFOCOM.2007.211

28.

Miao

Djouani

Kurien

Noel

Network coding and competitive approach for gradient based routing in wireless sensor networks

Ad Hoc Networks 2012 10 6 990 1008

2-s2.0-84859752518

10.1016/j.adhoc.2012.01.001

29.

Chandanala

Zhang

Stoleru

Won

On combining network coding with duty-cycling in flood-based wireless sensor networks

Ad Hoc Networks 2013 11 1 490 507

30.

The ONE

http://www.netlab.tkk.fi/tutkimus/dtn/theone/

31.

Vogels

Renesse

Birman

The power of epidemics: robust communication for large-scale distributed systems

ACM SIGCOMM Computer Communication Review 2003 33 1 131 135

32.

Lindgren

Doria

Schelen

Probabilistic routing in intermittently connected networks

ACM SIGMOBILE Mobile Computing and Communications Review 2003 7 3 19 20

Data Dissemination in Mobile Wireless Sensor Network Using Trajectory-Based Network Coding

Abstract

1. Introduction

2. Related Works

3. Implementing TBNC on MWSN

3.1. Conditions and Assumptions

3.2. TBNC

3.2.1. Network Coding in the Source

3.2.2. Recoding on the Cross Road

3.3. Implementing on MWSN

Algorithm 1: Formal description of network coding on the source nodes.

Algorithm 2: Formal description of recoding on mobile nodes.

4. Simulations

4.1. Simulations Setting

4.2. Simulation Results

5. Conclusion

Footnotes

Acknowledgments

References