An Energy Efficient MAC Protocol For Data Collection With Dynamic Traffic Pattern In Wireless Sensor Network

An Energy Efficient MAC Protocol For Data Collection With Dynamic Traffic Pattern In Wireless Sensor Network

1 Ms. Pushpa .S, 2 Mrs. Mangayarkarasi .P

1 Mtech Student, Computer networks, The Oxford College of Engineering, Bangalore, Karnataka, India

2 Assistant Professor, Department of Information Science , The Oxford College of Engineering, Bangalore, Karnataka, India

Abstract

Data collection is one of the significant applications in wireless sensor network. For data collection MAC layer protocol are used in wireless sensor nodes, where S-Mac protocol is efficient regarding energy and latency. This paper considers S-MAC protocol with continuous sensor data collection. In static network traffic pattern fixed set of nodes report data to the base station, but for continuous sensor data collection traffic dynamically changes and most energy consumed. To avoid energy cost and latency overhead a novel S-MAC protocol based algorithm is proposed called traffic pattern oblivious algorithm, which collects data for dynamic traffic pattern. This paper analyzes performance of Time and energy efficiency. The results show that proposed algorithm significantly improves time and energy efficiency.

Key words: S-Mac, Wireless sensor nodes, scheduling, energy efficiency, latency.

1. Introduction

   In wireless sensor network, data collection is one of the important tasks. Data collection is the gathering of data from the network without any aggregation. Many of the resources are limited in wireless sensor network such as sensing capability, signal processing, communication capability and limited battery energy. It is very hard to replace or charge the battery, so it is better to increase the life of the battery. The challenging task here is energy management. In wireless sensor node, data collection using MAC-(medium access control) protocol is efficient. In MAC protocol most of the energy is wasted due to (i) collision when two nodes transmit at the same time. (ii) Over hearing packet received from the node which is not destined to it. (iii) Idle listening node will be

   waiting for either sending or receiving data. These problems can be easily solved by using MAC techniques. To collect data efficiently in wireless sensor nodes TDMA the Mac protocol is well suitable.

   TDMA is a contention based protocol which avoids collision by scheduling only non-interfering transmissions to proceed in the same time slot. TDMA requires global topology information, rate at which packets generated by each node, to allocate time slot for sending data. During data collection when every node sends data at the same time it leads to lower throughput higher latencies and higher energy consumption. It results in consumption of more battery power, if the network is lightly loaded which leads to idle-listening. Hence TDMA is better for data collection. TDMA based scheduling algorithm is open to all types of data deliver. Most of the existing TDMA algorithm are only for static traffic pattern where fixed set of nodes report data to the base station. But data may change dynamically based on nature of monitoring and energy conservation concern also. The main applications of Wireless sensor nodes in scenarios such as military target tracking and surveillance [2,3], natural disaster relief [10], biomedical health monitoring [5-7], and hazardous environment exploration and seismic sensing [7]. Intrusion detection and identification of WSN are used in military target tracking and Surveillance, with natural disasters; sensor nodes can sense and detect the atmosphere to forecast. The main purpose of the data collection in wireless sensor network (WSNs) is to obtain valuable information from the operating environment.

   S-MAC(Sensor medium access control) works in localized synchronization and based on this synchronization periodic listen and sleep is scheduled. Periodically synchronization packet is

   broadcasted to its immediate sensor nodes. Each receiver node has listen period which is further divided for synchronization, request to send and carrier sense as shown in fig (1) carrier sense will avoid collision. Long messages are divided in to frames and sent in single burst by this technique energy can be saved. Latency avoided by adaptive listen method. Hence it reduce periodic delay.

   Figure 1 S-MAC messaging scenario

   This paper proposes the novel TDMA scheduling algorithm which mainly focus on data collections of any traffic pattern type, by achieving high energy efficiency and time efficiency. An salient feature of this algorithm is that it allows every node to transmit data in its successive transmission slot irrespective of traffic pattern. The rest of this paper is organized as follows. The different types of data collection in wireless sensor networks are reviewed in Section II. In Section III, we define the scope of our problem and highlight our approach. In Section IV, we present the approaches, which progressively reduce latency by using less transmission slots length. It also focuses on energy efficiency utilization. Finally, we conclude this paper in Section V.

