Mobile Ad Hoc Data Networks for Emergency Preparedness
`
`Telecommunications - Dynamic Power-Conscious Routing Concepts
`
`Madhavi W. Subbarao
`Wireless Communications Technologies Group
`National Institute of Standards and Technology
` Bureau Drive Stop  
`Gaithersburg, MD, USA  - 
`
`February , 
`
`Submitted as an interim project report for Contract Number DNCR to the National
`
`Communications Systems.
`
`
`
`Apple Inc. 1019
`U.S. Patent No. 9,445,251
`
`

`

`I. Introduction
`
`In the next generation of wireless communication systems, there will be a need for the
`
`rapid deployment of independent mobile users. Signicant examples include establishing
`
`survivable, ecient, dynamic communication for emergencyrescue operations and disaster
`
`relief eorts, e.g., the bombing of the Oklahoma City Federal Building, or the aftermath of
`
`a hurricane where cellularPCS service may not be available. Typically, emergencyrescue
`
`communication is centralized, and the network is dependent on proper function of the central
`
`controllers. If the centralized infrastructure were to fail due to a disaster or any other reason,
`
`the network may collapse. Hence, advances in wireless communication should aid in making
`
`emergency preparedness systems and disaster relief networks robust and autonomous, and
`
`provide for reliable and secure inter-group communication.
`
`Rescue operations and disaster relief scenarios cannot rely on centralized and organized
`
`connectivity, and can be termed as wireless mobile ad hoc networks MANETs for emer-
`
`gency telecommunication. A MANET is an autonomous collection of mobile nodes that
`
`communicate over relatively bandwidth-constrained wireless links. Each node is equipped
`
`with wireless receivers and transmitters using antennas that may be omni-directional, highly
`
`directional, or possibly steerable. Since nodes are mobile, the network topology may change
`
`rapidly and unpredictably over time. The network is decentralized, where all network activ-
`
`ity including discovering the topology and delivering messages must be executed by the nodes
`
`themselves, i.e., routing functionality will be incorporated into mobile nodes. A MANET
`
`for emergency telecommunication may operate in a stand-alone manner or be connected to
`
`a larger network.
`
`The set of applications for emergency MANETs is diverse, ranging from small, static net-
`
`works that are constrained by power sources, to large-scale, mobile, highly dynamic networks.
`
`The design of network protocols for these networks is a complex issue. Regardless of the
`
`application, emergency telecommunication MANETs need ecient distributed algorithms
`
`to determine network organization connectivity, link scheduling, and routing. However,
`
`determining viable routing paths and delivering messages in a decentralized environment
`
`
`
`

`

`where network topology uctuates is not a well-dened problem. While the shortest path
`
`based on a given cost function from a source to a destination in a static network is usually
`
`the optimal route, this idea is not easily extended to MANETs. Factors such as variable
`
`wireless link quality, propagation path loss, fading, multiuser interference, power expended,
`
`and topological changes, become relevant issues. An emergency telecommunication network
`
`should be able to adaptively alter routing paths to alleviate any of these eects in order to
`
`maintain the performance and dependability of the network.
`
`In this report, we focus on the Network Layer operation of routing and implications of
`
`power consumption for emergency MANETs. We discuss the benets of power conscious-
`
`ness and conduct an initial investigation on the eects of energy-ecient wireless routing in
`
`MANETs. We develop an initial dynamic power-conscious routing scheme minimum power
`
`routing - MPR that incorporates physical layer and link layer statistics to conserve power,
`
`while compensating for the propagation path loss, shadowing and fading eects, and inter-
`
`ference environment at the intended receiver. The main idea of MPR is to select the path
`
`between a given source and destination that will require the least amount of total power ex-
`
`pended, while still maintaining an acceptable signal-to-noise ratio SNR at each receiver. A
`
`cost" function is assigned to every link reecting the transmitter power required to reliably
`
`communicate on that link. Routing decisions and cost updates are made based on feedback
`
`or information extracted from the received signal and special control packets. As an initial
`
`approach, we use the distributed Bellman-Ford algorithm to perform shortest" path routing
`
`with the cost functions as the link distances. The resulting shortest path" is the MPR path
`
`from a given source to a destination. We compare the performance of MPR to the common
`
`routing protocols of shortest distance routing with power control SD-PC and minimum
`
`hop routing with power control MH-PC, and present our preliminary results.
`
`II. Benefits of Power Consciousness
`
`In an emergency telecommunication scenario, power may be supplied to static nodes
`
`through a generator, while mobile nodes operate o a battery supply. Clearly, a vital issue
`
`
`
`

`

