EasiTPQ：QoS BasedTopology Control in Wireless Sensor Network
LIU Wei
1Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080
2GraduateUniversity of ChineseAcademy of Sciences, Beijing 100049
CUI Li
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080
LI Tian Pu
I1nstitute of Computing TechnolIogy, Chinese Academy of Sciences, Beijing 100080
2GraduateUniversity of ChineseAcademy of Sciences, Beijing 100049
Abstract
With the rapid development of wireless sensor network, the requirements for quality of service are growing,particularly in applications where real time imaging, video or audio communications are involved. The system needs to meet optimized energy consumption design criterion and to satisfy certainQoS requirements at the same time from long view. Most of the existing works deal withresource allocation (e.g., scheduling or buffering) orrouting strategyto achieve QoS. In this paper, we propose to extend QoS support to the topology control layerby introducinga number of active nodes distributed in a gradient fashion based on their logical distances to the sink node.Presenta novel topology controlalgorithm,namelyEasiTPQ (Easy QoS based topology control)for QoS improvement in wireless sensor networks. Simulation results show that data loss rate and latency are averagelyimproved by 60% and 55%,respectively.
Key words:gradientchange density; QoS; state transmission
1. Introduction
A wireless sensor network is composed of a large number of tiny and inexpensive sensor nodes which can compute and communicate by wireless [1]. Sensor nodes can be deployeddensely on a large scaleandare hard to be re-collected and recharged. Thus the level of energy consumption is an important design criterion for sensor networks, since it is directly related to the network lifetime.Topology control and management is an effective way to control the power level of the network. Herehow sensor nodes cooperate with each other tocreate an efficient and connected network to upper layer is the major problem in topology control process.
Although most of the applications are dealing withsmall data flow obeying the principle of best effort, the high-speed data flow, however, have to besustained from long view.This trend looks more apparent with the introduction of hybrid sensor networks [2].In this work, research was focused on a QoS-based topology control algorithm which can reduce packet loss rate and latency in networks wheresome sensor nodes generate high-speed data to sink simultaneously. Energy saving scheme was also designed. Nodes which have littlecontribution toQoS guaranteewere scheduled to sleep to prolong the life time of the network.
The rest of this paper is organized as follows: Section II summarizes the related works. Section III describes our QoS-based topology control algorithm and analyzessome crucial parameter selections from simulation. Finally, Section IV concludes the paper.
2. RelatedWorks
In topology control, both powering off redundant nodes and lowering radio power while keeping the network connected can contribute to power-saving. However, powering off unnecessary nodes can achieve better results[3-5].
Since sensor nodeshave limitedcapability of computing and limited memory space to storage data, the QoS solutionfor sensor networks can not simply follow those for broad-band networks. Moreover, sensor network is highly oriented to applications,sothata “fits-all” QoSsolution is unlikely existing.
Sequential Assignment Routing (SAR) [6] is the first protocolfor sensor networks that includes a notion of QoS. Assumingmultiple paths to the sink node, each sensor uses a SARalgorithm for path selection. It takes into account the energyand QoS factors on each path.
SPEED [7] is similar toSAR.The protocolrequires each node to maintain itsneighbor’sinformation.In addition, SPEED strives to ensure a certain speed for eachpacket delivery so that each application can estimate the end-to-end delay for the packets by considering the distance to thesink and the speed of the packet delivery before making theadmission decision.
For real-time traffic generated by imagingor video sensors,the protocol presented in [8] finds a least costand energy efficient path that meets certain end-to-end delayrequirement.
More recently, hybrid sensor networkattracts more attention. A three-tiredarchitecture presented in[2] are composed of normal data collection nodes, data relay nodes and data relay gateway. A path composed of high capacity and little latency nodes can be selected
3. QoS-Based Topology Control (EasiTPQ)
3.1.The Feasibility and necessityof EasiTPQ
Existing research on QoS problem in wireless sensor network is focused on how to find a proper data pathin pre-existing network topologyon the hypothesis that this path exists. Actually path satisfying all the QoSrequirements does not always exist， especially topology control scheme is adopted.
Byanalyzing the architecture of WSN, we conclude that each node in network has different functionalities in transmitting data. The data transmission mode is usuallyin a multi-to-one fashion where more relay data flowsaretransmitted by nodescloser to the sink. Hence for thoseinterior nodes, the tasks of transmitting data may be quite heavy with morerelay data thanlocal generated data. Meanwhile the exterior nodes transmit local collected data mostly.The most exterior nodes have only got local collected datato transmit.
3.2.Gradient Topology Structure
3.2.1 EasiTPQ Design
Based on the above analysis, the proposed QoS-based topology control algorithm, namely EasiTPQ, is designed by reducing exterior redundant nodes andincreasing interior active nodes simultaneously to create a gradient topology structure aiming to meetQoS requirements, e.g. the data loss rate and latency.Fig.1illustrates the nodes category created by our EasiTPQ algorithm.
Fig.1 Architecture of EasiTPQ
There are three types of nodes in EasiTPQ: (a) NA (Not Active) nodes which are nodes in sleep mode, (b) CA (Connectivity Active) nodes which are scheduled to work for network connection and (c) QA (QoS Active) nodes which are scheduled to work for extra sustain to meet for QoS requirements. The main design criterionof EasiTPQ is to add QA nodes as few as possible to satisfy certain QoS requirements.
Threedefinitionsare introduced as below:
Definition 1: Node’s active power value AP:
APdenotes the value or capacity to become an active node.
（1）
Whereeis node’s remaining power, and Eis node’s initial power.（Neighbor Total）is the number ofnode’s neighbor it can communicatewhilesin non-sleep state. reflects the importance of node in the network and can be used to differentiate crucial nodes from other normal ones. and are the weightvaluebetween this two parameters,and can be flexibly configured according specific application.
Definition 2: The sorting function
The functionisthe value order of local node’s among allvalues it can hear.
(2)
is the value of local node, and is other node’s value this local node can hearat its R_Test stage. So definition 2 reflects a sorting relation between local nodes and its neighbors.
Definition 3: Gradient descending function
istherelation between node’s active neighbor number andits hop count to sink.
（3-1）
（3-2）
In this paper, we focus our attention mainly on two types of function, including alinerdescending function and a square root descending function described in formula (3-1) and (3-2) respectively. The reasonof selecting these two types of function is thatthese two simple functions can be used as examples toevaluate the effect of node’s gradient distribution schemes to the overall QoSperformance of the network. Mis the initial number of neighbors and is often set bythe value of the diameter of network.i is the hop count between each node to the sink node and the initial value is set to 1. Thusrepresents the active neighbor number of local node which have a hop count i to sink node.
3.2.2EasiTPQ implementation
In EasiTPQ, nodes are in one of the four states: R_Test, R_Passive, R_Active and R_Sleep. Fig.2shows a state transition diagram.
Fig.2Diagram of EasiTPQ state transitions
(1) Initially, only sink node is in the active state and other nodes are in R_Passive state with their radio on to overhear all packets transmitted by their active neighbors. No data packets are forwarded in this state since this is a listen-only state.
(2) Sink node sends Topo_Initial command by broadcasting which informs nodes in network to enter the process of EasiTPQalgorithm.
(3) Nodes received Topo_Initial command entersR_Test state from R_Passive state, and start to exchange data and routing control messages.
(4) Nodes in R_Test state start to broadcast message including value and, at the same time, to set up a timer Tt. When Tt expires, the node enters the R_Active state. Before Tt expires, if the node findsthat the average data loss rate is higher than the average loss before entering in the R_Test state, then the node moves into the R_Passivestate. is the active neighbor count need to be decidedwith a minimal value of. is set in view of the basic network connectivity target [9]. From above information we know that is a crucial parameter in EasiTPQand thisvalue has a gradient property which changes according to hop count fromthis nodetothe sink. is the average data loss before entering in R_Test state, which is the influence of data loss rate when this node enter the data transmissionprocess.
(5) Nodes in R_Passive state set up a timer Tp. When Tpexpires, the node enters the R_Sleep state. Before Tpexpires, if the number of neighbors is below or the data loss rate higher than, the node makes a transition to the R_Test state to transmit data.denotes the minimal data loss rate application required, which is a parameter related to the QoS property.
(6) Nodes in R_Active state transfer to R_Test state after a period of time Ta to detect whether it should become an inactive node. This detection process may balance the power consumption among nodes, and may avoid the crucial nodes consume all its power to make other nodes logically broken down (e.g. could not transmit data continually). A node which enters the R_Sleep state turns the radio off, sets a timer Ts, and goes to sleep. When Ts expires, the node moves into R_Passive state.
After all above procedures, the active nodes form a network architecture consisting of three types of nodes. The neighbor numberensures the basic network connectivity [9], while other active nodes or QA nodes ensure some QoS performancein network.
3.3.Performance evaluation and parameter analysis
In the simulation part, we use NS2 simulation tools and choose parameters as below: ，,，Tp=2min，Ts=2min，Tt=4min，Ta=4min，=2, and node number is 120.Network performances were examined according to different schemes as shown in (3-1) and (3-2), respectively.
The simulation results of data loss rate and data latency are shown in Fig.3. PL1 and LA1is the initial network data loss rate and data latency whose topology is obtained by ASCENT [9]. PL2 andLA2 is the network data loss rate and data latency whose topology is obtained by EasiTPQ using formula (3-1) (in a liner descending scheme). And PL3 andLA3is the network data loss rate and data latency whose topology is obtained by EasiTPQ using formula (3-2) (in a square root descending scheme).
Fig.3Packet loss rate and Latency
From Fig.3, we can see that
(a)The performance in PL2 is improved by 50%
Averagelythan that of PL1, which can verify the efficiency of addingQA nodes?
(b) The performance of PL3 decrease fast when data rate exceed certainvalue. This may because those more extra active QA nodes in exterior circle may cause more channel competition. When data rate exceeds some threshold, the negativeeffect of channel competition will suppress the QoS contribution by these extra active QA nodes.
(c) PL3 has an improvement by 70% in the data raterange of 0-20Kbps.Many real time imaging and audio communications are in this range. Other applicationswith higher data rate than the threshold may choose PL2 scheme for better QoS performance.
(d) The latency from node to sink of LA3is always less than that of LA1 with an improvement by 40%in average.This may because those packages successfully transmitted have more easy access to MAC channel, so less channel access latency can be acquired.
(e) LA2 has a very good latency performance. The latency of LA2 is less than that of LA1 with an improvement by averagely 70%in the data rate range of 0-20Kbps. This may because that LA2 scheme both have a less channel access latency and have less extra hop latency compare to LA3 scheme in that data raterange. But when the data rate exceeds some threshold the MAC latency might be apparent compared to other factors which are the same as LA1, if considering the extra hop latency the larger latency may occur.
4. Conclusions
The EasiTPQ algorithm proposed in this paper is a QoS based topology control algorithm. EasiTPQ makes use of the fact that each node in network has different functionalities in data transmission, e.g., some nodes bear more data relay tasks whilst some other nodes only transmits data generated by itself. EasiTPQ schedule more nodes active if these nodes are responsible more to “relay” data tasks. Simulation results show that EasiTPQenablesimproved data loss rate and delay performanceby 60% and 55% respectivelycompared withanother existing topology control algorithmsuch as ASCENT. EasiTPQ is more useful if the data rate range is withina certainrange.The QoS problem is highly oriented to application in wireless sensor network.Further experimental or simulation works need to be carried out to study the concrete parameter settings for particular applications.
References
[1] 崔莉,鞠海玲,苗勇,李天璞,刘巍.无线传感器网络研究进展.计算机研究与发展,2005,42(1):163-174
[2] O.Kasten. Energyconsumption. ETH-Zurich, Swiss Federal Institute of Technology. Available at 2001.
[3] Zafer Sahinoglu and Philip Orlik“transmit poweradjustment,” in Proc. IEEE INFOCOM, 2000, pp.404–413. [Online]. Available: citeseer.nj.nec.com/ramanathan00topology.html
[4] G.C˘alinescu, I.M˘andoiu, and A.Zelikovsky, “Symmetric connectivity with minimum power consumption in radio networks,” in 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002). Kluwer Academic Publishers, 2002, pp. 119–130.
[5] M.Stemm and R.H.Katz. Measuring and reducing energy consumption of network interfaces in hand-held devices. IEICE Transactions on Communications, E80-B(8):1125–1131, Aug. 1997.
[6] B.Chen, K.Jamieson, H.Balakrishnan, and R.Morris. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. ACM Wireless Networks, 8(5), September 2002.
[7] C. Schurgers, V. Tsiatsis, and M.Srivastava.STEM: Topology management for energy efficientsensor networks. In IEEE Aerospace Conference,pages 78–89, March, 2002.
[8] K. Sohrabi, J. Gao, V. Ailawadhi and G. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network, ” IEEE Personal Communications, pp. 16-27, October 2000.
[9] A.Cerpa andD.Estrin. ASCENT: Adaptive selfconfiguring sensor network topologies. In Twenty First International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), June 2002