View source for PARO: Conserving power in wireless ad-hoc networks

== Introduction ==

A reduction in the power consumption increases the operational lifetime of network enabled devices. Especially for small computing and communication devices with built-in or attached radios reducing the transmission power may extend operational lifetime.


=== What is PARO? ===
PARO is a power-aware routing technique for wireless ad hoc networks where all nodes are located within the maximum transmission range of each other.

PARO uses a packet forwarding technique where immediate nodes can elect to become redirectors on behalf of source-destination pairs.

As the required transmission power to communicate between any source and destination node is not proportional to the distance of them adding multiple intermediate redirectors may result in an overall lower power consumption compared to the direct communication.

=== PARO in comparison to other MANET routing techniques === 

PARO's approach is in direct contrast to existing MANET routing protocols:

*MANET protocols try to minimize the amount of hops therefore wasting power

*MANET routing protocols are not suitable for discovering optimal power-aware routes in wireless ad hoc networks

== PARO Model ==

Here the PARO Model is beeing described including the link assumption, the way PARO calculates the cost of transmission power as well as the operation of the PARO protocol.

=== Link Assumptions ===

*radios need to be capable of dynamically adjusting transmission power

*Assumption: transmission power needed to transmit between nodes A and B is somewhat similar to transmission power between B and A

*Requirement: interference-free Media Access Control (MAC) found in frequency band radios such as Channel Sense Multiple Access (CSMA)

*Every data packet successfully received is acknowledged at the link layer

*Nodes in the network are capable of overhearing any transmission by other nodes as long as the received signal to noise ratio (SNR) is above a certain minimum value

=== Cost Function ===
Assuming a network with several static nodes:


*A node keeps its transmitter “on” to transmit one data packet to another node for L/C seconds
**L:  size of transmitted frame in bits
**C: raw speed of wireless channel in bits/s


*Receiver node keeps transmitter “on” to acknowledge a successful data transmission for a combined period of l/C seconds
**l: size of the acknowledgment frame including layer 2 headers

Cost function for transmitting Q packets between a given source-destination pair along the best route then is:

<center><math>P_k = R_k + Q \cdot \sum_{i = 0}^{N_k} = \frac{T_{i,i+1} \cdot L + T_{i+1,i} \cdot
l}{C}</math></center>

*<math>T_{i,j}</math> : minimum transmission power at node i such that the receiver node j along route k is still able to receive the packet correctly

*<math>N_k</math> : number of times a data packet is forwarded along route k including the source node

===Protocol Operations ===

*Before transmitting a packet, a node updates its packet header to indicate the power required to transmit

*Nodes capable of overhearing source and destination can compute whether packet forwarding can reduce transmission power in comparison to direct exchange

*In that case an intermediate node may elect to become a redirector and send a route-redirect message to the source and destination


== Protocol Design ==

In this chapter the three core algorithms of PARO are described.

=== Overhearing ===

*Processes packets that are successfully received by the MAC

*Creates or refreshes a cache entry in the overhear table