`for emergency MANETs then is to conserve power while still delivering messages reliably,
`
`i.e., achieving a high packet success rate. This can be accomplished by altering the trans-
`
`mitter power of the emergency telecommunication nodes to use just that amount needed to
`
`maintain an acceptable SNR at the receiver. Reducing the transmitter power allows spatial
`
`reuse of the channel and thus, increases network throughput  . Using power control in
`
`an emergency situation mitigates the multiuser interference since a transmission will not
`
`interfere with as many nodes. This will increase the number of emergency or rescue mission
`
`nodes that may communicate simultaneously. Altering the transmission power also reduces
`
`the amount of interference caused to other emergency preparedness telecommunication net-
`
`works or any other wireless network operating on adjacent radio frequency channels.
`
`In
`
`networks where nodes operate on battery power, e.g, hand-held radio being used by a res-
`
`cue worker, conserving power is crucial since battery life determines whether a network is
`
`operational or not. For certain emergency telecommunication MANET applications - for
`
`example, hostage situation or terrorist attack - it is desirable to maintain a low probability
`
`of intercept andor a low probability of detection . Hence, rescue mission nodes would
`
`prefer to radiate as little power as necessary and transmit as infrequently as possible, thus
`
`decreasing the probability of detection or interception.
`
`The benets of power conservationcontrol for emergency MANETs prompt the impor-
`
`tant question: What is the most power ecient way to route a packet from a source to a
`
`destination such that the packet is received with an acceptable packet success rate ? Since
`
`channel conditions and multiuser interference levels in an emergency situation are constantly
`
`changing with time, the transmitter power necessary on a particular link must be determined
`
`dynamically.
`
`Previous research in the area of routing for MANETs has focused on establishing routes
`
`between dierent source and destination pairs protocols proposed in the Internet Engineer-
`
`ing Task Force - MANET Working Group. A connection between two nodes is considered
`
`either present" or absent" depending on if the distance between the nodes is less than or
`
`greater than a threshold distance. All links that are present" are regarded as having the
`
`
`
`

`

`same link quality. This is a generalization assumption since the quality of any particular
`
`link depends on its location and surroundings. It is known that a node can exhaust its power
`
`supply trying to communicate reliably over a link that has a severe fade. Moreover, a cen-
`
`trally located node may experience excess trac and multiuser interference. Communicating
`
`through this node may be inecient and require many retransmissions, thereby expending
`
`more power. More recently, in , Wieselthier, Nguyen, and Ephremides addressed the prob-
`
`lem of power conservation in the context of wireless multicasting, and in  , Pursley, Russell,
`
`and Wysocarski considered this problem in a frequency-hopping ad-hoc network.
`
`III. Power-Conscious Routing
`
`There are clear benets to conserving power in emergency telecommunication MANET
`
`applications, as discussed in Section II. In this Section, we develop a new power conscious
`
`routing concept for MANETs.
`
`A. System Model
`
`Consider a transmitter communicating with a receiver at a distance of r in a MANET.
`
`As the transmitted signal propagates to the receiver, it is subject to the eects of shadowing
`
`
`
`and multipath fading, and its power decays with distance, i.e., PR  KF PT r(cid:0) , where K is a
`
`constant, F is a non-negative random attenuation for the eects of shadowing and fading, PT
`
`is the transmitter power, and  is the path loss exponent. At the receiver, the desired signal
`
`is corrupted by interference from other active nodes in the network. We assume that nodes
`
`know the identity of all other nodes in the network and the distances to their immediate
`
`neighbors, i.e., nodes that are within transmission range. Interfering nodes use the same
`
`modulation scheme as the transmitter and nodes can vary their transmit power up to a
`
`maximum power Pmax. We assume that the multiuser interference is a Gaussian random
`
`process. At the receiver, the decoder maintains an estimate of the average SNR.
`
`
`
`

`

