Abstract
Data generated in wireless sensor networks may not all be alike: some data may be more important than others and hencemay have different delivery requirements. In this paper, we address differentiated data delivery in the presence of congestion inwireless sensor networks. We propose a class of algorithms that enforce differentiated routing based on the congested areas of anetwork and data priority. The basic protocol, called Congestion-Aware Routing (CAR), discovers the congested zone of the networkthat exists between high-priority data sources and the data sink and, using simple forwarding rules, dedicates this portion of thenetwork to forwarding primarily high-priority traffic. Since CAR requires some overhead for establishing the high-priority routing zone,it is unsuitable for highly mobile data sources. To accommodate these, we define MAC-Enhanced CAR (MCAR), which includesMAC-layer enhancements and a protocol for forming high-priority paths on the fly for each burst of data. MCAR effectively handles themobility of high-priority data sources, at the expense of degrading the performance of low-priority traffic. We present extensivesimulation results for CAR and MCAR, and an implementation of MCAR on a 48-node testbed.Index Terms—Wireless sensor networks, routing, congestion, differentiated service.
INTRODUCTION
SENSOR network deployments may include hundreds orthousands of nodes. Since deploying such large-scalenetworks has a high cost, it is increasingly likely thatsensors will be shared by multiple applications and gathervarious types of data: temperature, the presence of lethalchemical gases, audio and/or video feeds, etc. Therefore,data generated in a sensor network may not all be equallyimportant.With large deployment sizes, congestion becomes animportant problem. Congestion may lead to indiscriminatedropping of data (i.e., high-priority (HP) packets may bedropped while low-priority (LP) packets are delivered). Italso results in an increase in energy consumption to routepackets that will be dropped downstream as links becomesaturated. As nodes along optimal routes are depletedof energy, only nonoptimal routes remain, furthercompounding the problem. To ensure that data withhigher priority is received in the presence of congestiondue to LP packets, differentiated service must be provided.In this work, we are interested in congestion that resultsfrom excessive competition for the wireless medium.Existing schemes detect congestion while considering alldata to be equally important. We characterize congestionas the degradation of service to HP data due to competingLP traffic. In this case, congestion detection is reduced toidentifying competition for medium access between HPand LP traffic.Congestion becomes worse when a particular area isgenerating data at a high rate. This mayoccur in deploymentsin which sensors in one area of interest are requested to gatherand transmit data at a higher rate than others (similar tobursty convergecast [25]). In this case, routing dynamics canlead to congestion on specific paths. These paths are usuallyclose to each other, which leads to an entire zone in thenetwork facing congestion. We refer to this zone, essentiallyan extended hotspot, as the congestion zone (conzone).In this paper, we examine data delivery issues inthe presence of congestion. We propose the use of dataprioritization and a differentiated routing protocol and/or aprioritized medium access scheme to mitigate its effects onHP traffic. We strive for a solution that accommodatesboth LP and HP traffic when the network is static or nearstatic and enables fast recovery of LP traffic in networkswith mobile HP data sources. Our solution uses adifferentiated routing approach to effectively separateHP traffic from LP traffic in the sensor network. HP traffichas exclusive use of nodes along its shortest path to thesink, whereas LP traffic is routed over uncongested nodesin the network but may traverse longer paths.Our contributions in this work are listed as follows:. Design of Congestion-Aware Routing (CAR). CARis a network-layer solution to provide differentiated682 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 7, NO. 6, JUNE 2008. R. Kumar, H. Rowaihy, G. Cao, and T.F. La Porta are with the Departmentof Computer Science and Engineering, The Pennsylvania State University,State College, PA 16802.E-mail: {rajukuma, rowaihy, gcao, tlp}[at]cse.psu.edu.. R. Crepaldi is with the Department of Computer Science, University ofIllinois, Urbana-Champaign, IL 61801-2302. E-mail: rcrepal2[at]uiuc.edu.. A.F. Harris III is with the Center for Remote Sensing of Ice Sheets(CReSIS), University of Kansas, Lawrence, KS 66045-7612.E-mail: afh[at]cresis.ku.edu.. M. Zorzi is with Department of Information Engineering, University ofPadova, 35131 Padova, Italy. E-mail: zorzi[at]dei.unipd.it.Manuscript received 6 Aug. 2007; revised 16 Nov. 2007; accepted 10 Jan.2008; published online 28 Jan. 2008.For information on obtaining reprints of this article, please send e-mail to:tmc[at]computer.org, and reference IEEECS Log Number TMC-2007-08-0232.Digital Object Identifier no. 10.1109/TMC.2008.20.1536-1233/08/$25.00 _ 2008 IEEE Published by the IEEE CS, CASS, ComSoc, IES, & SPSservice in congested sensor networks. CAR alsoprevents severe degradation of service to LP data byutilizing uncongested parts of the network.. Design of MAC-Enhanced CAR (MCAR). MCARis primarily a MAC-layer mechanism used inconjunction with routing to provide mobile andlightweight conzones to address sensor networkswith mobile HP data sources and/or burstyHP traffic. Compared to CAR, MCAR has asmaller overhead but degrades the performance ofLP data more aggressively.We compare CAR and MCAR to an AODV schemeenhanced with priority queues (AODVþPQ). Both CAR andMCAR lead to a significant increase in the successful packetdelivery ratio of HP data and a clear decrease in the averagedelivery delay compared to AODVþPQ. CAR and MCARalso provide low jitter. Moreover, they use energy moreuniformly in the deployment and reduce the energyconsumed in the nodes that lie on the conzone, whichleads to an increase in connectivity lifetime. In the presenceof sufficient congestion, CAR also allows an appreciableamount of LP data to be delivered. We further show that, inthe presence of mobile HP data sources, MCAR providesmobile conzones, which follow the HP traffic.We also present the implementation of MCAR on oursensor network testbed. The implementation shows thefeasibility of MAC-layer enhancements and differentiatedrouting on current hardware. We demonstrate that using anactual implementation, HP delivery rates similar to thoseseen in simulation can be achieved in a practical system.The rest of this paper is organized as follows: Section 2presents related work. Details of CAR and MCAR arepresented in Section 3. Simulation details and results arepresented in Section 4. Section 5 discusses our testbedimplementation and results. Finally, Section 6 presentsconclusions and future directions.
RELATED WORK
An obvious solution to enhance service to HP data is to usepriority queues to provide differentiated services (see [4],[15], and [25]). However, in such schemes, thoughHP packets get precedence over LP packets within a node,at the MAC layer, they still compete for a shared channelwith LP traffic sent by surrounding nodes. As a result,without a routing scheme to address the impact ofcongestion and hotspots in the network, local solutions likepriority queuing are not sufficient to provide adequatepriority service to important data.QoS in sensor networks has been the focus of currentresearch (e.g., [4], [8], and [26]). SPEED [8] provides softreal-time guarantees for end-to-end traffic using feedbackcontrol and location awareness. It also concludes that localadaptation at the MAC layer alone is insufficient to addressthe problem of hotspots and that routing is essential to thesolution. Akkaya and Younis [4] propose an energy-awareQoS routing protocol to support the delivery of real-timedata in the presence of interfering non-real-time data byusing multiple queues in each node in a cluster-basednetwork; they do not consider the impact of congestion inthe network and the interference that non-real-time trafficcan cause to real-time data. Zhang et al. [26] propose ageneric model for achieving multiple QoS objectives.Degrading service to one type of data to provide betterservice to another has been used in schemes like RAP [15]and SWAN [3]. Similar to these works, we segregate data;however, instead of real-time delivery demands, we usedata priority as the basis for our segregation.Approaches like 802.11e [1] and other differentiatedMAC schemes that assign higher priority to important data(e.g., VoIP for 802.11e) via MAC-layer mechanisms succeedat providing better service to HP data by assigning thempreferential medium access. Funneling-MAC [2], proposedby Ahn et al., addresses the issue of increased trafficintensity in the proximity of a sink by using a schedulebasedand contention-based MAC hybrid. As with dataaggregation schemes like [16] and [21], it serves to delay theoccurrence of congestion. Back pressure and rate limiting(also used in SPEED [8] and Fusion [10]) are essential toavoid situations where the network capacity is less than theamount of traffic being injected into the medium.Rangwala et al. [20] propose Interference-Aware Fair RateControl (IFRC), which employs schemes to achieve fair andefficient rate limiting. It uses a tree rooted at each sink toroute all data. When congestion occurs, the rates of the flowson the interfering trees are throttled. But, these schemes donot adopt differentiated routing. Also, in a large networkthat is under congestion in a constrained area, our approachleverages the large uncongested parts of the network that isoften underutilized to deliver LP traffic.RAP [15], SPEED [8], and MMSPEED [7] use velocitymonotonicscheduling. Applications assign an expected speedto each data packet, which is then ensured by theseschemes. The speed that the application should assign toa packet if the network is congested is unclear. Theseschemes spread traffic around hotspots, but they do notgive preference to HP data. In fact, if LP data has led to ahotspot in an area, routes for HP data that later enter thenetwork will circumvent this hotspot. This will increase thenumber of hops over which this data has to be routed andincrease the energy consumed in the network. In the worstcase, no path for HP data may be found, and these packetswill be dropped. Additionally, MMSPEED [7] achievesreliability by duplicating packets and routing them overdifferent paths to the destination. Duplication of packets incongested networks may further precipitate congestion.Also, these schemes do not explicitly separate LP andHP traffic generated in the same area.Our schemes are different from these schemes, becausewe use differentiated routing to provide the best possibleservice to HP data while trying to decrease the energyconsumption in the conzone.Congestion in sensor networks has been addressedin works like CODA [22], Fusion [10], and by Ee andBajcsy [6]. Though these schemes take important steps tomitigate congestion in sensor networks, they treat all dataequally. These schemes are complementary to the capabilityprovided by CAR and MCAR. Similarly, our solutions donot preclude the use of priority queues, which can be addedas a simple extension.Existing work on congestion in sensor networks hastwo aspects: detection and mitigation. As mentioned earlier,we do not concern ourselves with congestion detection
download full report
http://googleurl?sa=t&source=web&cd=4&ve...onzone.pdf&ei=LdGSTa_kG4HfceLxxYkH&usg=AFQjCNGCdKDGAJ3ILxvIl9SjlUBllgMDlA&sig2=Sb3S7UfCTRIh0N3hU_cLEA