*This cache entry contains the triple:<math>[ID, time, T^{min}]</math>
**ID: Unique identifier (e.g. MAC or IP=
**time: time at which the packet was overheard
**<math>T^{min}</math>: minimum transmission power needed to reach overheard node

=== Redirecting ===

*Responsible for performing the route optimization

*Performs 2 operations:
**Compute-redirect: computes whether a route optimization between two nodes is feasible
**Transmit-redirect: determines when to transmit route-redirect messages

=== Route Convergence ===

*Repeatedly adding more redirectors between source-destination nodes to further optimize a route into smaller steps (one step at a time)
**Multiple iterations are required to establish an optimum route
**PARO will converge as fast as transmission rate of data transmitted by the source

*PARO converges fast and linear with the number of required iterations
**A certain optimum in power savings is reached with about three redirectors.
**Further redirectors barely improve power savings

== Mobility Support ==
Here the modifications for the core algorithms are discussed thatare necessary for mobile nodes in the network.

=== Route Maintenance ===
*Data packets are the main source of routing information for PARO

*For mobile nodes data traffic alone may not be sufficient to maintain routes

There is a need to maintain a minimum rate of packets between source and destination pairs to discover/maintain routes as redirectors move in and out of existing routes


=== Overhearing ===

A node transmitting a packet to the next hop redirector in the route has to determine the next hop’s current range

If a node transmits a packet assuming that the next hop’s current range is the same as the last recorded range, then three scenarios may occur.

1. Current position of the next redirector is within the current transmission range (some power is wasted)

2. Current position of the next redirector is at the same transmission range (optimum)

3. Current position of the next redirector is outside the current transmission range (worst case)

Solution: 
*transmit a packet with a higher transmission range than previously recorded

*Increase in transmission range depends on average speed of nodes, time interval between the last time the redirector was overheard and the current time

=== Redirecting ===

Because of mobility a redirector may move away:
*it no longer helps to optimize the transmission power between two communicating nodes.
*It is necessary to remove a node from the path using a route-redirect message

== Performance Overview ==
Here the results of simulations and tests made by the PARO-team are summarized.

*Route Convergence
** As expected PARO converges appropriate to the inter-packet interval times
** the faster nodes can transmit the faster PARO discovers power-efficient routes

*Power Optimization
** PARO can save a large amount of power even with only few redirectors
** Adding more and more redirectors does not save much more power after having added three redirectors
** PARO saves power even without redirectors because it only transmits at the required power level while standard WLAN always sends with maximum power

*Route Maintenance:
** Nodes travel and transmit fast: very high transmission success rate. PARO can update its route information in time thanks to the very high transmission rate
** Nodes travel slowly: very high transmission success rate. PARO does not need to update routes very often so no matter what the transmission rate is the routes can be maintained.
** Nodes travel fast but transmit slowly: low transmission success rate. The nodes travel faster than PARO can update the routes due to low transmission rates. Therefor a lot of packets are lost.

== Qualitiy of Service ==

In this chapter the effect of PARO on the networks performance is discussed.

*Main QoS tradeoff: average number of times a packet is forwarded versus average number of interfering nodes per transmission

*Every time a node attempts to transmit and senses the medium is busy it backs off for an exponentially increased period of time

*Result: theoretical channel utilization of a simple chain network with 5 nodes is ¼ of the maximum capacity

*Simulations regarding throughput and delay showed the weakness of PARO
** With increasing numbers of redirectors the throughput drops strongly while the delay is increased.
** For instance with zero redirectors the simulation showed a throughput of about 1.7 mbps while with only three redirectors this droped below 0.5 mbps.

== Conclusion ==

*An implementation of PARO using IEEE 802.11 showed a basic proof of concept though some anomalies were identified

*In general more work is necessary to improve QoS-aspects which are the biggest problem PARO has at the moment.

For details and pictures please see the [http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/14.pdf PARO paper].

--[[User:Ertelt|Ertelt]] 15:49, 7 Feb 2005 (CET) 

== Discussion ==

The discussion in the seminar was centered around the QoS-aspects mostly. For networks where performance is not as important as lifetime PARO is the way to go. However until the performance can be increased the use of PARO for commercial MANETs where throughput and delay are of importance is limited.
Also we discussed the problem of nodes beeing used very often. Even with PARO minimizing power costs per packet certain nodes that are very often used as redirectors will run out of power sooner or later. It would be wise to take power supply of each node into account for route discoveries so nodes with a depleted power supply are not beeing used if not really necessary.

== Credits ==

[1] Javier Gomez, Andrew T. Campbell, Mahmoud   Naghshineh, Chatschik Bisdikian, PARO: Supporting Dynamic Power Controlled Routing in Wireless Ad Hoc Networks, in: Wireless Networks 9, 443-460, 2003