`B. Minimum Power Routing Concepts
`
`The aim of MPR is to route a packet on a path that will require the least amount of
`
`total power expended and for each node to transmit with just enough power to ensure that
`
`the transmission is received with an acceptable bit error rate . Threshold  is a design
`
`parameter and may be selected according to the network performance desired. Let E be the
`
`bit-energy-to-noise-density ratio, Eb=Nef f , necessary at a node to achieve .
`
`Without loss of generality, consider a transmission from node i to node j, where i = j, and
`
`i; j  f ; : : : ; Ng, where N is the number of nodes in the network. The received Eb=Nef f is
`
`given by
`
`" Eb
`Nef fij
`
`=
`
`PRij =D
`N + PIij =W
`
`;
`
` 
`
`where D is the data rate in bits per second, W is the system bandwidth in Hertz, N= is the
`
`power spectral density of the thermal noise, PIij is the power of the interference at node j
`
`due to all nodes excluding node i, and PRij is the received power at node j due to node i.
`
`From the description in Section III-A, it follows that the received power is given by
`
`PRij = KFijPTij r(cid:0)
`ij ;
`
`
`
`where PTij is the transmitter power used at node i to communicate with node j, Fij is a
`
`non-negative random attenuation for the eects of shadowing and fading on link ij, and rij
`
`is the distance between node i and node j. Substituting  into  , we obtain
`
`where
`
`Nef fij
`" Eb
`
`= Sij PTij r(cid:0)
`ij ;
`
`Sij =
`
`KFij
`DN + PIij =W 
`
`;
`
` 
`
`
`
`may be interpreted as a dynamic link scale factor reecting the current channel character-
`
`istics and interference on link ij. These scale factors reect a link’s most recent reception
`
`environment. Note that Sij = Sji since channel conditions are not symmetric.
`
`
`
`

`

`It is desirable for Eb=Nef f ij to equal the energy ratio E, since this is the minimum
`
`Eb=Nef f necessary to achieve the bit error rate . Hence, with knowledge of scale factor
`
`Sij, node i can easily determine the power PTij necessary to achieve this goal using Eq.  ,
`
`i.e.,
`
`PTij =
`
`E
`Sijr(cid:0)
`
`ij
`
`:
`
`
`
`Let Eb=Nef f ij be an estimate of the received bit energy ratio at the output of the decoder
`at node j. Many methods may be used to determine Eb=Nef f ij, e.g., using side information
`by embedding known test symbols in packet transmissions . Although PTij was selected
`
`to achieve energy ratio E at the receiver, since network conditions are changing, the actual
`
`received Eb=Nef f ij may dier from E. If node j has knowledge of the transmitter power
`
`PTij which can be accomplished by including PTij in the packet header, it can update its
`
`estimated scale factor using a smoothing function as follows,
`
`^Sij =  (cid:0) 
`
`Eb=Nef f ij
`PTij r(cid:0)
`
`ij
`
`+ ^Sij ;
`
`
`
`which mitigates the uctuations due to multiuser interference and is a smoothing factor.
`
`An initial value for ^Sij may be computed as described in Section III-C. The estimated
`
`link scale factor ^Sij accounts for variable channel conditions and for all types of Gaussian
`
`interference, e.g., multiuser interference and partial-band jamming. If the received bit error
`
`rate ij on link ij is less than threshold , the eect of  is that node j decreases its
`
`link ^Sij value, indicating an increase in its interference noisy channel level, and thus, an
`
`increase in the power necessary to communicate on link ij as computed by . The opposite
`
`behavior occurs when ij is greater than .
`
`Each time node j receives a packet from a node i, it computes and stores a value for ^Sij
`
`that accurately reects its current SNR on link ij. We assume that the rate of change of
`
`the network is much slower than a packet transmission interval, and hence the value for ^Sij
`
`is valid for many packet transmissions.
`
`
`
`

`

`For every pair of nodes i and j, a cost Cij given by
`
`PTij  + 
`
`if PTij  +   Pmax;
`
`
`
`otherwise;
`
`
`
`Cij = 
` :
`
`is assigned, where  is a dampening constant to inhibit oscillations. The inequality in 
`
`is necessary since the transmitter power is limited by Pmax. The cost Cij is the power
`
`necessary to communicate from node i to node j to compensate for channel conditions and
`
`interference. Since nodes only know estimates of the link scale factors, the power required
`
`on a link must be overplayed. Thus,  provides an extra margin for the transmission power
`
`and is a design parameter that must be selected. As an initial approach, the distributed
`
`Bellman-Ford algorithm can be used to perform shortest" path routing with the Cijs as
`
`the link distances. The resulting shortest path" is the MPR path from a given source to
`
`a destination. If there is more than one path with the same minimum total cost, the MPR
`
`path is chosen as the one with the smallest maximum cost on any one link. MPR avoids
`
`congested areas and is also minimax optimal, i.e., given some uncertainty in the link scale
`
`factors, it minimizes the worse case total path cost.
`
`C. Network Implementation
`
`Initially, nodes transmit using power Pmax, and the cost of every link is set to a constant
`
`d, where d = Pmax + . This will result in nodes initially routing packets according to
`
`the minimum number of hops to the destination. The rst time node j for j  f ; : : : ; Ng,
`
`receives a transmission from another node, say node i, it will compute its link scale factor
`
`^Sij, i.e,
`
`^Sij =
`
`Eb=Nef f ij
`Pmax r(cid:0)
`
`ij
`
`:
`
`
`
`The link costs will be computed as described in Section III-B and propagated throughout
`
`the network. If the cost of a particular link has not yet been computed within a specied
`
`amount of time because no data packet was transmitted on that link, a boost" packet is
`
`transmitted on the link and the link cost is computed. Once all of the link costs have been
`
`computed, the routing protocol is now MPR.
`
`
`
`

`

`The MPR path costs must be periodically circulated around the network. This information
`
`can be passed around via data packets, acknowledgments, and special control packets known
`
`as packet radio organization packets PROPs . For this initial implementation, we assume
`
`an underlying information dissemination scheme.
`
`A dynamic routing table is maintained by each node. For each destination, a node stores
`
`the outgoing link for the most power-ecient route and the corresponding path cost, dis-
`
`tance to the destination, and the necessary transmitter power. Since network conditions
`
`are changing, routing tables are continually updated based on an update interval, and the
`
`transmission power is altered on a per packet basis according to Eq. . Before an update,
`
`if a link cost is deemed out-dated, i.e., the cost has not been recomputed within a specied
`
`interval before an update, a boost" packet is transmitted on that link in order to compute
`
`a current link cost.
`
`IV. Performance of Power Conscious Routing
`
`We compare the performance of MPR to that of SD-PC and MH-PC, and present our
`
`preliminary results. The transmission power for SD-PC and MH-PC is altered to overcome
`
`the distance between the transmitter and intended receiver. We use the modeling and
`
`simulation tool OPNET to build a network prototype and execute the simulations. We
`
`assume a MANET using the ALOHA random access protocol. We consider a slow fading
`
`log-normal shadowing environment, and vary the random attenuation eects on a link
`
`every TS seconds according to a correlation factor. We assume that a node has knowledge
`
`of the transmitter power used to communicate with it and hence, uses  to update the
`
`estimate of its link scale factor. A list of the simulation parameters is given in Table I.
`
`Performance measures of end-to-end throughput, end-to-end delay, eciency, and average
`
`power expended are used to analyze the performance of the routing protocols. End-to-end
`
`throughput is dened as the number of packets that successfully reach their nal destination
`
`per unit time. End-to-end delay is based only on successful packets and is dened as the
`
`average time required for a packet to arrive at its destination. Eciency is the number
`
`
`
`

`