2. Related work

   The distributed minimal time convergecast scheduling algorithm [2] mainly focus on data collection in network, where the routing tree aggregates all the data before forwarding to upstream. In this algorithm the child node is scheduled before the internal nodes are scheduled, Hence most of the times the upstream nodes will be ideal. This above schedule doesnt work for non-aggregate data collection. Another one link scheduling scheme [4] designed for non-aggregate data collection, but it needs more transmission slots which work only for static traffic pattern, where each node generates a fixed amount of data to the base station. The Dynamic Conflict-free Query Scheduling [3] works for queries in wireless sensor networks supporting in-network aggregation with dynamic traffic pattern but it works only for non-continuous data collection.

   Capacity of data collection [10], focuses on deriving bounds based on capacity of data collection for arbitrary networks, where sensor

   nodes can be deployed all over network and which can form dynamic network topology. In this technique BFS tree is used for node deployment up and which has achieved higher capacity.

   TDMA-ASAP Sensor Network implements TDMA Scheduling with Adaptive Slot-stealing and Parallelism [14], which conserves energy during low load, appropriate sleeping between transmissions and intelligent scheduling transmissions. Distributed Cross-Layer Scheduling for In-Network Sensor Query Processing [13] which proposes a power efficient scheme, each node employs its MAC, routing, and an scheduling algorithm is constructed for querying, while making layering for query it will negotiate transmission time. Again it will follow the same scheduling algorithm for computing, to know the position of neighbor nodes and sleep time of each node while processing cycle of query.

   Contour mapping [15] technique proposes an energy efficient protocol called Iso-map protocol. This protocol considers a novel algorithm which constructs isoline nodes. Within the isoline nodes network, traffic pattern is restrained which reduces traffic in the network and also over head per node. This protocol has set of rules to select nodes and efficiently extracts node information from contour map.

   Distributed Edge Coloring Revisited technique in sensor networks [5] presents a distributed edge based on coloring link scheduling algorithm. The algorithm works in two phases. First is coloring edges of the network in a distributd fashion. In the second phase every node and incident are colored and associated with plus or minus sign, Which states that collision free transmission will takes place along edges. Hence hidden terminal and the exposed terminal problems are avoided.

   Time optimum packet scheduling algorithm

   [11] is an energy efficient and time optimum algorithm. According to this algorithm every node will put itself to sleep mode. Based on the duty cycle table every node in the network will send and receive the messages. Algorithm for fair data gathering tree attains minimum sensor sink delay and also reduces idle listening.

   Sensor nodes with network based PC base station minimize cost of communication by using Ken a robust approximate technique. It uses replicated dynamic probabilistic models.

   To maintain network model and to reduce communication cost between sensor nodes this algorithm exploit spatial correlation across sensor nodes.

3. System model

   This project considers data collection once per sampling interval where data collected from sensor nodes to the base station. This design assumes that sensor nodes are organized and rooted at the base station for data collection

   .

   In addition to reporting its own data, each internal node in the tree is also responsible to its parent. We consider a continuous data collection scenario in which data is collected from sensor nodes to the base station once per sampling interval. In each sampling interval, sensor nodes first sample local phenomena (like temperature and solar radiation) and then transmit the acquired data to the base station. Following common practices [6][9], [10], [12], we assume that the sensor nodes are organized into a tree structure rooted at the base station for data collection. In addition to reporting its own data, each internal node in the tree is also responsible for forwarding the data received from its children to its parent. If the data is redundant then sensor node may not report its acquired data to the base station. Decisions of what data to report are driven by the data itself and this scenario takes place only after data are acquired by the sensor node. As a result, the network traffic pattern of data collection changes over different sampling intervals in an unpredictable manner.

