Abstract
We present how the mobility of routers impacts the performance of a wireless substitution network. To that end, we simulate a scenario where a wireless router moves between three static nodes, a source and two destinations of UDP traffic. Specifically, our goal is to deploy or redeploy the mobile relays so that application-level requirements, such as data delivery or latency, are met. Our proposal for a mobile relay achieves these goals by using an adaptive approach to self-adjust their position based on local information. We obtain results on the performance of end-to-end delay, jitter, loss percentage, and throughput under such mobility pattern for the mobile relay. We show how the proposed solution is able to adapt to topology changes and to the evolution of the network characteristics through the usage of limited neighborhood knowledge.
1. Introduction
Problem Description
It is critical to design efficient algorithms to support ubiquitous services in networked environments. This is due to the fact that wireless technologies are evolving into the next generation, so an increasing number of users will enjoy ubiquitous access. Some of the main challenges include a fairly complex node placement/deployment problem without prior knowledge of the optimal network topology or optimal mobile routers locations.
Previous work has focused on deployment and placement of mobile devices (e.g., robots) for area coverage [1–5]. In our work, the goal is to deploy a set of wireless mobile devices between classical network routers to restore the connectivity without prior knowledge of the optimal placement of the devices. Additionally, most efforts to date use local area networks, ad hoc networks, wireless sensor networks, and mesh networks for several different purposes, such as community and neighborhood networking, transportation systems, networking for developing countries, connection of isolated locations, spontaneous networking, and disaster recovery [6]. In these papers, the spontaneous networking approach is used for specific cases, such as hurricanes, earthquakes, fiber optic cable cuts, flash crowds, or in presence of weak connectivity. Instead, in this paper, we consider the use of controlled mobility provided to wireless routers to restore or improve network connectivity. We assume that mobile relays have self-organization, self-optimization, and self-healing capabilities in order to allow a flexible, scalable, and resilient deployment. Hence, the main issue in this context is how to deploy or redeploy the wireless mobile relays in order to keep the network services running.
Contributions
(1) We introduce different adaptive strategies for the deployment/redeployment of wireless mobile relays. (2) Our solution is localized, scalable, and adaptive. (3) We show that our scheme outperforms the static approach.
Paper Organization
The remainder of this paper is structured as follows. In Section 2, we state the problem, introduce some motivating applications, and state our assumptions, followed in Section 3 by the description of our solution, the simulation model, and the performance metrics. In Section 4, we evaluate the proposed scheme through extensive simulations and discuss the experimental results. Finally, Section 5 concludes this work and presents future developments.
2. Some Background
Spontaneous networking, or public service networking, is used in specific cases such as hurricanes, earthquakes, fiber optic cable cuts, flash crowds, or in presence of weak connectivity, the network not only must be deployed in a short period of time, but also must have capabilities as self-organization, self-optimization, and self-healing [7]. This type of networks is called rapidly deployable network (RDN).
We consider a substitution network (SN) as a kind of RDN. An SN is a temporary wireless network created to help the base network to keep providing services. This substitution network must be rapidly deployed to quickly adapt to network topology changes and to ensure the network connectivity [8].
A specific example of an application of an SN is the contractor's mistake in the Sydney's Business District [9]. In 2009, some contractors cut through 10,000 of Telstra company copper wires and 8 fiber optic cables by mistake. This caused over 12,000 business and residential customers without phone, mobile, or Internet services for several days. The cost to Telstra of this mistake was AU$1 million just to repair the wires, plus the compensation cost for the affected customers and a demand by the Australian government. Finally, it took Telstra about a week to replace the cables and restore the service.
Another example is after a natural or man-made disaster, such as earthquakes or terrorist attacks, when the communications networks are not destroyed but congested. In September 11, 2001, the radio network used by the Emergency Medical Service was saturated by panicked operator transmitting unnecessary information [10].
2.1. Related Work
In the last years, many schemes and solutions have been proposed to improve network performance by placing wireless relays in specific positions [11, 12]. The most common objectives are energy consumption and coverage as presented in [4, 13–17]. However, these solutions are not suitable to substitution networks because they depend on a preplaned deployment.
Evans et al. introduced in 1999 the concept of a rapidly deployable network [18]. The main idea is to deploy a network infrastructure in promptu to provide communication services for military applications. After this work, several deployment schemes have been proposed in the literature not only for military communications but also for emergency communications.
In order to address the deployment problem, a relay-based approach is presented in [19–21]. In most of these proposals, the first responders, for example, firemen or policemen, carry a personal mobile radio and small relays. Then, the first responders must drop these devices while exploring the emergency zone in order to maintain the connectivity with the central command thus creating a multihop network. Each mobile radio exchanges control information with the closest relay to decide when to drop a new small relay. So, the main focus is to propose a deployment decision process that maximizes the network performance.
Bao and Lee present a method to rapid deploy an ad hoc backbone for spontaneous networks with no preplanning [19]. The authors present a collaborative deployment algorithm, which takes into account physical or link quality measurements such as signal-noise ratio and packet loss rate. The algorithm measures the link quality through control messages added to the control packet header of the ad hoc routing protocol. They assume that each device can notice the different type of its neighbors, that is, if the neighbor is a mobile device or a relay, and also they keep track of each relay deployed.
Later, Souryal et al. present an algorithm for NIST real-time deployment of mesh networks project [21]. The authors propose an algorithm based on a quick evaluation of the physical layer performed by the mobile radio. In a nutshell, the mobile radio establishes one-hop communication by constantly broadcasting probe packets to previous relays, when some relays in the range respond with a probe ACK packet, the mobile radio measures the RSS through ACK reception, if the RSS value falls below a given threshold level, then a new relay must be dropped.
Nevertheless, the concept of static relays has changed, for example, the LANdroids project launched by the Defense Advanced Research Projects Agency, DARPA. The goal is to propose an RDN for battlefield based on mesh networks composed of small mobile relays. Based on this call, a spreadable connected autonomic network (SCAN) is presented in [22]. SCAN is a mobile network that automatically maintains its own connectivity by moving constantly its nodes. The authors present the SCAN algorithm capable to deal with environments where the predeployment mapping is expensive or infeasible without any previous information of the environment. This protocol proposes an online distributed process where each node uses two-hop radius knowledge of the network topology and each of them determines when to stop its motion if the decision criterion indicates risk of dividing or disconnecting the network.
2.2. Key Points
We propose to deploy a network composed of a fleet of dirigible wireless mobile routers for public service. In order to fully adapt to the current conditions, the mobile routers should move or redeploy on demand. This means that, not only the edges of the net may move but also the core or part of the core. One of the deployment issues is in which direction move the router to avoid disconnection or degradation of the quality of service (QoS).
The deployment of a network composed of a fleet of dirigible wireless mobile routers (named from now on as substitution network) can be useful in case of multiple link failures as in natural disasters, weak connectivity, fiber optic cable cuts, or flash crowds.
In this work, we focus on a typical use case of substitution networks as presented in [8]. In this scenario, the substitution network aims at helping a base network to restore and maintain some of the basic services available before the failure. Thus, a fleet of mobile relays is self-deployed to compose a substitution network together with the base network. Thereby, we evaluate an adaptive positioning scheme to increase the network depending on the driving applications.
Our basic idea is that, during the network lifetime, each wireless mobile device of the substitution network determines a new position by using the feedback on the link quality coming from its neighbors.
We assume that two nodes are “neighbors” when they are within the communication range of each other. Likewise, we assume that some of the devices are fixed, that traffic needs to be transferred between two fixed devices, and that wireless devices dynamically move in the scenario and act as relays, regardless the routing protocol. Besides, we assume that each device is aware of its own position by using GPS or any other localization system, so as to allow nodes to use controlled mobility. More ever, as with many link layer protocols, we assume that each node is equipped with a timer and an 802.11 wireless card, and it has an identifier that is unique in the network (MAC address).
In this paper, we use the term “broadcast” for message propagation in a device's neighborhood. As well as, we call “link parameter” a measure of link quality between a mobile device and each of its neighbors, for example, signal-noise ratio (SNR), received signal strength (RSS), round-trip-time (RTT), and transmission rate (TR).
Based on the assumptions above, we propose a solution to deploy/redeploy intermediate mobile relays, that is,
localized: every decision taken by the mobile relay is based only on close neighbors (i.e., one-hop neighbors) and local link information. The mobile routers take advantage of probe packets to exchange information about their surrounding links status, and drive their positioning; scalable: as a consequence of the previous property, our solution is scalable on the network size and the mobility strategy of the surrounding wireless mobile routers; adaptive: the algorithm ensures that the connectivity quality is permanently monitored based on close neighbors and local link information. As a consequence, the proposed placement scheme is adaptive to topology changes and to the evolution of the network characteristics.
3. Proposed Scheme
Briefly, the major steps of the algorithm that runs in each node independently are the following: (1) measurement of the “link parameter” (2) computation of the new position and (3) movement towards the computed position. Each of these steps is described.
No prior knowledge of the optimal mobile device locations is assumed to be available at nodes. Our algorithm uses close neighbors and local links information to allow nodes to position themselves. Each relay runs the algorithm regularly and measures the link parameters.
3.1. Detailed Operation
3.1.1. Measure Link Parameters
In order to measure link parameters, we use an intrusive method. The wireless mobile device regularly (every t seconds) broadcasts probe request packets containing a sequence number and the id or MAC address of the wireless mobile device. Each node receiving probe request replies with a probe reply message by using unicast transmission and including information such as its id, its position, and any local information regarding the link parameters. We use an intrusive method to get up-to-date information regarding link parameters but also to get a consistent and fair view of each link in the surroundings of a mobile device. An additional advantage of using broadcasting of probe request packets is that we can avoid the clock synchronization problem between devices.
It is important to notice that the probe packets, request and reply, have a higher access priority than other packets. Specifically, when a probe packet is generated, it will be put at the head of line in the link layer queue. However, these packets cannot preempt a scheduled transmission at the MAC layer. Note also that since the mobile routers are only used as relays, they are able only to exchange protocol stack information up to network layer. Thus, they cannot use application or transport layer measures directly or indirectly related with the “link parameter” currently measured.
3.1.2. Compute New Position
Each node computes its new position based on the surrounding link parameters every
The wireless mobile device compares the values of the link parameter received from the next and the previous hop,
3.1.3. Move to New Position
In this step, each wireless device moves forward on the computed direction for a distance d. This stepwise choice is arbitrary and it would be easier to relate the traveled distance d to the link parameter value. However, we chose this stepwise movement to be more realistic since in real environments, some geographical positions cannot be considered as a suitable position due to potential obstacles, for example, a wireless mobile device cannot cross a vehicles road.
Based on the link parameter measurements, the mobile device tries to equalize the metrics for both the previous node and the next node. The study of this tradeoff is left as a future work. It is important to notice here that we assume a correlation between link parameters and position due to wireless channel impairments or fading effects, for example.
The protocol version of the proposed scheme, named APA for (adaptive positioning algorithm), is given in Algorithm 1.
(i) (ii) double int k, (1) set TIMER to expire in time (2) (3) (4) Send (5) (6) set TIMER to expire in time (7) (8) (9) (10) Upon reception of a (11) (12) Store (13)
(1) set TIMER to expire in time k × (2) (3) (4) Compute link parameter for (5) (6) Move towards the (7) (8) Move towards the (9) (10) Do not move; (11) (12) set TIMER to expire in time k × (13) (14)
3.2. Topology and Simulation Description
We implement APA by using the NS 2.29 [23] network simulator with patches that reflect real wireless propagation, real wireless physical layer, and the adaptive autorate fallback (AARF) mechanism for 802.11b [24]. AARF adapts the transmission rates depending on the network conditions, in order to increase link reliability. Rather than using a fixed threshold, AARF adapts such threshold following binary exponential backoff. We also extend the simulator by adding a realistic channel propagation and error model, as proposed in [25], by adding the effect of interference and different thermal noises to compute the signal to noise plus interference ratio (SINR) and accounting for different bit error rate (BER) to SINR curves for the various codings employed. We use the DSR protocol for our simulations in order to account with an initial routing solution. As we mentioned before, APA is not tied to any routing protocol in particular, so it is designed to work with any routing protocol. Table 1 shows all the parameters used in our simulations.
Simulation parameters.
Below, we present an experimental performance evaluation of APA under different network metrics such as throughput, delay, and jitter. They are defined as follows:
average throughput (TH). The average throughput of a data transfer is: average end-to-end delay (D). This is the total average time for a packet to travel from source to destination; average jitter (J). We compute the jitter as the measure of the variability over time of the packet latency across a network; as known, jitter is a function of the delay; loss percentage (L). The loss percentage is equal to
At the transport layer, we transmit UDP traffic with a packet size of 1000 B. We also vary the average transmission rate with steps of 10, 50, 200, 300, 600, 1000 kbps for each set of simulations. Each simulation runs for a period of 2000 seconds.
4. Results
We start by simulating a simple scenario with a source and a destination node that communicate through one wireless mobile relay (Figure 1). In this topology, the destination node is placed 250 meters far from the source node. At the beginning of the simulation, the relay node is placed 10 meters far from the source node. Thus, the relay starts moving by using our APA algorithm.
Simple evaluation scenario.
Thus, we evaluate the convergence of our proposal with each link parameter, RSS, RTT, SNR, and TxRate. We use the topology illustrated in Figure 1, with UDP traffic with a packet size of 512 B during 3,000 seconds. The resulting movements are depicted in Figure 2, the relay moves between the source and the destination trying to position itself by equalizing each of the mentioned parameters. We observe that, by using RSS as input for our scheme, the relay reaches exactly the middle position (i.e., 125 meters from the source) after less than one third of the simulation, and it remains in that position for the rest of the simulation time. Besides, when the relay uses the RTT, SNR, and TxRate as input, it keeps moving without reaching a fixed position.
Placement evolution with APA comparison (RSS, RTT, SNR, and TxRate).
Accordingly, we evaluate the network performance changing the number of flows and destinations. We use the topology depicted in Figure 3, where we present a source (n0) and two destinations (n2, n3) out of range. So, we use a relay (n1) to connect the source and the destinations. At the beginning of the simulation, the relay (n1) is placed 60 meters far from the source node (n0) on the straight line that connects the source node from the middle position between the receiver nodes (n2 and n3). For all the simulations, we consider transmitting UDP packets with a size of 1000 B, and we vary the transmission rate as we described in the previous section.
Evaluation scenario with one source and two different destinations.
We compare the performance of each link parameter versus the performance of a fixed node. The fixed node is positioned on the barycenter of the given topology, that is, 173 meters far from the source node on the straight line that connects the source node from the middle position between the receiver nodes.
We present in Figure 4, the positioning evolution of the relay by using APA. This figure presents two views of the evolution, Figure 4(a) is a 3D view showing the movement on the Cartesian plane with the time on the z-axis. We observe that, when the relay uses SNR as the equalizing parameter, it stops moving after 200 seconds, by using RSS, it stops moving after 1500 seconds, whereas by using RTT and TxRate, it continues moving until the end of the simulation. The movement trace is depicted in Figure 4(b). Here, we observe that by using TxRate, the relay goes close to n3. We also observe that only the RTT parameter reaches the point that is closer to the barycenter, and the RTT-based scheme improves its performance in this scenario compared with the simple scenario presented before.
Deployment evolution in time (RSS, RTT, SNR, TxRate, and Barycentric), contrasting the relay placement as function of time.
In the following simulation campaigns, we transmit two UDP flows starting at the same time. The source node (n0) transmits Flow 1 to destination node 1 (n2) and Flow 2 to the destination node 2 (n3). In Figure 5, we show the average end-to-end delay and the average jitter comparison for each flow. The performance for these two parameters, when the mobile relay is positioned on the barycenter, is constant. We see also that for a transmission rate under 600 kbps, the mobile relay obtains low values for both delay and jitter.
End-to-end delay and jitter comparison.
Figure 6 shows the results for throughput and the packet loss. We can see that when the relay is positioned on the barycenter, as the transmission rate increases, the results are constant and outperform those obtained by using the mobile relay. Besides, as the transmission rate increases, the packet loss grows. For both metrics, the RTT parameter performs better than the RTT, SNR, and TxRate parameters.
Throughput and packet loss percentage comparison.
However, these results do not reflect the performance during the simulation time. This is important because, as we can see in Figure 7, the mobile relay in some moments improves the throughput values obtained with the static relay. We have to recall that the mobile relay starts moving from a position 60 meters far from the source node, which is worse than the barycenter in terms of network performance; but, when using our algorithm, the mobile relay improves its position and its performance on the fly.
Instant throughput comparison between each link parameter and barycentric.
5. Conclusion
In this paper, we have presented a scheme based on different link parameters for substitution networks that operates in environments where connectivity guarantee is an issue.
We have introduced a suite of algorithm strategies to control the placement of wireless mobile devices. In particular, we have focused on networks where the source and the destination nodes of UDP traffic are connected through multihop communications performed by wireless mobile devices that act as relays. Specifically, our goal has been to deploy or redeploy the wireless mobile devices so that application-level requirements, such as data delivery or latency, are met. The APA algorithm we have proposed achieves these goals by using a localized and adaptive approach that determines the optimal positions of mobile relays in terms of delay, jitter, loss percentage, and throughput. Our simulation results show the importance of the placement of wireless mobile relay nodes to increase the performance at the application level. Finally, we compared our solution with the optimal theoretical placement, which is the barycenter.
Our future work will focus on determining theoretically the optimal placement of the relay nodes in order to increase quality of service and quality of experience.
Footnotes
Acknowledgments
This work is partially supported by the French National Research Agency (ANR) under the VERSO RESCUE project (ANR-10-VERS-003) and by the Inria ARC MISSION grant.