`of received data packets divided by the total number of data packets and control packets
`
`transmitted. Average power expended is the average power consumed in the network relay-
`
`ing successful packets including necessary control packets from their source to their nal
`
`destination per unit time.
`
`First, we consider a  node static network with packet generation rate = pack-
`
`etssecondnode and a total of ; packets being exchanged. The routing table update
`
`interval is s, and the shadowing parameters are = : and TS = s. From Table II, we
`
`see that MPR achieves approximately double the throughput for similar power consumption
`
`levels, or alternatively, requires approximately : times less power for similar throughput
`
`levels. The overall end-to-end delay is comparable for all schemes. While MPR does not op-
`
`timize on the number of hops, it routes around undesirable links and hence, requires overall
`
`lower power consumption.
`
`Parameter
`
`Value
`
`Network area
`
` m x  m
`
`Data rate
`
` Mbps
`
`Max TX powerrange
`
` mW m
`
`Min frequency
`
`Bandwidth
`
`. GHz
`
` MHz
`
`Modulation
`
`Direct-Sequence BPSK
`
`Processing Gain
`
`Packet length
`
` dB
`
` bits
`
`Shadowing
`
` log F  N ; dB 
`
`, , , 
`
` x (cid:0); :; :; :
`
`Table I: Network simulation parameters.
`
`Next, with the same network conguration, we vary the packet generation rate and plot
`
`the eciency and average power expended in Figures and  respectively. We see that as
`
` increases, the eciency increases until the point where further packet generation causes
`
`excess levels of network trac, and thus, a decrease in eciency. MPR achieves approxi-
`
`mately double the eciency as SD-PC and MH-PC for low values of and approximately
`
`
`
`

`

`Measure
`
`MPR SD-PC SD-PC MH-PC MH-PC
`
`Hops
`
` 
`
` 
`
`  
`
`
`
` 
`
`Overhead
`
`.
`
`
`
`Pk delay*s
`
`Pk pwr*mW
`
`.
`
` 
`
`Hop pwr*mW
`
` .
`
`Eciency
`
`Thruput pks
`
`. 
`
` .
`
`.
`
`
`
`
`
`. 
`
` .
`
`
`
`
`
`
`
` .
`
`.
`
`. 
`
`
`
`.
`
`
`
`
`
`. 
`
` .
`
`
`
`.
`
`
`
` .
`
`.
`
`.
`
`Table II: Simulation results for a  node static network. * mean value of three trials
`
`a striking : times higher eciency for larger values of , since MPR adapts to changing
`
`interference levels. For low values of , MPR utilizes from  (cid:0)  less power relaying
`
`successful packets than SD-PC and MH-PC. For higher values of , although MPR utilizes
`
`approximately mW more power than SD-PC and MH-PC, since both MH-PC and SD-PC
`
`achieve low eciency, most of the total power expended in those schemes is on unsuccessful
`
`transmissions.
`
`Finally, we introduce mobility into the network with nodes moving at a speed of m=s
`
`and investigate the eect of dierent routing table update intervals on MPR. The packet
`
`generation rate is = packetssecondnode. In Figure , we plot the network eciency
`
`verses update interval frequency s. We consider the eciency of only data transmissions,
`
`and the global eciency of both data and control packets, i.e., data packets received divided
`
`by total communication packets - both data and control. We see that as the update interval
`
`decreases, the data eciency increases since the routing information utilized is more current.
`
`However, the global eciency increases until it reaches a point where further updates cause
`
`too much overhead communication, and hence, a decrease in network eciency. Clearly,
`
`there is a trade-o between utilizing current routing information and the communication
`
`overhead generated. It is our conjecture, that the optimum update interval is the same as
`
`the slow fading duration TS.
`
`
`
`

`

`Figure : Eciency vs. Packet generation rate .
`
` 
`
`

`

`Figure : Average power expended vs. Packet generation rate .
`
`
`
`

`

