Optimizing Wireless Network Protocols Using Real-Time Predictive Propagation Modeling - PDF

Please download to get full document.

View again

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 7 | Pages: 6

Extension: PDF | Download: 0

Related documents
Optimizing Wireless Network Protocols Using Real-Time Predictive Propagation ing Ratish J. Punnoose, Pavel V. Nikitin, Josh Broch, and Daniel D. Stancil Department Of Electrical and Computer Engineering
Optimizing Wireless Network Protocols Using Real-Time Predictive Propagation ing Ratish J. Punnoose, Pavel V. Nikitin, Josh Broch, and Daniel D. Stancil Department Of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA 1513 Abstract A common feature of all wireless mobile data networks is the dynamic nature of the propagation environment. Our work introduces a new level of intelligence into wireless networks by creating a realtime prediction model that runs independently on each mobile node. Such a prediction can assist the routing protocol in making hand-offs or in choosing the best route to a destination, taking into account future RF propagation conditions. 1 Introduction In areas where there is little or no communication infrastructure wireless mobile users may still be able to communicate through the formation of an ad hoc network. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. Each node participates in an ad hoc routing protocol that allows it to discover multi-hop paths through the network to any other node. Some examples of the possible uses of ad hoc networking include soldiers relaying information for situational awareness on the battlefield [1] and emergency disaster relief personnel coordinating efforts after a hurricane or earthquake. One of the major challenges for multi-hop wireless ad hoc network routing protocols is rapid adaptation to topological change so that users of the ad hoc network experience minimal packet loss and delay when topological change occurs. However, if changes in the network topology can be predicted, the job of the routing protocol becomes easier as it can reroute network traffic before topological change causes an existing route to break, and thereby avoid packet loss or delays that would otherwise be incurred. We have designed and implemented a real-time predictive propagation model that uses terrain information, GPS position information for each node, movement modeling and prediction, and propagation modeling to estimate the signal strength and loss factor between each pair of nodes in an ad hoc network. The predictive aspects of this model are used to estimate when routes that are presently working will break and this estimation is then passed to the routing protocol so that it can adapt to impending changes in the network before they cause packets to be lost or delayed. Hardware Control (power, antenna, thresholds, etc.) Routing Protocols (Mobile IP, Ad hoc, etc.) Hardware signal quality input Non position based prediction Calculation Decision maker Position Acquisition System Mobility RF Propagation & Communications Environment/ Terrain update System Environment/ Terrain Map Figure 1 General structure of the prediction model and the model-protocol interaction Our predictive model has been implemented and validated in a real ad hoc network testbed of 7 nodes [] that was in regular use for 5 months from November 1998 through March Using this testbed we demonstrated that the use of real-time interaction between the routing protocols and a predictive model can improve the reliability and performance of multi-hop wireless ad hoc networks. Section provides a detailed description of the model s architecture. Section 3 has details of the implemented pieces of the architecture. Section 4 describes the testbed, while Section 5 describes the tests that we used to validate the accuracy of the model and demonstrate the usefulness of its interaction with ad hoc network routing protocols. Prediction Design The model uses node location information, knowledge of terrain characteristics, and an RF propagation calculation to compute a link quality metric between each pair of nodes in the network. The ad hoc network protocol uses these link quality metrics in route selection. Figure 1 describes the components of the prediction model in terms of inputs, outputs and prediction elements. Inputs: Position acquisition system: This block provides location information of nodes to the prediction model. The position information may come from a GPS device, some feature inherent to the networking technology being used, or by other means specific to the scenario in which the network is implemented. A node can pass along its movement information to other nodes either by explicit periodic notification or by appending this information to data packets. Environment/Terrain update system: In the case of a rapidly changing terrain, the prediction model may be kept up to date of such changes. If structural information of mobile nodes is available, terrain height can be inferred from the node location. Updated terrain information can also be obtained from radar or lidar images. This information can be provided to the prediction model as updates to a digital elevation map. Hardware signal quality input: If the wireless networking hardware provides some information about the signal strength, SNR, etc. at which data is being received from other nodes, this information can be used in multiple ways: for a simple extrapolation based on recent values to predict a signal strength, as a form of memory in case the network configuration is repeated in the future and as validation and feedback to an RF Propagation Calculation. Prediction Elements: Non-position based prediction: Even in the absence of position information, the presence of some form of hardware signal quality measurement allows prediction by extrapolation of these values. Environment/Terrain Map: The environment/terrain map kept by the model is needed to make a detailed RF Propagation calculation. It is updated by any information obtained about topographical changes. Mobility : The mobility model uses past and current information about node positions and velocities to predict probable future positions. RF Propagation and Communications : The RF Propagation and Communications computes link qualities between nodes based on node locations predicted by the mobility model, the information stored in the terrain map, feedback received about past predictions, and specifications about the wireless technology currently being used. Decision Maker: This block is the affecter of change in the network. It interacts with the network protocol to determine the links to be tracked, provides link quality information to the network layer and asserts physical control of the network hardware when appropriate. Outputs: Routing Protocols: The prediction model makes estimates of link quality between different nodes. This information is used to guide the network protocol in either choosing routes or making hand-off decisions. Hardware: The prediction model can control the wireless network hardware directly by regulating power levels, setting signal thresholds and effecting any positive control on the antenna if possible. It may not always be possible for the prediction model to do this due to real-time constraints. An alternative is to provide the necessary information to the network layer which can then control the hardware on a packet by packet basis. 3 Implementation Details At present the shaded blocks in Figure 1 have been implemented and tested. We used an implementation of the Dynamic Source Routing ad hoc network protocol to test our ideas. This protocol was designed and implemented by the Monarch Project at Carnegie Mellon. This section provides further detail about the operation of the DSR protocol, the interface between DSR and the prediction model, the mobility model, and the RF propagation model. 3.1 Dynamic Source Routing The Dynamic Source Routing protocol (DSR) [3, 4, 5] works by discovering and using source routes. That is, the originator of a packet first learns the complete, ordered sequence of network hops necessary to reach the destination, and each packet sent carries this list of hops in its header. The key advantage of a source routing design is that intermediate nodes do not need to maintain up-to-date routing information in order to route the packets that they forward, since the packets themselves already contain all of the routing decisions. This fact, coupled with the on-demand nature of the protocol, eliminates the need for the periodic route advertisement and neighbor detection packets present in other protocols [6]. The DSR protocol is composed of two mechanisms: Route Discovery and Route Maintenance. Route Discovery is the mechanism by which a node S wishing to send a packet to a destination D obtains a source route to D. To perform a Route Discovery, the source node S broadcasts a ROUTE REQUEST packet that is flooded through the network in a controlled manner and is answered by a ROUTE REPLY packet from either the destination node or another node that knows a route to the destination. To reduce the cost of Route Discovery, each node maintains a cache of source routes it has learned or overheard, which it aggressively uses to limit the frequency and propagation of ROUTE REQUESTs. When sending or forwarding a packet to some destination D, Route Maintenance is used to detect if the network topology has changed such that the route used by this packet has broken. When a route breaks, the detecting node returns a ROUTE ERROR packet to the original sender S of the packet. The sender S can then attempt to use any other route to D that is already in its route cache, or can invoke Route Discovery again to find a new route. 3. /Protocol Interface A routing socket interface is used for communication between the DSR networking layer and the prediction model, which runs as a user program. The prediction model provides the network layer with a quality metric for a multi-hop route. In an ad hoc network with a sizeable number of nodes, keeping track of each end-to-end path can be computationally intensive. The prediction model should only keep track of the routes of interest to the network layer. Choosing a limited set of routes to track requires input from the network layer. The network layer may request the prediction model to keep track of source/destination pairs or a specified hop-by-hop route. To this end an interface has been tested to allow the network protocol layer to send requests to the prediction model, but in the experiments described below, the prediction model kept track of all possible links so that we could collect more data points for analysis. Packet from C1 to C5 C1 C1 C C3 C5 C1 C3 C5 C1 C C5 C1 C C4 C5 C1 C5 C Figure and Routing Protocol Interaction. The model provides route quality metrics to the protocols to aid in selecting the best route from the route cache. In the current implementation the prediction model provides the network protocol layer with a quality metric for pairs of nodes. The ad hoc protocol layer combines these quality metrics to compute a single metric for each multi-hop route so that it can choose the best route (Figure ). 3.3 Mobility In the current implementation, the location of each node is tracked by a Global Positioning System device located on each node. These devices are also capable of receiving differential GPS updates which can be sent over the wireless network. Without differential GPS, a node will still provide position information but with a degraded accuracy. Each node advertises its GPS information (location, speed and heading) in the packets it originates. These packets may use multiple hops to reach their final destination. Any other node overhearing a packet in transit can record the GPS information of the source. This information is collected by the network layer and provided to the prediction model. The mobility model on each node keeps track of the location history of all nodes. Using this information, it can perform path prediction to approximate the location of a node some time into the immediate future. In the case that the node is following a cyclic pattern, this is recognized and information from previous cycles is used to improve current prediction. The best prediction of future location of nodes is provided to the propagation model to make signal connectivity predictions. These predictions take C3 C4 C5 the form of link quality metrics that are sent to the network layer. 3.4 RF Propagation We use a site-specific three-dimensional propagation model. This model can be called N + ray + diffraction model since it takes into account a direct ray, a ground-reflected ray, and rays reflected off N objects, as well as diffraction from these objects. Objects considered in the model are arbitrarily oriented buildings of simple shape. A vehicle can also be described as an object whose location is known from the GPS information contained in the packets that it transmits. The model takes as an input the locations and heights of the transmitter, the receiver, and the buildings. Multipath is computed deterministically, assuming interference of the direct ray and single specular reflections from the ground and buildings. The geometrical optics approximation that allows us to use raytracing is valid because typical obstacle size in our experiment is much larger than the wavelength. The power received is computed by the following expression: Γ de ;j d d P r = P t G t G r Γ c + N+ X l= (4) Γ dl Γ l e ;j dl d l where P t is the transmitter power, G t is the gain of the transmitting antenna, G r is the gain of the receiving antenna, Γ c is the loss factor for antenna leads, is the wavelength, Γ d is the coefficient of diffraction losses along the direct path, d is the direct path length, Γ dl is the coefficient of diffraction losses for the l-th reflected ray, Γ l is the reflection coefficient of the l-th reflecting object, and d l is the path length of the l-th reflected ray. In the current version of the model, Γ dl is equal to either 1 or, depending on whether the ray reflected from the l-th object is blocked or not. The ground reflection is included into the summation above as the first term with l =. Diffraction effects become important when the line of sight is obstructed or a building is present in the first Fresnel zone. The equivalent diffraction coefficient Γ d is computed using a method similar to that described in [7] generalized to our geometry. An exhaustive search for all sources of multipath can be computationally expensive. To make this computation as efficient as possible, we limit our search to the ellipsoid with foci colocated at the transmitter and receiver, that represents the maximum distance impacting our problem [8]. The size of this ellipsoid can be determined by the following factors: the distance at which the power drops below a certain level the maximum differential path delay corresponding to the chip rate of the radio for direct sequence spread spectrum (1) meters E1 CMRI (site office) Monongahela river river C1 C Aristech Pitt C3 C4 C5 E meters Figure 3 Map of the Ad Hoc Network Testbed. End nodes E1, E remained stationary as cars C1-C5 followed a cyclical path (dashed line) with an average speed of mph. end node E1 C1 C5 ad hoc network with wireless 9 MHz links C C4 C3 site office end node E point to point wireless.4 GHz link Figure 4 Network Diagram. The site office also provided connectivity to the campus network and the Internet. the maximum differential path delay corresponding to the channel hopping rate for frequency hopping spread spectrum The Doppler shift resulting from the movement of vehicles was not included in the model. Theoretically our model allows computation of propagation conditions for an arbitrary terrain represented as a digital elevation map. Depending on the elevation profile, diffraction and multipath calculations can become quite challenging. In our experiment the testbed site was relatively flat and we used flat ground terrain in our model. 4 Testbed Description An experimental testbed was constructed for evaluating the performance of the ad hoc network protocol and to test the ideas described in this paper. An area of approximately 7 m by 3 m was chosen on the map shown in Figure 3. Five mobile nodes and two stationary end nodes were used in different scenarios. A stationary GPS receiver was set up as a reference base-station for differential corrections at the site office which provided an accuracy on the order of a few centimeters. The network architecture of the system is shown in Figure 4. Each mobile node (car) was equipped with an IBM Thinkpad 56X notebook, a WaveLAN 9 MHz PCMCIA card, and a Trimble 74 series GPS receiver. The equipment and power supply were housed in a rack on the front passenger seat. The antennas for the WaveLAN card and the GPS receiver were mounted separately on the top of the car. The Thinkpad notebook ran FreeBSD..7 with DSR (see section 3.1) implemented by the Carnegie Mellon Monarch Project. The WaveLAN radio (External Antenna Module) is a Direct Sequence Spread Spectrum card (DSSS) with a power output of approximately 5 mw (measured) and a raw data rate of. Mbps [9]. The chip rate of the WaveLAN card is 11 MHz, which means that the reflections arriving with a delay of 91 ns beyond the direct path are off by one chip. This limits the area of search for significant sources of reflections to the ellipsoid defined by the differential time delay of 91 ns (path difference 7.3 m), as described in Section 3.4. Experimentally, however, a differential delay of about 3 ns or less was needed to significantly impact the received signal strength. This reduces the ellipsoid to one representing a path difference of 9 m. The average speed of the cars in the experiments was mph (9.3 m/s). This corresponds to a maximum Doppler shift of 57 Hz at 915 MHz. This shift had no noticeable impact on the performance of the WaveLAN radios. Additional information about the testbed can be found in []. 5 Experimental Results 5.1 Validation In the typical operation of the testbed, five vehicles (C1-C5) followed each other on the loop course shown in Figure 3. Two stationary nodes, E1 and E, were positioned at the far ends of the course. Figure 5 shows the experimentally measured power received by node C1 from node C and the power level predicted by the model. The experimental values were obtained from the WaveLAN hardware. The peaks in the signal strength occur when the cars periodically pass each other on the road, moving in opposite directions. Similarly, the minimum signal strength occurs when the cars are farthest apart. This typically occurs when the cars are traveling in the same direction on the middle portion of the loop (Figure 3). The large-scale signal level predicted by the propagation model is in good agreement with the experimental data (Figure 5). However, there are significant differences in the fine structure between the model and the measurements. The fine structure in the predicted signal strength primarily results from interference between the direct and ground-reflected rays. As mentioned previously, only reflections with a differential path delay in excess of 3 ns are included in the model. This eliminates almost all of the building reflections at our test site. In contrast, the experimental curve generally has more fluctuations than the theoretical curve, suggesting the presence of multi-path components not included in the model. To explore this possibility, swept frequency channel 1 Experimental Measured Signal Strength 6 Y 3 Power in dbm meters 4 CMRI Car 1 (site office) Car :5: :55: 3:: 3:5: 3:1: 3:15: Theoretical Signal Strength 1 Car 3 3 Power in dbm Aristech building 9 Lost packets :5: :55: 3:: 3:5: 3:1: 3:15: Lost packets :5: :55: 3:: 3:5: 3:1: 3:15: Time Figure 5 Experimentally measured signal strength, theoretically predicted signal strength and count of lost packets for a pair of two mobile nodes in the wireless ad hoc network. measurements were made from the parking lot in front of the Aristech building (Figure 3) using t
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks