Internet DRAFT - draft-brown-eadsr
draft-brown-eadsr
Internet Draft T. X Brown
Expires: 23 December 2003 S. Bhandare
S. Doshi
University of Colorado, Boulder
23 June 2003
The Energy Aware Dynamic Source Routing Protocol
<draft-brown-eadsr-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Comments on this draft may be sent directly to the authors.
Abstract
The energy aware dynamic source routing (EADSR) protocol is an
extension to the dynamic source routing (DSR) protocol for mobile ad
hoc networks. It retains the features and benefits of DSR while it
incorporates new features for energy limited nodes. The EADSR
features include (1) a DSR header option so that link power costs
can be passed with source routes; (2) an extended route discovery
protocol to find lower energy routes than minimum hop routes; and
(3) an additional route maintenance mechanism that allows the source
node to respond to link changes without route disruption. The
protocol is able to find routes with minimum total transmit power
cost. It is able to track changes in link power on a route, choose
between routes based on cost, and notify the source of new lower
cost routes as they become available. This document specifies the
EADSR header option and operation changes to DSR.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page i]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
Table of Contents:
Status of This Memo i
Abstract i
Table of Contents ii
1. Introduction 1
2. Assumptions 2
3. EADSR Protocol Overview 4
3.1. EADSR Route Discovery . . . . . . . . . . . . . . . . . . . 4
3.1.1 Route Request . . . . . . . . . . . . . . . . . . . . . 4
3.1.2 Gratuitous Replies . . . . . . . . . . . . . . . . . . 5
3.1.3 Operational Example . . . . . . . . . . . . . . . . . . 6
3.2. Additional Route Discovery Mechanism . . . . . . . . . . . 6
3.3. EADSR Route Maintenance . . . . . . . . . . . . . . . . . . 7
4. Conceptual Data Structures 9
4.1. Energy Aware Link Cache . . . . . . . . . . . . . . . . . 10
4.2. Acknowledgement Table . . . . . . . . . . . . . . . . . . 10
5. EADSR Header Format 11
5.1. Fixed Portion of EADSR Header . . . . . . . . . . . . . . 13
5.2. Energy Aware Route Request Option . . . . . . . . . . . . 13
5.3. Energy Aware Route Reply Option . . . . . . . . . . . . . 13
5.4. Route Error Option . . . . . . . . . . . . . . . . . . . . 13
5.5. Acknowledgement Request Option . . . . . . . . . . . . . . 13
5.6. Acknowledgement Option . . . . . . . . . . . . . . . . . 13
5.7. Energy Aware Source Route Option . . . . . . . . . . . . . 13
5.8. Pad1 Option . . . . . . . . . . . . . . . . . . . . . . . 14
5.9. PadN Option . . . . . . . . . . . . . . . . . . . . . . . 14
6. Detailed Operation 14
6.1. General Packet Processing . . . . . . . . . . . . . . . . 14
6.1.1. Originating a Packet . . . . . . . . . . . . . . . . 14
6.1.2. Adding a DSR Options Header to a Packet . . . . . . . 15
6.1.3. Adding an EADSR Source Route Option to a Packet . . . 15
6.1.4. Processing a Received Packet . . . . . . . . . . . . 15
6.1.5. Processing a Received DSR Source Route Option . . . . 16
6.1.6. Handling an Unknown DSR Option . . . . . . . . . . . 16
6.2. Route Discovery Processing . . . . . . . . . . . . . . . . 17
6.2.1. Originating a Route Request . . . . . . . . . . . . . 17
6.2.2. Processing a Received Route Request Option . . . . . 17
6.2.3. Generating a Route Reply using the Route Cache . . . 18
6.2.4. Originating a Route Reply . . . . . . . . . . . . . . 18
Brown, Bhandare, Doshi Expires 23 December 2003 [Page ii]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
6.2.5. Processing a Received Route Reply Option . . . . . . 18
6.3. Route Maintenance Processing . . . . . . . . . . . . . . . 19
6.3.1. Using Link-Layer Acknowledgements . . . . . . . . . . 19
6.3.2. Using Passive Acknowledgements . . . . . . . . . . . 19
6.3.3. Using Network-Layer Acknowledgements . . . . . . . . 19
6.3.4. Originating a Route Error . . . . . . . . . . . . . . 19
6.3.5. Processing a Received Route Error Option . . . . . . 19
6.3.6. Salvaging a Packet . . . . . . . . . . . . . . . . . 20
6.3.7. Processing a Received Data Packet . . . . . . . . . . 21
6.3.8. Promiscuous mode operation . . . . . . . . . . . . . 21
6.4. Multiple Interface Support . . . . . . . . . . . . . . . . 21
6.5. Fragmentation and Reassembly . . . . . . . . . . . . . . . 21
6.6. Flow State Processing . . . . . . . . . . . . . . . . . . 21
7. Protocol Constants and Configuration Variables 21
8. Security Considerations 21
Acknowledgements 22
Appendix A. Implementation and Evaluation Status 22
References 22
Chair's Address 24
Authors' Addresses 25
Brown, Bhandare, Doshi Expires 23 December 2003 [Page iii]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
1. Introduction
The Energy Aware Dynamic Source Routing (EADSR) protocol [3,4]
serves to extend the Dynamic Source Routing (DSR) protocol [1,2] by
providing for energy conservation. In EADSR, the nodes in the
network select minimum energy routes to forward packets to each
other using dynamic transmit power control to transmit packets on
the medium. As topology changes occur, new minimum energy routes are
formed and these routes are automatically discovered and maintained
by EADSR.
The EADSR protocol allows nodes to dynamically discover source
routes to any destination in the ad hoc network along with the
minimum recommended transmit powers (MRTP) required for successful
communication for each link in the route. The data packet sent by a
node includes in its header the complete sequence of nodes that will
forward the packet to the destination. The header also includes link
energy information (LEI), such as the MRTP, for each link
in the route to the destination. Each node in the route transmits
the packet at the specified MRTP over the medium to the next node in
the sequence of the route. Due to the inclusion of the source route
and LEI in the header of each data packet, other nodes forwarding or
overhearing any of these packets can save this information for
subsequent use.
The current version of DSR does not discover the minimum energy
routes as described in [3]. Energy savings that can be obtained by
employing the dynamic transmit power control in multi-hop routes is
not exploited by DSR. This is the motivation of having an energy
aware extension for the DSR protocol. EADSR has been designed to
achieve energy savings in low mobility scenarios by the discovery
and maintenance of minimum energy routes within the network keeping
the overhead incurred in discovery and maintenance of these routes
at the same level as that of DSR.
The EADSR protocol is composed of three mechanisms that allow the
discovery and maintenance of energy aware routes in the ad hoc
network:
- The EADSR header option includes LEI along with DSR source
routes in Data, Route Request, and Route Reply packets.
- Energy Aware Route Discovery is similar to the Route Discovery
procedure in DSR with the ability to discover additional routes
that are minimum energy routes.
- Energy Aware Route Maintenance is the mechanism by which a source
node is able to maintain minimum energy routes. This is an
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 1]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
extension to the Route Maintenance mechanism used in DSR and
also involves detection of newly formed minimum energy routes due
to topology changes in the network and tracking the energy cost
of the links in the route.
Similar to the DSR mechanisms, Energy Aware Route Discovery and
Energy Aware Route Maintenance each operate entirely "on demand".
The overhead incurred due to these mechanisms scales well for
stationary and low mobility scenarios. As communication patterns
change, the routing packet overhead of DSR automatically scales to
only that needed to track the routes currently in use.
Using the Energy Aware Route Discovery mechanism, a node MAY learn
and cache multiple routes to any destination along with the minimum
transmit powers for each route. This provides a choice of routes
when the minimum energy route that is being used fails.
The EADSR protocol currently supports only bi-directional links.
This is unlike DSR that has a mechanism to support uni-directional
links as well as asymmetric routes.
This document specifies the operation of the EADSR protocol for
routing unicast IPv4 packets in multi-hop wireless ad hoc networks.
Advanced, optional features, such as Quality of Service (QoS)
support and efficient multicast routing, and operation of DSR with
IPv6 [6], are covered in other documents. The specification of
EADSR in this document provides a compatible base on which such
features can be added, either independently or by integration with
the EADSR operation specified here.
EADSR requires minimal addition to the DSR protocol. In a mixed DSR
and EADSR node scenario, it is expected that DSR nodes will maintain
full DSR functionality while EADSR nodes will maintain their energy
aware functionality to the extent that other EADSR nodes are in the
ad hoc network. This interoperabilty is not specified here, but,
the EADSR specification is designed for this feature to be added.
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [4].
2. Assumptions
The assumptions specified in the DSR draft hold true for the EADSR
protocol with the following additions.
The node MUST have the ability to measure the received signal
strength of each packet. The nodes SHOULD have the capability of
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 2]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
dynamic transmit power control on a per packet basis. The nodes
SHOULD know the maximum transmit power, minimum transmit power, and
receiver sensitivity of their interfaces. If these values are not
known and generic defaults are used, correct operation can not be
guaranteed. A node MAY have a single transmit power level in which
case its maximum and minimum transmit powers would be the same.
Nodes SHOULD be able to operate in so-called promiscuous mode that
allows them to receive any packet including packets directed to
other nodes. In case this feature is NOT supported, the
functionality of energy aware route discovery and energy route
maintenance mechanisms will be limited.
The underlying MAC layer SHOULD support bi-directional links. In
particular, a computed MRTP that allows packets to be received in
one direction of a link is assumed to allow packets to be received
in the opposite direction. If this is not the case, then correct
operation can not be guaranteed.
The design assumes that the EADSR protocol will be implemented in
scenarios where the nodes in the network are either static or low
mobility scenarios at pedestrian speeds. In particular, the link
changes are slow and the topology is stable over the time scale of
many end-to-end round trip times. Medium speed scenarios with
topology changes on the order of several end-to-end round trip
times, will function but with a large fraction of packets devoted to
route discovery and maintenance. High-speed scenarios with topology
changes faster than the end-to-end round trip time will deliver few
packets.
The energy aware route maintenance mechanism of the EADSR protocol
is proactive in a limited manner. When a packet is sent, other nodes
will notify the source with any better routing information for use
in future packets sent to the same destination. In order for this
information to be useful it is assumed that most packets are one of
multiple packets sent to the same destination.
This draft assumes energy use is proportional to the transmit power
used by the radio interface. This assumption is valid when link
distances are large and transmit power dominates all other signal
processing, computing, and receiving power. In general whenever
other power drains are small compared to transmit power this is
valid. The EADSR specification allows for more sophisticated
definitions of energy aware to be defined in future releases.
These alternate definitions would affect the ranking of different
routes. But, the primary EADSR function of route discovery, setting
transmit powers for each hop in a route, and route maintenance would
remain unchanged.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 3]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
The EADSR operation specified here is relative to the April 2003
Version 9 of DSR. For ease of comparison and reference, numbering of
subsections parallels the numbering in DSR.
3. EADSR Protocol Overview
This section describes the main route discovery and maintenance
features of EADSR. Details of the internal data structures, packet
header formats, and detailed operational descriptions are given in
later sections.
3.1. EADSR Route Discovery
When some source node originates a new packet addressed to some
destination node, the source node places in the header of the packet
a source route giving the sequence of hops along with the minimum
transmit powers at which the packet is transmitted for each hop. The
node will look up in its cache to select the minimum energy route to
the destination. If no route is found in the cache, it will initiate
route discovery similar to the route request flooding process
carried out in the DSR protocol. This is only guaranteed to find a
minimum hop route. Additional route refinement mechanism to find
minimum energy routes is implemented with a gratuitous route reply
mechanism.
3.1.1 Route Request
To discover a route, a route request packet is broadcast over the
medium at the maximum power of the interface. This is to maximize
the connectivity of the route request packet in the network. The
route request packet contains a source route (with only the source
so far), the link energy information for each link in the source
route, and the power that the route request packet will be
transmitted (the maximum power of the interface).
Nodes that receive this packet compute the MRTP based on the
transmit power and the receiver sensitivity of the node interface:
MRTP = Ptx - RSSI + T + M (MRTPequation)
where:
MRTP = minimum recommended transmit power (in dBm)
Ptx = power the previous node transmitted the packet (in dBm)
RSSI = power the current node received the packet (in dBm)
T = receiver sensitivity of the receive interface (in dBm)
M = added margin to ensure successful communication (in dB)
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 4]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
This information and any LEI in the route request packet can be
stored in a link cache for future use. The packet is further
processed.
If the node is the target destination for the route discovery, it
sends a "Route Reply" to the initiator of the route request packet
in which it includes the entire source route from the initiator to
the destination and the minimum transmit powers for each hop. The
route reply route is found by reversing the source route in the
route request and sending the packet with this source route. Each
node on the route forwards the packet to the next node and transmits
at the MRTP power computed for the link during the route request. In
this way the source learns a source route and the LEI for each link
on the route.
If the node is not the target of the route discovery it follows the
a similar procedure as the DSR Route Discovery procedure. If it has
already seen this route request, it discards the packet. Otherwise,
it adds itself to the source route, adds the LEI values for the link
from the previous node and adds the power that the route request
will be forwarded. The node then re-broadcasts the route request.
The interfaces used can have bounded range and discrete power
levels. Since these values are transmitter specific, the receiver
may not know them when it computes (MRTPequation). For this reason
the computed MRTP is forwarded as is during the route request. The
transmitting nodes bound or quantize the MRTP and reinsert it into
the LEI during the route reply.
The MRTP value is modified as follows. If the computed MRTP is
below the minimum transmit power of the interface it is set to the
minimum power value. If the computed MRTP is above the maximum
transmit power of the interface it is set to the maximum power
value. If the interface has discrete power levels the MRTP is
rounded up to the next available power level.
After initiating a route discovery, the sending node saves a copy of
the original packet in a local buffer called "Send Buffer". The
structure and operation of the Send Buffer is the same as described
in Section 4.2 of the DSR draft.
3.1.2 Gratuitous Replies
The EADSR route discovery process so far is equivalent to the DSR
route discovery process in that they will find the same set of
routes. EADSR will use power control to save energy and may choose a
different lower energy route than DSR. But, it may not find routes
that have significantly lower energy costs. For this reason EADSR
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 5]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
implements the following additional mechanism.
Each node listens to the unicast route replies using the
"promiscuous" mode and estimates the minimum transmit power value
from itself to the transmitting node using (MRTPequation). It then
looks up its cache to check if there exists a route from itself to
the next hop of the route reply packet whose total transmit power is
less than the power at which the packet is currently being
transmitted by the transmitting node. If such a route exist, the
node creates a gratuitous reply with the lower power route and
corresponding minimum transmit powers. This is sent to the initiator
of the route discovery.
As in 3.1.1, each node in the route reply checks the MRTP computed
for them by receivers and bound or quantize the value as appropriate
for their interface. The modified value is inserted into their LEI in
the EADSR header of the gratuitous reply.
3.1.3 Operational Example
Consider the example in the figure where the source node A wishes to
communicate to destination node D. The figure shows the packets
transmitted by each node over time with one time line for each node.
Node A initiates a route discovery by broadcasting a route request
packet at maximum power, M. Node B and node C receive this packet
and re-broadcast the same after adding themselves and the minimum
transmit power values from node A to the route request packet. Node
B and node C do not re-broadcast the route request that are
broadcast by them as each node will broadcast a route request at
most once.
Node D receives route requests from node B and node C and sends
route replies A-C-D and A-B-D with the respective transmit powers as
shown in the figure. Node B now listens to the route reply A-C-D and
discovers that it lies on a minimum power route A-B-C-D. It then
sends a gratuitous reply to node A informing it about this lower
power route. Node A, now has three routes, A-B-D, A-C-D, and
A-B-C-D. Since A-B-C-D is the lowest energy it chooses this route
to transmit data packets to destination node D. This is an example
of EADSR listening to the unicast route reply messages and
discovering additional low power routes that would never be
discovered using the DSR protocol.
3.2 Additional Route Discovery Mechanism
DSR optionally allows non-destination nodes to generate Route
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 6]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
--- ----
|Rqb| |DB |
|A | |ABCD|
|M | |vzy |
A---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--->
t
--- --- ---- -- ----
|Rqb| |RRA| |GRA | |AA| |DC |
|AB | |ABD| |ABCD| |- | |ABCD|
|vM | |vx | |v5y | |M | |vzy |
B---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--->
t
--- --- -- ----
|Rqb| |RRA| |AB| |DD |
|AC | |ACD| |- | |ABCD|
|wM | |wy | |M | |vzy |
C---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--->
t
--- --- --
|RRB| |RRC| |AC|
|ABD| |ACD| |- |
|vx | |wy | |M |
D---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--->
t
Legend
---
|RRA| = Packet type [route reply sent to A]
|ACD| = Source route [A->C->D]
|wy | = Per hop MRTP [w=power(A->C), y=power(C->D)]
---
Packet types
Rqb = Route Request broadcast
RRX = Route Reply sent on next hop to node X
DX = Data packet sent on next hop to node X
AX = Route level Ack packet reply to data packet from node X
GRX = Grat reply sent on next hop to node X
Replies from cached values. EADSR requires fresh routes in the
network to be optimal in minimum energy routing. Hence, route
discovery is carried out till the destination node replies with the
entire route instead of propagating stale routes in the cache by
replying from the cache. In EADSR the route replies from cache
option is disabled.
3.3 EADSR Route Maintenance
The source route header includes the list of intermediate nodes and
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 7]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
the MRTP for each link. The data packet is now transmitted by each
node in the route at the power level specified by the MRTP value in
the header.
On each forwarding link, the transmitting node expects a network
layer ACK in return. In case the ACK is not received within a
certain time interval, the node removes that link from the cache. As
in DSR, if it is not the source of the packet, it generates a route
error message specifying the link that is broken and sends the route
error packet to the source of the data packet. In any case, the
source chooses an alternate route or initiates a new route
discovery.
A node listens to DATA/ACK exchanges not directed to itself using
"promiscuous" mode and looks up its cache for a lower energy route
through itself to the next hop of the packet. If a lower energy
route is present, the node generates gratuitous reply with the route
and the minimum transmit powers, and sends it to the source node of
the data packet.
Energy Aware Route maintenance additionally involves tracking the
energy costs of the route. At every link in the route of a data
packet, the nodes compute the new estimate of MRTP for the link and
compares the value to the value specified in the header. In case
there is a substantial difference specified by a margin, a flag is
set in the source route header. The destination node checks this
flag when it receives the data packet and generates a gratuitous
route reply with the changed powers and sends it to the source of
the data packet.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 8]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
+-----+
t=t1 | B | P1
+-----+
|
v
+-----+
t=t2 | B | P2
+-----+
|
v
+-----+ +-----+ +-----+
| A | t=t3 | B | P3 | C |
+-----+ +-----+ +-----+
|
v
+-----+
t=t4 | B | P4
+-----+
|
v
+-----+
t=t5 | B | P5
+-----+
For example, node A and node C are exchanging data at controlled
power. Node B is a mobile node that moves from position P1 through
P5 at times t=t1 through t=t5. Node B listens to the DATA/ACK packet
exchange between node A and node C and estimates the energy cost of
the route ABC compared to the current route AC. At P1 the ABC route
has higher cost than AC and so node B takes no action. At P2, the
ABC route is lower cost so node B sends a gratuitous reply to node
A. Node A uses the new route. At P3, node B senses that power on the
AB link is significantly lower and so it sets the MRTP to the new
lower power and sets the link change flag in the header. Node C
upon seeing the flag set, sends a gratuitous reply to the source
with the new power information. Similarly at P4, node B senses that
the power on the AB link is significantly higher and it sets the new
MRTP and the link change flag. At P5, the power is again
significantly higher and Node B sets the new MRTP and the link
change flag. Node A upon receiving the information about the new
higher power, determines that the AC route is the lowest power and
uses route AC. Note that throughout this mobility the routing is
proactive and no route error is created.
4.Conceptual Data Structures
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 9]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
The DSR Send Buffer and Route Request Table Data structures are as
described in the DSR draft. EADSR adds two new structures.
4.1 Energy Aware Link Cache
This data structure stores individual links in the system in the
form of a neighbor table. It also stores the LEI of each link that
can be used to compute the energy cost metric for that link. The
LEI definition and how a cost is computed are in Section 5.
LEI SHOULD be added to the Link Cache every time the node receives a
Route Request, Route Reply, Gratuitous Reply, Data and ACK packets.
Each time information is added to the Link Cache, the node SHOULD
look up the Send Buffer to check if any outstanding packets can be
sent.
To search for a route to some destination node, the link metrics are
computed using the cached LEI information. The source node MAY use
the Dijkstra's minimum-cost algorithm as the graph search
algorithm.
When the node receives a Route Error packet, the corresponding link
entry is removed from the Link Cache.
Every entry in the Link Cache SHOULD be associated with a timeout.
If the link is not used within this timeout value, the entry MAY be
deleted from the cache.
4.2. Acknowledgement Table
In order to implement a network layer ACK mechanism on a link by
link basis, an ACK table is required. This is used to store the ACK
request entries that includes the ACK id, along with the copy of the
data packet sent out on the medium. Each entry is also
associated with a timeout value. If the ACK packet is not received
within this timeout value, the link is declared as invalid and this
link SHOULD be removed from the Link Cache. If the ACK packet is
received within the timeout value, the ACK entry is removed from the
ACK table.
Each entry in the ACK table contains the following fields:
- The Acknowledgement identifier of the acknowledgement request in
the data packet.
- The time at which the entry was added to the ACK table
- The copy of the data packet that is sent out on the wireless
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 10]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
medium.
This entry is deleted by the node either IF the ACK packet is
received for that entry or the timeout value expires.
As in DSR a retransmit mechanism MAY be implemented.
5. EADSR header format
The EADSR protocol uses all the options that are used by the DSR
protocol in addition to a special option denoted the EADSR option.
This optional header consists of the fields that carry energy aware
information. The format of the optional header is as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Version | Version Length|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Energy Information[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Energy Information[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Energy Information[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
EADSR fields:
Option Type
8. Nodes not understanding this option will ignore this
option as specified in 6.1 of the DSR draft.
Option Data Length
8-bit unsigned character. The length is given by the following
equation: (Version Length) * (Hop Count) + 2
Version
8-bit unsigned character. The current implementation of EADSR
is Version 1.
Version Length
8 bit unsigned character. This length specifies the length of
the LEI field in octets.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 11]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
Link Energy Information Field
This is a variable length field whose length is specified by
the Version length of the EADSR option. (The above diagram
shows a 4 octet LEI, but it could be any length as defined by
the Version and Version Length).
The LEI field MAY have different definitions in different versions.
The first octet of every field in every version SHOULD be the MRTP
as defined below for Version 1.
LEI[1] corresponds to the source to first node link in the source
route. LEI[2] corresponds to the first nodes to second node link,
etc. LEI[n] in every packet except Route Requests corresponds to
the link to the destination.
In Route Requests, LEI[n] corresponds to the node that is forwarding
the Route Request. The full LEI[n] field in a Route Request MAY
depend on the version number, but, the first byte MUST be the power
that the Route Request is being transmitted.
In Version 1 of EADSR, the Version Length is 1 octet. The LEI field
is an 8-bit signed integer indicating the MRTP in dBm for the
corresponding link.
On Route Request packets, LEI[n] is the power that the route request
packet is transmitted in dBm. The receiving node MUST compute the
MRTP for this hop according to (MRTPequation) and replace LEI[n]
with this computed MRTP.
On Data packets, the MRTP value MUST be the power that the packet is
actually transmitted on the link. If for any reason a node chooses
to change the transmit power for hop i, then it MUST set the MRTP
value in LEI[i] to the actual transmit power. If the new power
differs by more than M_Delta then the Link Flag is set as described
in Section 6.3.7.
On Route Reply packets, a node MAY transmit at a power different
than the MRTP in the LEI field. Route Replies are reversing a route
and the MRTP on the forward link may not be appropriate when the
link is reversed. The node that would transmit on hop i of a source
route MUST bound and quantize the LEI[i] MRTP to match its
capabilities as described in Section 3.1.1.
The energy cost of a route is the sum of the absolute MRTP values.
The MRTP values MUST be converted from dBm to absolute values for
this computation.
The EADSR option MAY be inserted either before or after the DSR
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 12]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
options. It SHOULD be present for the protocol to be identified as
the EADSR protocol.
5.1 Fixed Portion of EADSR header
This is the same as the DSR fixed portion of the header.
The EADSR options are the same as the DSR options. The EADSR header
option as described in the previous section is required with some
DSR options. The options are defined in the following sections. The
DSR Flow State Extension is NOT supported by EADSR. It MAY be
supported in future versions.
5.2 Energy Aware Route Request Option
The Energy Aware Route Request option in EADSR is the same as
described in Section 6.2 of the DSR Draft with the addition of the
EADSR header option.
5.3 Energy Aware Route Reply Option
The Energy Aware Route Reply option in EADSR is the same as
described in Section 6.3 of the DSR Draft with the addition of the
EADSR header option.
5.4 Route Error Option
This option remains the same as described in Section 6.4 of the DSR
draft.
5.5 Acknowledgement Request Option
This option remains the same as described in Section 6.5 of the DSR
draft. It is required on all Data packets in EADSR.
5.6. Acknowledgement Option
This option remains the same as described in Section 6.6 of the DSR
draft.
5.7 EADSR Source Route Option
The Energy Aware Source Route option in EADSR is the same as
described in Section 6.7 of the DSR draft with the addition of the
EADSR header option and the following modification. The right-most
bit of the Reserved field in the Source Route option header is
replaced by the Link Flag in the EADSR Source Route option.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 13]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len |F|L|Rsvd |f|Salvage|Segs Left |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The following fields are added to the existing DSR Source Route
option.
LinkFlag (f)
This flag indicates if the energy cost of any of the links in the
route have changed. This flag is set by a forwarding node if the
change in the cost of the link is greater or equal to a margin
M_Delta. The value of the flag is looked up by the destination
node when it receives a packet and if set, the destination sends
a gratuitous reply to the source node indicating the changed
energy cost value of the route.
5.8 Pad1 Option
This option remains the same as discussed in Section 6.8 of the DSR
draft.
5.9 PadN Option
This option remains the same as discussed in Section 6.9 of the DSR
draft.
6. Detailed Operation
To simplify the description only modifications to the DSR draft are
listed here. Within the DSR draft, references to within Section 8
MUST be interpreted as references to the corresponding section
within Section 6 of this draft so as to incorporate all
modifications here. Thus Section 8.1.1 in the DSR draft refers to
Section 8.1.2. This is interpreted as Section 8.1.2 in the DSR draft
with the modifications listed in Section 6.1.2 of this draft.
6.1 General Packet Processing
6.1.1 Originating a Packet
This processing is the same as that described in Section 8.1.1 in
DSR with the following modifications:
- When multiple routes are possible, the route with the lowest
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 14]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
energy cost SHOULD be chosen.
- If the Route Request option is present then the packet MUST be
transmitted at the maximum power of the interface.
- Otherwise, the packet MUST be transmitted at the MRTP as
specified in the first octet of LEI[1] in the EADSR header. The
ACK request option described in Section 6.3 MUST be included.
6.1.2. Adding a DSR Options Header to a Packet
The process of adding a DSR options header remains the same as that
described in Section 8.1.2 of the DSR draft.
6.1.3. Adding a EADSR Source Route Option to a Packet
The process of adding a DSR Source Route option remains the same as
that described in Section 8.1.3 of the DSR draft.
In addition, the EADSR header option is added according to the
following sequence of steps:
- The node creates a EADSR option as described in Section 5, and
appends it to the DSR Options header.
- The number of LEI fields to include in the EADSR option (n) is
the number of hops in the source route.
- The LEI for the links along the source route are copied into
sequential LEI[i] fields in the EADSR option, for i = 1, 2, ...,
n.
6.1.4. Processing a Received Packet
The processing of a received packet remains the same as that
described in Section 8.1.4 of the DSR draft with the following
modifications:
- If the DSR Options header contains an EADSR option, the node
SHOULD extract the energy information from the EADSR option and add
this information to its Link Cache. The energy information is the
sequence of link energy information fields
LEI[1], LEI[2], ..., LEI[n]
where LEI[i] corresponds to the i-th hop in the source route which
is derived as described in Section 8.1.4 of the DSR draft. The
value n here is the number of LEI fields in the EADSR option, or
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 15]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
(Opt Data Len - 2)/(Version Length).
- The Received Signal Strength (RSSI) is computed for the received
packet. The current hop, i, can be computed with each header
option described in 8.1.4. Extract the transmit power, Ptx, from
the first octet of LEI[i]. The MRTP is computed according to
(MRTPequation).
6.1.5. Processing a Received DSR Source Route Option
The processing of a received DSR Source Route Option remains the
same as that described in Section 8.1.5 of the DSR draft with the
following modifications:
- Route Shortening SHOULD NOT be performed.
- When a node receives a packet containing a DSR Source Route
Option, this packet could be either a packet that is overheard
due to the promiscuous mode operation, or it could be a normal
packet addressed to this node.
If it is a normal packet, the node SHOULD check the packet to
determine if it is the final destination.
If so,
- If the Link Flag is set, it SHOULD perform Energy Aware Route
Maintenance on the packet as discussed in Section 6.3.7.
- The node then strips the EADSR headers, and sends the packet
to the higher layers for processing.
If the node is NOT the final destination,
- It SHOULD perform Energy Aware Route Maintenance discussed in
Section 6.3.7.
- The node SHOULD look up the next hop address using the
procedure mentioned in DSR Source Route Processing of Section
8.1.5 of the DSR draft, and look up the corresponding transmit
power value for that hop. The packet SHOULD be transmitted at
the controlled power.
If the packet is overheard due to the "promiscuous" mode, the
packet is processed as discussed in Section 6.3.8.
6.1.6. Handling an Unknown DSR Option
This sections is the same as that described in Section 8.1.5 of the
DSR draft.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 16]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
6.2. Energy Aware Route Discovery Processing
Energy Aware Route Discovery is the mechanism by which a node S
wishing to send a packet to a destination node D obtains a minimum
energy source route with a list of minimum transmit powers to D.
Energy Aware Route Discovery is initiated only when the "initiator"
node S attempts to send a packet to "target" node D and does not
already know a route to D. The process of Energy Aware Route
Discovery is entirely on demand.
The Energy Aware Route Discovery procedure utilizes two types of
messages, a Route Request (Section 5.2) and a Route Reply (Section
5.3), to actively search the ad hoc network for a route to the
desired destination. These DSR messages MAY be carried in any type
of IP packet, through use of the DSR header as described in Section
5.
The condition for initiating Energy Aware Route Discovery are the
same described in Section 8.2 of the DSR draft.
6.2.1. Originating a Route Request
This section is the same as that discussed in Section 8.2.1 of the
DSR draft with the following modification.
The EADSR header option is added according to the following sequence
of steps:
- The node creates an EADSR option as described in Section 5, and
appends it to the DSR Options header.
- A single LEI field is included in the EADSR option.
- The first octet of the LEI field is set to the maximum transmit
power in dBm of the interface.
- The packet is transmitted at the maximum transmit power of the
interface.
6.2.2. Processing a Received Route Request Option
This section is the same as that discussed in Section 8.2.2 of the
DSR draft with the following modifications if the node further
processes the Route Request.
- The node SHOULD NOT reply with a route from its own cache.
- Set the first octet of LEI[n] in the EADSR option to the computed
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 17]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
MRTP for the previous hop.
- Append this nodes maximum transmit power to the LEI[i] list in
the EADSR option, and increase the value of the Opt Data Len
field in the EADSR option by Version Length.
6.2.3. Generating a Route Reply using the Route Cache
EADSR SHOULD NOT generate Route replies from its Link Cache.
6.2.4. Originating a Route Reply
This section is the same as that discussed in Section 8.2.4 of the
DSR draft with the following modifications:
- The EADSR header option is added according to the following
sequence of steps:
o The node creates an EADSR option as described in Section 5,
and appends it to the DSR Options header.
o The LEI fields are copied from the Route Request packet.
o The first octet of the LEI[n] field is set to the MRTP
computed from the last hop.
- The packet SHOULD be sent at the power represented by the first
octet of LEI[n].
- The condition of bi-directional links SHOULD exist for Energy
Aware Route Replies.
- The node SHOULD send a unicast Route Reply to every Route Request
packet it receives for which it is a target node.
6.2.5. Processing a Received Route Reply Option
This section is the same as that discussed in Section 8.2.4 of the
DSR draft with the following modifications:
- If the node is on the source route specified on the route reply,
it SHOULD check that the computed MRTP that it would transmit at
on the route is achievable. If not it SHOULD bound and/or
quantize the value as specified in Section 3.1.1.
- If the node forwards the Route Reply Option, it SHOULD transmit
the packet at the MRTP listed in the EADSR header.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 18]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
6.3. Route Maintenance Processing
This section is the same as that discussed in Section 8.3 of the DSR
draft. Note that EADSR requires a network-layer acknowledgement of
every packet.
6.3.1. Using Link-Layer Acknowledgements
This section is the same as that discussed in Section 8.3.1 of the
DSR draft.
6.3.2. Using Passive Acknowledgements
This section is the same as that discussed in Section 8.3.2 of the
DSR draft.
6.3.3. Using Network-Layer Acknowledgements
This section is the same as that discussed in Section 8.3.3 of the
DSR draft. With the following modifications:
- Each data packet that is originated by a node, SHOULD request a
network-layer acknowledgement from the next-hop node.
- The network-layer ACK packets SHOULD be transmitted at the
maximum power level supported by the interface.
- If the maximum transmit power supported by node interfaces is not
generally known, then an EADSR option SHOULD be added to the
packet according to the following sequence of steps:
o The node creates an EADSR option as described in Section 5,
and appends it to the DSR Options header.
o A single LEI field is created.
o The first octet of the LEI field is set to the maximum
transmit power of the interface.
6.3.4. Originating a Route Error
This section is the same as that discussed in Section 8.3.4 of the
DSR draft.
6.3.5. Processing a Received Route Error Option
This section is the same as that discussed in Section 8.3.5 of the
DSR draft.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 19]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
6.3.6. Salvaging a Packet
This section is the same as that discussed in Section 8.3.6 of the
DSR draft.
6.3.7 Processing a Received Data packet
Each node along a source route SHOULD check the difference between
the MRTP just computed for the received packet and the MRTP in the
EADSR option for this hop.
If the following equation holds, the Link Flag SHOULD be set and
the minimum transmit power advertised SHOULD be overwritten by
the new estimated value of the minimum transmit power.
|P(tx) - P(cmp)| > M_Delta
where P(tx) is the power the packet was transmitted as listed in the
EADSR option and P(cmp) is the MRTP computed for the received
packet.
If the destination address specified in IP header of the Data
packet matches the node's address,
It SHOULD check the Link Flag in the Source Route option. If the
flag is set, it SHOULD create a gratuitous reply as discussed in
Section 8.1.5 of the DSR draft. If the Link Flag is not set, it
strips the EADSR headers, and sends the packet to the higher
layers for processing.
6.3.8 Promiscuous Mode Operation
If the data packet is overheard due to the "promiscuous" mode,
- The snooping node extracts the source route and the source powers
and saves the same in the Link Cache as described in Section
6.1.4.
- This node estimates the power required to route packets through
itself i.e. it computes the cost of routing packets from the
source node to itself, and from itself to the next node. Let's
consider the case where source node A communicates with
destination node C and node B is an intermediate node that
overhears the data/ack exchange between nodes A & C. Let's
assume that the cost from the node A to node C is given by
P(PrevHop) and from node C to the node B is P(NextHop). Let P(tx)
be the power to transmit between node A and node B. If the
following equation holds
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 20]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
P(PrevHop) + P(NextHop) + Margin < P(tx),
the node creates a gratuitous reply with the new source route
initiator, ..., transmitting node, current node, next hop
node, ..., destination
and the new LEI fields corresponding to this source route.
6.4. Multiple Interface Support
This section is the same as that discussed in Section 8.4 of the DSR
draft with the following modification. The energy cost of links
between interfaces on the same device are zero.
6.5. Fragmentation and Reassembly
This section is the same as that discussed in Section 8.4 of the DSR
draft.
6.6. Flow State Processing
The optional DSR flow state extension is not supported in EADSR.
7. Protocol Constants and Configuration Variables
Any EADSR implementation MUST support all the Protocol Constants as
defined in the DSR draft with the following EADSR modifications:
NetworkLayerAckTimeout 1000 milliseconds
M 6 dB
M_Delta 4 dB
T -85 dBm
The value of the threshold T depends on the wireless interface
sensitivity. We used Cisco 350 Aironet Series wireless ethernet
cards that had a sensitivity of -85 dBm.
8. Security Considerations
This document does not specifically address security concerns.
However, this document assumes that every node participating in the
EADSR protocol function co-operatively without any malicious
intent. In mission-oriented environments where all the nodes
participating in the DSR protocol share a common goal that motivates
their participation in the protocol, the communications between the
nodes can be encrypted at the physical channel or link layer to
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 21]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
prevent attack by outsiders.
Acknowledgements
The protocol described in this draft has been designed and developed
within the Pervasive Communications Laboratory, a research project
at University of Colorado at Boulder that deals with research
problems such as densely interconnected networks, power management,
and communications link. The work was funded by NSF Grant
ANI-0082998
We would like to acknowledge the work carried out by Dave Johnson
et. al. on DSR upon which our work is based.
We would like to thank Jean Tourrilhes, Javier Achirica, and Peter
K. Lee for their help in modifying the device driver for the Cisco
350 Aironet Series card and the Wireless Tools used.
Appendix A. Implementation and Evaluation Status
The initial design of the EADSR protocol, including EADSR's basic
Route Discovery and Route Maintenance mechanisms, was first
published in July 2002 [3] followed by a comparison of DSR and EADSR
in 2003 [4]. The hardware test-bed that was used to carry out the
testing of the protocol is described in [5].
The EADSR protocol has been implemented on laptops running Red Hat
Linux with Cisco 350 Series wireless Ethernet cards. The protocol
has been extensively tested on the NS2 simulator and the hardware
test-bed and the results have been published in [3] and [4]. We are
also working on implementing the EADSR protocol on Compaq iPAQs.
We have implemented the EADSR protocol using the Click Modular
Router on Linux 2.4.18 kernel running on Intel x86 platforms. This
protocol is kernel-independent and requires the Click Modular Router
running on any 2.4.X kernel with a kernel tap running.
We designed and implemented an Emulated Wireless Ad hoc Networking
(EWAN) test-bed [5].
References
[1] David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts.
In Proceedings of the IEEE Workshop on Mobile Computing Systems and
Applications, pages 158--163, December 1994.
[2] David B. Johnson and David A. Maltz. Dynamic Source Routing in
Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 22]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer
Academic Publishers, 1996.
[3] S. Doshi, S. Bhandare, and T. X. Brown, An On-demand Minimum Energy
routing protocol for a wireless ad hoc network, Mobile Computing
and Communications Review, vol. 6, pp. 5066, 2002.
[4] S. Bhandare, S. Doshi, T. X. Brown, and S. Sanghani, Comparison of
two ad hoc wireless routing protocols on a hardware test-bed, IEEE
WCNC, March 2003.
[5] S. Sanghani, T. X. Brown, S. Bhandare, and S. Doshi, EWANT:
Emulated wireless ad hoc network test-bed, IEEE WCNC, March 2003.
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 23]
Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003
Chair's Address
The MANET Working Group can be contacted via its current chairs:
M. Scott Corson Phone: +1 908 947-7033
Flarion Technologies, Inc. Email: corson@flarion.com
Bedminster One
135 Route 202/206 South
Bedminster, NJ 07921
USA
Joseph Macker Phone: +1 202 767-2001
Information Technology Division Email: macker@itd.nrl.navy.mil
Naval Research Laboratory
Washington, DC 20375
USA
Authors' Addresses:
Questions about this document can be directed to the authors:
Timothy X Brown Phone: +1 303 492-1630
Electrical and Computer Engineering Fax: +1 303 492-1112
Interdisciplinary Telecommunications Email: timxb@colorado.edu
University of Colorado
Boulder, CO 80309-0530
USA
Shweta D. Bhandare Phone: +1 303 735-3664
Interdisciplinary Telecommunications Fax: +1 303 492-1112
University of Colorado Email: bhandare@colorado.edu
Boulder, CO 80309-0530
USA
Sheetalkumar R. Doshi Phone: +1 303 492-2759
Electrical and Computer Engineering Fax: +1 303 492-2758
University of Colorado Email: doshi@colorado.edu
Boulder, CO 80309-0425
USA
Brown, Bhandare, Doshi Expires 23 December 2003 [Page 24]