4. Proposed scheduling algorithm

   1. Traffic pattern oblivious (TPO) scheduling algorithm

      This project proposes the novel scheduling algorithm called TPO (Traffic pattern oblivious) which work for any network traffic pattern and constructs schedule. This TPO scheduling algorithm allocates schedules in rounds. For each round the algorithm allocates one new transmission slot to a node which has not assigned its required number of transmission slots. It is been assumed that the rooted tree with sub-tree of size x needs a total of x transmission slots. Hence in every round i combine all the nodes rooted at subtrees of size i.

      1. Algorithm 1: TPO Scheduling Algorithm

         1: let N be the list of all nodes in a post-order traversal;

         2:. for each node v in N do 3: TS(v) ;

         4: while N = do

         5: for each node v in N do

         6: t min _s | s / _uI(v) TS(u) and s > j, j

         TS(v) c C(v) TS(c)};

         7: TS(v) TS(v) all {t}; 8: if |TS(v)| = |Tv| then 9: remove v from N;

         Figure 2 : An example execution of the TPO Algorithm

   2. Distributed implementation of TPO algorithm In this project TPO scheduling algorithm is

      implemented in distributed manner. This project assumes that every child node c(v) knows its parental node p(v) for each sensor node v

      .Algorithm 2 presents pseudo code for distributed implementation algorithm. Each node independently can choose its own transmission slots. A token message is sent to all the nodes those who have not selected their transmission slots in post order in every round. First the token will be generated by base station and circulated it to its children(step 1-3).When a child node receives a token from its parental node p(v) it indicates beginning of new round (step 23-24). Hence parental node p(v) forwards the token one at a time (step 25-27).If the token traversed all children node of parental node of vs in Cn(v) and comes back to parental node to choose new transmission slot t (step 28-30).consistently throughout duration

      of continuous data collection TPO algorithm should be constructed. Hence duration continuous data collection is minimal.

      1. Algorithm 2: Distributed TPO Algorithm 1: Ctovisit CN(s);

         2 :s sends TOKEN to a node w Ctovisit;

         3: Ctovisit Ctovisit {w}; 4: while CN(s) do

         5: wait for a TOKEN message to arrive;

         6 : if TOKEN_t, tag is received from a child u then

         7: CTS(u) CTS(u) U {t};

         8: if tag = finished then CN(s) CN(s) {u}; 9 : if Ctovisit then

         10: s sends TOKEN to a node w Ctovisit; 11: Ctovisit Ctovisit {w};

         12 : else Ctovisit CN(s); 13 : while |TS(v)| |Tv| do

         14 : wait for a message to arrive;

         15: if MN_t, tag is received from a node u then 16: CS(v) CS(v) U {t};

         17: if tag = finished then IN(v) IN(v) {u}; 18: else if a TOKEN message is received then

         19: if TOKEN_t, tag is received from a child u

         then

         20: CTS(u) CTS(u) U {t};

         21: if tag = finished then

         22: CN(v) CN(v) {u};

         23 : if TOKEN is received from parent pv then

         24: Ctovisit CN(v); 25: if Ctovisit then

         26: v sends TOKEN to a node w Ctovisit; 27: Ctovisit Ctovisit {w};

         28: else

         29: t min {s | s U CS(v) and s > j, j TS(v) all cC(v) CTS(c)};

         30: TS(v) TS(v) U {t};

         31: if |TS(v)| < |Tv| then tag = unfinished; 32 : else tag = finished;

         33: v sends a notification message MN<t, tag> to all

         Table 1 : Parameters used for simulation

         Parameters	Values
         Area	300*300sqm
         No. of nodes	25
         Transmission range	0.15
         Sample Interval	200
         Data sending rate	200 kbps
         Error bound	15 W/m2
         Initial energy	7.5 joules
         Packet receiving power	175 mW
         Packet tranmission power	175 mW
         Packet size	512 Bytes
         Routing protocol	AODV

         5.1 Scenario for S-MAC Technique using TPO algorithm

         Simulation is performed on a network where nodes are randomly deployed over square field with base station located at the center of the node. Data collection is done by constructing an breadth first search algorithm where base station located at root and conflict constraints are placed on scheduling.

         Fig 3 show all nodes communicating neighboring nodes to know their positions to send data packet while transmission. Figure 4 show implementation of TPO algorithm in S-MAC where all nodes of dynamic traffic pattern sending data to the base station at different transmission slots.

         nodes in IN(v);

         34: v sends TOKEN_t, tag back to parent pv; slots. Acknowledgements

5. Simulation

   We have done simulation scenarios which evaluate performance of proposed TPO algorithm for various traffic patterns. These Simulation were implemented using NS-2.

   Figure 3 : Sensing neigboring nodes

   Figure 4 transmission packets to the base station from all the nodes.

   Figure 5 shows performance for different error bounds based on number of slots used.

   Figure 6 shows energy consumed by sensor nodes based on error bound.

   Figure -5 shows that proposed TPO scheduling algorithm for different energy bound based on the different number of transmission slots lead ower energy significantly. Over a range of error bound. The latency of TPO is much higher than TIGRA. The TPO algorithm spends much less energy than SPARSE for most consuming node as shown in figure 6 .