`
`
`94
`
`Q2
`
`90
`
`88
`
`88
`
`Efficiency
`
`84
`
`82
`
`
`
`—a— Efficiency (data)
`--n-- Efficiency (global)
`
`
`
`fat“
`
`f
`
`" “a.“
`
`If
`.f
`
`2’
`
`“.fidh‘a
`
`‘-
`
`)h'h
`
`"wk
`
`'\.
`
`‘0
`
`\-
`
`‘-\_
`
`‘1
`
`‘-
`
`‘-
`
`
`
`
`|
`|
`|
`|
`|
`5
`10
`15
`20
`25
`
`80
`
`0
`
`Update frequency (3}
`
`Figure : MPR: Eciency vs. Update frequency s.
`Update frequency (5)
`Figure 3: MPR: Efficiency vs.
`
`14
` 
`
`

`

`V. Conclusion and Future Directions
`
`Rescue operations and disaster relief scenarios cannot rely on centralized and organized
`
`connectivity, and fall in the domain of MANETs for emergency telecommunication. In this
`
`study, we discussed the benets of power consciousness for emergency application MANETs
`
`and conducted an initial investigation of energy-ecient wireless routing in MANETs. We
`
`developed power conscious concepts - MPR -, which adapt to the changing channel conditions
`
`and interference environment of a node. We presented our preliminary results and conclude
`
`that MPR shows promise as a power conscious routing scheme for MANETs.
`
`The performance of MPR indicates clear benet to employing power conscious concepts
`
`in the routing operation for MANETs. As an initial investigation, we used the distributed
`
`Bellman-Ford algorithm to determine the routing paths. Since MANETs have various ap-
`
`plications and network congurations, it is unlikely that one routing algorithm will obtain
`
`the best performance in all situations. Hence, it is important to be able to apply the power
`
`conscious concepts to other distributed MANET algorithms. As a future direction, we will
`
`extend the power conscious concepts developed herein to other MANET routing algorithms.
`
`As a supporting study to this work, we will provide a survey of existing wireless radios and
`
`their respective power adjustment capabilities. This will aid in determining which wireless
`
`radios are better suited for power adjustment in emergency preparedness telecommunication.
`
`VI. Resulting Publications
`
` J.S. Pegon and M.W. Subbarao, Simulation Framework for a Mobile Ad-Hoc Net-
`
`work," Proceedings of OPNETWORK , Washington DC., Sept. .
`
` M.W. Subbarao, Dynamic Power-Conscious Routing for MANETs: An Initial Ap-
`
`proach," Proceedings of IEEE VTC Fall , Amsterdam, The Netherlands, Sept.
`
` .
`
` M.W. Subbarao, Dynamic Power-Conscious Routing for MANETs", NIST Journal of
`
`Research, Volume , Number , Nov.-Dec. .
`
` 
`
`

`

`Acknowledgments
`
`I would like to thank Jean-Sebastien Pegon for his hard-work and diligent eorts in creating
`
`the simulation environment in OPNET, executing the simulations, and producing the plots.
`
`References
`
`  L. Kleinrock and J. Silvester, Spatial reuse in mutlihop packet radio networks," Proc.
`
`IEEE, vol. , pp.  , Jan. .
`
` M. B. Pursley, The derivation and use of side information in frequency-hop spread
`
`spectrum communications," IEICE Trans. Commun., Special Issue on Spread Spectrum
`
`Techniques and Applications, vol. E-B, pp.  , Aug. .
`
`  M. B. Pursley, H. B. Russell, and J. S. Wysocarski, Energy-ecient routing in frequency-
`
`hop packet networks with adaptive transmission," in Proc. IEEE MILCOM, .
`
` F. J. Ricci and D. Schutzer, U.S. Military Communications. Rockville, MD.: Computer
`
`Science Press, .
`
` M. W. Subbarao, On Optimizing Performance in Mobile Packet Radio Networks. PhD
`
`thesis, The Johns Hopkins University, Dept. Electrical Engineering, Baltimore, MD, Mar.
`
` .
`
` L. Westcott and J. Jubin, A distributed routing design for a broadcast environment,"
`
`in Proc. IEEE MILCOM, vol. , Boston, MA, pp. .. , Oct. .
`
` J. Wieselthier, G. D. Nguyen, and A. Ephremides, Multicasting in energy-limited ad-hoc
`
`wireless networks," in Proc. IEEE MILCOM, Bedford, MA, Oct. .
`
` 
`
`