Absfruct-We present the Pulse protocol which is designed for multi-hop wireless infrastructure access. While similar to the more traditional access point model, it is extended to operate across multiple hops. This is particularly useful f i x conference, airport, or large corporate deployments. In these types ofenvironmen& where users are highly mobile, euerpy efficiency hecomes of great importance. The Pulse protocol utilizes a peridic Rood initiated at the network gateways which provides both muting and synchmnization lo the network. This synchronization i s used to allow idle nodes to power off their radios for B large percentage of the time when they are not needed for packet forwarding. Tlus results in suhstantial energy savings. Through simulation we validate the performance of the routing protocol with respect to both packet delivery and energy savings. Wireless networking today is predominantly used to provide mobile users with untethered access to fixed infrastructure. This allows users to move freely throughout the office nr warehouse while remaining continuously connected with the office network and the Internet. In these types of environments a majority of the traffic is moving between the mobile nodes and the fixed infrastructure, as opposed to between the mobile nodes themselves such as in ad hoc networks. While traditional access point devices currently provide this capability. they have a limited coverage range and thus many access points are required to provide coverage of a given area. One solution to this problem is to use a routing protocol that allows the users to traverse multiple hops to the nearest access point. This greatly expands the coverage range of each access point while simultaneously reducing costs and simplifying deployment. Although a number ofrouting protocols have been proposed by the wireless networking community. they have been primarily designed for peer-to-peer ad hoc networks and not specifically optimized for fixed infrastructure access. Multi-hop tixed infrastructure access networks typically contain up to a large number of mobile users with no readily available power resources. While these networks may contain a large number of users. generally only a small subset of them would be communicating at one time. This necessitates a protocol that scales to high node densities. handles topological changes due to mobility, and is highly energy efficient. Several methods have been proposed for energy conservation. For example, the 802.1 1 standard provides power saving functionality, but it only operates in a single hop environment. A number of power saving protocols have been designed for ad hoc networks. but none of them have focused specifically on this type of infrastructure access application. Since this infrastructure access model is a more specific case of the general ad hoc model, it may be possible to design a protocol that extracts additional performance and power saving. Our Cunrribririon. We present the Pulse protocol that utilizes a periodic flood. which we refer to as a pulse, initiated at the network gateways to provide both routing and synchronization to the network. This periodic pulse forms a spanning tree rooted at the network gateways. By tracking its current parent in the tree. each node has a continuously updated route towards the nearest network gateway. This allows nodes to maintain connectivity with fixed infrastructure across multiple wireless hops; thereby increasing the coverage area of a traditional access point based system. Nodes are able to synchronize with the pulse. which allows idle nodes to power off their radios a majority of the time. except when they are required for packet forwarding. This result$ in substantial energy savings. Through simulation we validate the performance of the routing protocol with respect to both packet delivery and energy savings. This paper is organized as follows: In Section II we present our infrastructure access model and power model. We discuss existing strategies for power conservation in Section 111. In Section IV we describe in detail the Pulse protocol and provide simulations in Section V. PROBLEM DEFiNITlON AND MODEL While the utility of wireless networks extends to a wide range of applications. we would like to consider specifically the application of multi-hop infrastructure access. Currently, a ma.jority of wireless network deployments involve the use of access points which utilize the IEEE 802.11 Point Coordination Function (PCF) to control access to the wireless medium through centralized coordination. These access points provide access to fixed infrastructure to all nodes within a single hop. Multi-hop operation is not currently specified as part of the IEEE standard. This limitation complicates wireless network deployment by requiring every access point to be wired into the fixed infrastructure and requiring a large number of access points to provide adequate coverage of a given area. By extending the limited access point model to a multi-hop  In order to analyze the power eificiency of routing protocols. it is imponaut to tirst understand exactly how power is consumed by wireless interfaces. In this work we will spccitically be referring to SO2.I I wirelcss adapters. The wireless interface is capable of being in four possible operational states. each of which consumes power at a spccilic rate. The least power consuming state is the slerp sfutr. While in the sleep state the wireless card itsclfis still consuming a smull amount of power. hut the radio (which typically consumes the most power) is turned off. While in this state. the card is unable to send or receive packets and has no knowledge of activities taking place on the medium. Since only the radio is powered off, the card can switch the radio off and on quickly. If the card is completely powered off (not just the radio) the reactivation time is much longer. The wireless card can also be in an i d r sfute. meaning its radio is powered on. hut it is not currently sending or receiving data. On-demand routing protocols typically spend a great deal of time in this slate. since they need to be continuously ready io receive route requests. While in the idle state the card is continuously monitoring the medium sensing for a carrier signal which would cause it to enter the receiving state. The card is in the transniit or receive state when it is actively sending or receiving. According to the power consumption measurements for commonly available 802.11b cards [2] (Table I)_ the power consumption in the sending or receiving state is not much more than the power consumption in the idle stale_ while the sleep state consumes significantly less power. The idle swte consumes only 36% less power than continuously transmitting, The sleep state however consumes 9% less power then continuously transmitting, As a result. in order to achieve maximum power savings a protocol must utilize the sleep state as frequently as possible. There has been a great deal of research conducted with regard to energy efficiency in wireless ad hoc networks as well as in sensor networks where it could be considered even more important due to more limited resources. In general. this work seems to fall into two main categories. The first technique attempts to control the amount of power used to transmit a packet such that only the power required to get the packet to a specific destination is used. The second category involves the design of distributed protocols which allow the nodes of the network to be placed in a sleep mode. The sleep mode category is further divided into three types of approaches: connected active subset. asynchronous wake up. and synchronous wake up. Each of these suategies has advantages and disadvantages when applied to the stated infrastructure access and power model. Topology control protocols and least energy path routing [5] both attempt to provide energy savings by controlling transmission power, The fundamental concept that drives these protocols is that long range transmissions require greater power than short range transmissions. As a result. sending a packet using several shon rang< hops can consume less total transmission power than sending the packet directly to the destination. The main disadvantage of power control protocols is that transmission power consumption usually represents a small fraction of total consumed system power in typical 502.1 1 radios. This is due to both the high idle energy consumption. and the low transmission duty cycle ot' a typical node in multi-hop shared medium wireless networks. In these networks nodes must take turns transmitting, so any particular node will only have the opportunity to transmit a fraction of the time. As a result power control strategies are fundamentally limited to reducing the overall power consumption by a fraction of 36%. This type of power saving suategy is much more useful when using much higher power radios where transmission power begins to dominate the total power consumption. and in CDMA systems where the transmission duty cycle is much higher. The intuition behind a connected active subset protocol. such as SPAN [6] or CAF [7]_ is that when there Me many nodes close together in a multi-hop wireless network. only a subset of these nodes need to be active in order to maintain One main disadvantage of the active subset strategy is that it i.s inherently dependent on node density for energy savings (SI. The basic premise is that there are enough nodes that only a small number of them are needed at any one time. In low density networks. almost no power can be saved using this strategy because almost every node must stay active. Another main disadvantage of this strategy is the overhead required to maintain an effective subset. Since nodes are mobile. the subset must be continually updated in order to provide complete coverage. Even if nodes were not mobile. the subset must bc rotated in order to avoid completely draining lhe resources of a few nodes. Since coordination is required every time the subset changes. this can cause significant amounts of communication traffic which both limits scalability and reduces good-put by cutting into available medium time. The idea behind the asynchronous wake-up strategy [9] is that by using a carefully designed wake-up schedule, every node in the network should be able to sleep for some fraction of the time. Furthermore, due to the schedule-the node will be guaranteed to be awake at the same time as any particular neighboring node in the network within a bounded amount of time, without requiring any type of network clock synchronization. The main advantage ofthis strategy is that little coordination is required between nodes. Also since every node uses the same wake-up schedule. the network is inherently balanced in terms of equal power use hy differenr nodes. In addition. the energy savings are independent of node density allowing efficient operation in low density networks. However. while the asynchronous strategy has low protocol overhead and good energy efficiency. these come at the price of reduced communication quality and capabilities. The asynchronous strategy only guarantees that any two nodes will k on at the same time wilhin a hounded time period; that guarantee does not hold for any number of nodes beyond two. In other words, all the nodes a packet must traverse along a path will not all he on at the same time, so the packet may be delayed by up to the bounded time for every hop it traverses. Similarly all of a nodes neighbors will not be on at the same time. thus traditional broadcast is also impossible. Instead "broadcast" messages must be individually unicasl to each neighbor. Since the vast majority of wireless routing protocols depend on broadcast for efficient operation, this is a major drawback of the asynchronous strategy and greatly decreases its real world practicality. In addition, the asynchronous wakeup protocol makes heavy use of beacon packets (several per second) in order to detect when neighbors are awake. Since every node must send these beacons. the scalability of this strategy can be compromised in high density networks. Synchronized wake-up approaches operate by obtaining and maintaining network wide clock synchronization and allowing decisions in the network to be made at specific time intervals. This type of approach is able to save the greatest amount of power. especially in idle networks, since all of the nodes in the network can turn off their radios for extended periods of time. This is able to occur regardless of network properlies such as density. The other major advantage of this type of approach is that since nodes are always active at the same time: network broadcasts are still possible. This allows traditional ad hoc routing protocols to function. which depend on broadcast for efficiency. Most power saving protocols typically do not take this approach due to the difficulty in establishing network-wide synchronization. The most well known synchronized power saving strategy is the SO2.1 I Power Save Mode (PSM). This protocol only works within a single hop-making it not applicable to the model we are considering. Zheng et. al. [IO] provide a protocol which extends the 802.11 PSM to operate across multiple hops. Their strategy provides path activation. minimizing per packet delay. However their synchronization strategy requires MAC layer implementation in order to achieve the sub-millisecond accuracy required by the SO2.11 PSM, and does not handle the case of partitions and merges which can occur in an ad hoc environment. The Pulse protocol is also a synchronized wake-up approach. Therefore it allows broadcast and allows all the nodes in the network to power off their radios when the network is idle. Our protocol also uses path activation to eliminate per hop delay. but differers from the existing synchronized protocols in that the time scale is much larger. and that a proactive routing service is provided simultaneously to the power saving functionality. The larger time scale ofthe Pulse protocol allows it to operate with much courser time synchronization (on the order of 10 milliseconds) which can he implemented without MAC layer integration. The protocol design is centered around a flood we refer to as a pulse. which is periodically sent at a fixed pulse infervol. This pulse flood originates from infrastructure access nodes (pulse sources) and propagates through the entire ad hoc component of the network. This rhythmic pulse serves two functions simultaneously. It serves as the primary routing 0-7603-6355-9/04/$20.@l82004 XEPB. mechanism by periodically updating each node in the networks route to the nearest pulse source. Each node tracks the best route to the pulse source by remembering only the node from which it received a flood packei with the lowest metric. The propagation of the flood forms a loop free routing tree rooted at the pulse source. In addition. it is used to provide networkwide time synchronization. If a node needs to send and receive packets, it responds to the flood with a reservation packet. This reservation packet is sent up the tree to the pulse source. The reservation packet contains the address of the node making the reservation. and is used to setup reverse routes at all nodes on the path between the pulse snurce and the sending node. This reservation mechanism operates similarly to the route response mechanism used in AODV [I I]. Note that it is unnecessary for a node to send a reservation packet in response to the Hood? unless it has packets to transfer. A node that is actively communicating must send a reservation packet for every pulse it receives to keep the reverse route fresh. When a nude has not sent or received packets for at least a complete pulse interval. it no longer sends a reservation packet in response to the pulse. The Pulse protocol uses the time synchronization provided by the flood to create a fixed period of time during which all nodes in the network are active. During this prrlse period. the pulse tlood propagates. and nodes can reply with reservation packets. Since a node that does not send or forward a reservation packet will have no packet forwarding responsibilities until the next pulse occurs. it may place its radio in sleep mode until the next pulse period begins. This node deactivation is what allows the Pulse protocol to conserve power. The ratio between the pulse period and the pulse interval determines the duty cycle of the protocol. This duty cycle is the primary factor that determines the idle power consumption of every node in the network. Therefore, reducing the pulse period results in increased energy efficiency. However, the pulse period must he long enough so that the pulse flood and reservation packets can be delivered. In order to minimize this time. data traffic is halted. eliminating contention between data packets and the flood. The periodic pulse flood exploits the communication concentration at the pulse source by providing every node in the network with a continuously updated route. Infrequently, nodes in the network may need to establish peer to peer connections, which are relayed through the pulse source. This results in all of the routes in the network leading to the pulse source and eliminates the need for any additional routing overhead. One unique quality of the Pulse protocol is its inherent scalability according to many metrics. The protocol scales to large networks with regard to coverage area by allowing the simultaneous operation of multiple pulse sources. Additionally. the multi-hop nature of the protocol allows each pulse source to cover a much greater area then the traditional access point model. Also. since all other routing traffic aside from the periodic pulse is unicast. the route acquisition process creates only local traffic on the network. In contrast. traditional ondemand protocols must flood and re-flood the network for each active connection in order to establish and maintain routes. Scalability to high levels .of mobility is provided by the proactive pulse flood. As the mohility level increases. many route failures hegin to occur throughout the network. In the Pulse protocol, all broken routes are repaired simultaneously within one pulse interval using one flood and one unicast for every active node. In contrast, an on-demand protocol may The effectiveness of this technique is best seen through our simulation results in Section V. The Pulse protocol continuously cycles through four distinct phases. Fig 2 indicates these phases and visually depicts the duty cycle of the two second pulse interval used in the simulation section. Nodes must power on before the anticipated pulse arrival time to ensure that it is not missed due to a synchronization error. this period is labelled as Early Power O n in the diagram. An initial upper bound on this period would be a full network diameter. which we define as the amount of time for a flooded packet from the pulse source to reach every node in the network. since every node in the network would be synchronized wilh at least that precision. A more accurate mechanism. described below. allows this time to be significantly smaller in practice. The next phase is referred tn as Forward Pirlse Flood. During this time interval the pulse is flooded to all nodes in the network. This requires a full network diameter to reach all of the nodes. The protocol then enters the Foruard Resenorions which allows enough time for any reservation packets to he forwarded back to the pulse source. This period of time has to be long enough such that the last node in the network that receives the pulse flood is able to return a reservation packet to the source before the nodes in the network enter the next phase. Again. this requires a Nodes which have been reserved remain on and take part in actively transferring data during this period of time. The pulse flood originates at the pulse source, and is sent at a iixed time interval. Several parameters are used to tune the flood for fast propagation. high node coveraee. and good path selection. The flood provides both routing and synchronization, so it must be tuned to serve both needs simultaneously. A pulse packet contains only a few fields: a sequence number, a cost metric used for route selection. and an accumulaied delay timer used to increase the time synchronization accuracy. This keeps the size of the packet to a minimum: increasing the number that can be transmitted in a small amount of time. Two timing parameters govern the flood propagation: jitter and delay. Upon receiving the first pulse packet. a node sets a timer for retransmission of the pulse packet. A uniform random number between delay and delay + jitter is selected for this timer. When the timer expires, the pulse packet is retransmitted with an incremented cost field. and the reumsmission delay added to the accumulated delay tield. The random retransmission jitter is a well known technique used by many flooding protocols to help prevent collisions between nodes that received the same broadcast. The fixed delay is a mechanism used by the pulse protocol to enhance the initial accuracy of the routing metric. Adding a fixed delay dramatically increases the chance that the first pulse packet heard will have the lowest cost metric. This is a desirable feature for the pulse protocol. because a node must reserve a route almost immediately upon hearing the pulse flood in order to meet the tight timing requirements needed for low power operation. A node is committed to a path once it is reserved. even if knowledge of a better path becomes available. The fixed delay maximizes the chance that the best path will he known before the path is reserved. As an optimization. fixed delay is not used by nodes within two hops ofthe pulse source_ since these nodes always hear the best path first.  1471 Nodes in the network must acquire and maintain accurate synchronization with the pulse source in order to function effectively. Acquisition is accomplished by remaining in a listening state until a pulse flood is received. Each flood packet contains a relative time offset which represents the amount of time elapsed since the pulse flood was initiated. Using the received time, the offset. and its own local oscillator. a node can predict when the next pulse flood will be sent by the source. Since the offset in the flood packet does not include all sources of delay the Hood packet may have experienced (such ils MAC contention delay). and since the local oscillator is not perfect. the time sync is only partially accurate. In order to compensate for this. each node keeps track of the earliest pulse stan time received over all recently received pulses. In addition. every node wakes up a sync interval early in order to avoid missing the pulse Hood due to an imperfect sync. In the event that a node misses the pulse Hood, it will remain in a listening state until it can re-acquire synchronization on the next Hood. Reservation packets serve two purposes. They activate intermediate nodes so that they remain awake in order to forward the data packets and they create reverse route entries to the set of active nodes. When a node in the network receives a pulse update packet and has data to transfer. it creates a reservation packet and forwards it-immediately (once it has committed on a~route) up the tree to the pulse source. A reservation packet contains a list of node IDS. initialized to the ID of the node which created the resewation and a cost field initialized to the node's distancc from the pulse source. Whcn an intirrnediate node forwards a reservation packet it creates reverse routes to the nodes indicated by the list of IDS. sets the cost field equal to its own distance to the pulse source. and appends its node ID if it has not already forwarded or sent a reservation. After all of the reservation packets have been received by the pulse source. it has reverse routes to all-of the active noaes in the network. All other nodes in the network that do not send or forward reservation packets turn their radios off at .the end of the pulse period. Nodes that are sending data for long periods of time need to resend a reservation 'packet in response to every pulse Hood. This is required since the topology could be continuously changing. Since every time the pulse update is flooded through the network a new tree could be formed. nodes with active connections need to repeatedly send a reservation packet in response to each pulse. so that the current nodes that form its path remain on. Nodes that are not in the process of transferring data do not have to ever initiate a~reservation packet. The Pulse protocol requires a mechanism which allows it to overhear reservation packets sent by neighboring nodes.
This protocol could suffer from flood overlap delays and can result in significant consumption of energy REF .
The pulse protocol: energy efficient infrastructure access
IEEE INFOCOM 2004
IEEE INFOCOM 2004
Computer Science