6. Conclusion

   In this paper, the novel S-MAC scheduling algorithm is been proposed for data collection. The proposed schedule algorithm is traffic pattern oblivious which achieves higher energy efficiency and time efficiency while data collection for any type of traffic pattern in continuous data collection. The algorithm reduces latency by using less number of transmission slots.

   This algorithm allows identifying end of transmission while receiving data from sensor nodes hence it will stop listening to the sending node and consumes less energy.

7. References

1. Wenbo Zhao and Xueyan Tang Scheduling sensor data dollection with dynamic traffic patterns IEEE COM mini conference, pp. 286-290 Apr.2011

2. G. Werner-Allen, K. Lorincz, M. Ruiz,

   O. Marcillo, J. Johnson J. Lees,and M. Welsh Deploying a Wireless Sensor Network on an Active Volcano, IEEE Internet Computing, vol. 10, no. 2, Mar.- Apr. 2006.

3. O. Chipara, C. Lu, and J. Stankovic, Dynamic Conflict-free Query Scheduling for Wireless Sensor Networks, Proc. IEEE ICNP 06, pp.321331, Nov. 2006

4. S. Gandham, M. Dawande, and R. Prakash, Link Scheduling in Sensor Networks: Distributed Edge Coloring Revisited, Proc. IEEE INFOCOM 05, pp. 24922501, Mar. 2005.

5. B. Yu, J. Li, and Y. Li, Distributed Data Aggregation Scheduling in Wireless Sensor Networks, Proc. IEEE INFOCOM 09, pp. 21592167, Apr. 2009.

6. J. Gehrke and S. Madden, Query Processing in Sensor Networks, IEEE Pervasive Computing, vol. 3, no. 1, pp. 4655, Jan.-Mar. 2004

7. W. Song, F. Yuan, and R. LaHusen, Time-Optimum Packet Scheduling for Many-to-One Routing in Wireless Sensor

   Networks, Proc. IEEE MASS 06, pp. 8190, Oct. 2006.

8. S. Chen, S. Tang, M. Huang, and Y. Wang, Capacity of Data Collection in Arbitrary Wireless Sensor Networks, Proc. IEEE INFOCOM 10, pp. 15, Mar. 2010.

9. Y. Xu and W. Wang, Scheduling Partition for Order Optimal Capacity in Large-Scale Wireless Networks, Proc. ACM MobiCom 09, pp. 109 120, Sept. 2009.

10. D. Chu, A . Deshpande, J. Hellerstein, and W. Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proc. IEEE ICDE 06, Apr. 2006.

11. H. Wu, Q.Luo, and W. Xue, Distributed Cross-Layer Scheduling for In-Network Sensor Query Processing, Proc. IEEE PerCom 06, pp. 180189, Mar. 2006.

12. S. Gobriel, D. Mosse, and R. Cleric, TDMA-ASAP: Sensor Network TDMA Scheduling with Adaptive Slot-Stealing and Parallelism, Proc. IEEE ICDCS 09, pp. 458465, Jun. 2009.

13. Y. Liu and M. Li, Iso-Map: Energy- Efficient Contour Mapping in Wireless Sensor Networks, Proc. IEEE ICDCS 07, Jun. 2007.

14. Ramaraju Kalidindi, Lydia Ray, Rajgopal Kannan1, Sitharama Iyengar, Distributed Energy Aware MAC Layer Protocol For Wireless Sensor Networks,2009.

15. An Adaptive Energy Efficient Forwarding Data Aggregation and QoS Protocol for Wireless Sensor Networks, Basavaraj. S. Mathapati,Department of CSE. Appa IET, Gulbarga,Karnataka.

Miss Pushpa.S received her Bachelor of Engineering in Information Science and engineering in 2009. Currently She is a M.Tech student in Computer Networking Engineering from Visveswaraya Technological University at The Oxford College of Engineering, Bangalore. Her research interests are wireless sensor networks, Networking, datacollection in wireless sensor nodes.

Mrs P.Mangayarkarasi received MCA in 1997 from Avinashi Lingham Deemed University with first class, she received M.Tech with distinction from MGR university, Chennai in 2006. She is pursuing PhD in software Engineering at Visvesvaraya Technological University. Currently she is working as Assistant Professor in Dept of ISE, The Oxford College Engineering, Bangalore. Her main research areas are software engineering, Data mining and sensor networks.