Minimizing the schedule length for fast converge cast in tree based WSNS

Minimizing the schedule length for fast converge cast in tree based WSNS

Minimizing the schedule length for fast converge cast in tree based WSNS

SIVARANJANI R SANGEETHA K ANBUELAVENI A

Abstract-In wireless sensor networks, data from all the sensors should be received within a specific deadline. The factors limiting the data collection are topology, scheduling and interference. These limitations can be eliminated through the concept of time slot reusability. The proposed approach will increase the number of concurrent transmission which in turn minimizes the schedule length to achieve fast converge-cast. The simulation results show that number of slots required for data collection will be reduced.

Keywords: Wireless Sensor Networks; Converge-cast; Schedule length.

1. I ntroduction

   Data collection from a set of sensors to a common sink over a tree-based routing topology is a fundamental traffic pattern in wireless sensor networks (WSNs). This many-to-one communication pattern in which data flows from many nodes to a single node is known as converge-cast [Gandham et al. (2008)]. Converge-cast is opposite to broadcast or multicast in which data flows from a single node to a set of nodes in the network. Fig.1.shows an example for converge-cast. In converge-cast, as shown in Fig.1. each node has a message destined to the sink node and the intermediate nodes serve as a relay. Once data is collected at the sink, it either can be recorded and stored for future analysis or can be processed immediately to take certain actions depending on application requirements. The two fundamental types of data collection in WSN: (i) raw-data converge-cast, where every packet is relayed individually and (ii) aggregated converge-cast, where packets are aggregated at each hop before being relayed [Upadhayaula et al. (2007)]. Aggregated converge-cast is

   applicable when a strong correlation exists in the sensor readings or the goal is to collect summarized information, such as the maximum sensor reading.

   Fig.1. An example of Converge-cast in WSN

   Raw-data converge-cast, on the other hand, is applicable when every measurement is equally important or the correlation is minimal. These two types correspond to two extreme cases of data collection in sensor networks. Table1. shows the differences between aggregated converge-cast and raw-data converge-cast.

   Sivaranjani.R, Sangeetha.K, Anbuelaveni.A

   452

   Table 1. Difference between Aggregated And Raw Data Converge-cast

   S No.	Aggregated Converge-cast	Raw Data Converge-cast
   1	Occurs without external triggering.	Occurs with external triggering.
   2	Packets are aggregated at each hop.	Packets are individually relayed. towards sink.
   3	Applicable when strong spatial correlation exists in the data.	Applicable when the correlation is minimal.
   4	Collect summarized information such as the maximum sensor reading.	Every sensor reading is equally important.
   5	Energy efficiency is required due to its long term process.	Quick and reliable data transmission is required.
   6	Collected data can be recorded or stored for further processing.	Processed immediately to take certain action.
   7	Complete data compression.	No data compression.

2. Related Works

   Particularly under regular, heavy traffic conditions, contention-free medium access control (MAC) protocols, such as time division multiple access (TDMA), where nodes communicate on different time slots to prevent conflicts, offer several advantages for data collection as compared to contention-based protocols [Gandham et al. (2008)]. Here collisions, overhearing, and idle listening are eliminated, which are the main sources of energy consumption in wireless communications. In addition, nodes are also permitted to enter into sleep modes during inactive periods, thus achieving low duty cycles and conserving energy. Furthermore, TDMA-based communications can provide provable guarantee on the completion time of data collection, for instance, in timely detection of events. Another key aspect of time-slotted communication is robustness during peak loads. When the number of source node are many or the

   data rates are high, carrier-sense multiple access protocols, such as CSMA, may fail to successfully allocate the medium, causing retransmissions and collisions. The time scheduling with transmission power control reduces interference as well schedule length in tree based wireless sensor networks.

   The primary limiting factors of fast data collection are: (i)

   interference in the wireless medium, (ii) half-duplex transceivers on the sensor nodes, and (iii) topology of the network as mentioned by [Ozlem et al. (2011)]. The project explores a techniques that provide a hierarchy of successive improvements in the simplest way among which is an interference-aware, minimum-length, TDMA scheduling that enables spatial reuse. To achieve further improvement, transmission power control is combined with scheduling to enable more concurrent transmissions. Minimal schedule length can be achieved by maximizing the reuse of the time slots. In certain cases, a minimal schedule length may also contribute to minimizing the latency of data collection.

3. Proposed Approach

   For converge-cast, finding a minimum-length, conflict-free assignment of time slots, such that every packet generated by a node reaches the sink, is fundamental to efficient network operations. Several variants of the problem exist depending on network topology, interference model, packet generation scheme, number of frequency channels, buffer constraints, antenna models, etc. The paper is based on tree based routing topology, time scheduling and power control.

   1. Tree Based Routing Topology With Power Control

      Routing trees that allow more parallel transmissions do not necessarily result in small schedule lengths. For instance, the schedule length is N for a network connected as a star topology, whereas it is (2N 1) for a line topology once interference is eliminated. The routing tree should be constructed such that all the branches have a balanced number of nodes and the constraint nk < (N + 1)/2 holds. In this project, such routing tree is constructed. Assume that the nodes know their minimum-hop counts to sink and the weight of each link is taken as 1. In wireless networks, excessive interference can be eliminated by using transmission power control i.e., by transmitting signals with just enough power instead of maximum power. To this end,the impact of transmission power control on fast data collection is evaluated using discrete power levels, as opposed to a continuous range where an unbounded improvement in the asymptotic capacity can be achieved by

      Sivaranjani.R, Sangeetha.K, Anbuelaveni.A

      453

      using a non-linear power assignment. The algorithm proposed by [El Batt et al.(2002)] is a cross layer method for joint scheduling and power control and it is an optimal distributed algorithm to improve the throughput capacity of wireless networks. The goal is to find a TDMA schedule that can support as many transmissions as possible in every time slot. It has two phases: (i) scheduling and (ii) power control that are executed at every time slot. First the scheduling phase searches for a valid transmission schedule, i.e., largest subset of nodes, where no node is to transmit and receive simultaneously, or to receive from multiple nodes simultaneously. Then, in the given valid schedule the power control phase iteratively searches for an admissible schedule with power levels chosen to satisfy all the interfering constraints. In each iteration, the scheduler adjusts the power levels depending on the current RSSI at the receiver and the SINR threshold according to the iterative rule (as specified in Eq.(1)):

      P new = ( / SINR ) * P current

      According to this rule, if a node transmits with a power level higher than what is required by the threshold value, it should decrease its power and if it is below the threshold it should increase its transmission power, within the available range of power levels on the radio. If all the nodes meet the interfering constraint, the algorithm proceeds with the schedule calculation for the next time slot. On the other hand, if the maximum number of iterations is reached and there are nodes which cannot meet the interfering constraint, the algorithm excludes the link with minimum SINR from the schedule and restarts the iterations with the new subset of nodes. The power control phase is repeated until an admissible transmission scenario is found.

   2. Scheduling

   The nodes do not required to store more than one packet in their buffer at any time. Initialize all the buffers as full, and assume that the sinks buffer is always full for the ease of explanation. The balanced tree consists of root and branches. A branch is eligible if its top node has at least one packet to transmit. For a given time slot, schedule the top node of an eligible branch which has the largest number of total (remaining) packets. If none of the branches are eligible, the sink does not receive any packet during that time slot. Inside each branch, nodes are scheduled. A branch is active if there

   are still packets left in it (excluding its top node) to be relayed. If a nodes buffer is empty and the branch pointed at this node is active, schedule one of its end node at random whose buffer is not empty. The algorithm guarantees that in an active branch there will always be at least one end node whose buffer is not empty, and so whenever a node empties its buffer, it will receive a packet in the next time slot, thus emptying buffers from the end node to the top.

4. Performance Evaluation

The proposed approach is simulated and evaluated with NS2. NS2 is simulation software selected to implement the model. NS-2 is a discrete event simulator targeted for network research and provides support for simulating protocols on conventional networks and wireless networks. NS-2 is written in C++ and for simulation setup a script language called OTcl (Object Tcl) is used .A network simulation requires that an OTcl script for network configuration, a

mobility pattern(1d)escribing node movement, a traffic pattern describing data traffic, and files describing coordinates for

obstacles and pathways. In addition, it is necessary to trace the mobility model used, as well as the type of traffic at which level, i.e., routing, media access control (MAC) or application, into some output files for post-simulation analysis. Depending on the users purpose for an OTcl simulation script, simulation results are stored as trace files, which can be loaded for analysis by an external application. Parameters that are used for the analysis of the proposed system is shown in Table.2.In our simulation analysis, sensor nodes are randomly distributed in a 300 m × 300 m area.

Table 2. Parameter used in Simulation

Sivaranjani.R, Sangeetha.K, Anbuelaveni.A

454

According to Fig.2. the total number of slots required for data collection is lower bounded to N/2. In the X-axis the various schedule length varying fromm25 to 300 indicates the presence of interfering links. Though the schedule length becomes 3N, the proposed approach reduces the number of slots. Fig.3. illustrates the node sensing. Fig.4. shows that the sink node is represented in pink colour. Taking sink as root a balanced tree is formed to increase the concurrent transmissions.

Fig.2. Side Length Vs Number of time slots

Fig.3. Node Sensing

Fig.4. Tree based scheduling

Sivaranjani.R, Sangeetha.K, Anbuelaveni.A

455

5. Conclusion.

In this paper, we have proposed the minimum schedule length data collection approach in order to increase the convergecast. When L<200, the schedule length is bounded by N(total number of nodes in the network). For sparser networks i.e.) L>200, reusability is very less than scheduling. In the case of denser network , most of the interfering links are eliminated. This approach increases the average residual energy of sensor nodes to increase the life time of the network. In future we will evaluate this approach with various node densities.

References

1. Akyildiz.,I.F.; Su,W. (2002) : A Survey on Sensor Networks. IEEE Communication Magazine, August .

2. Aslam, N.; Phillips, W.; Robertson, W.; Sivakumar, S. (2011) : A Multi-Criterion Optimization Technique for Energy Efficient Cluster Formation in WSNs . Information Fusion, Vol. 12, No. 3, pp. 202- 212.

3. Chintalapudi, K.K.; Venkatraman,L.(2008) : On the design of mac protocols for low-latency hard real-time discrete control applications over 802.15.4 hardware . IPSN, pp. 356367.

4. ElBatt,T.; Ephremides, A .(2002) : Joint scheduling and power control for wireless ad-hoc networks. INFOCOM, Jun, pp. 976984.

5. Gandham,S.; Zhang, Y.; Huang, Q.(2008) : Distributed time-optimal scheduling for converge-cast in wireless sensor networks .Computer Networks, vol. 52, no. 3, pp. 610629.

6. Huang, X.; Fang,Y. (2008) : Multiconstrained QoS Mutlipath Routing in Wireless Sensor Networks.Wireless Networks, Vol. 14, No. 4, pp. 465-478.

7. Incel,O.D.; Krishnamachari,B.(2008) : Enhancing the data collection rate of tree-based aggregation in wireless sensor networks. SECON, San Francisco, CA, USA, pp. 569577.

8. Liu,M.; Cao, J.N.; Chen , G.H.; Wang, X.M .(2009) : An Energy- Aware Routing Protocol in Wireless Sensor Net-works. Sensors, Vol. 9, No. 1, pp. 445-462.

9. Lung, C.H.; Zhou, C.J. (2010) : Using Hierarchical Agglomerative Clustering in Wireless Sensor Networks: An Energy-Efficient and Flexible Approach. Department of Sysems and Computer Engineering Carleton University, Ottawa, Ontario, Canada.

10. Moscibroda, T.(2007) : The worst-case capacity of wireless sensor networks . IPSN, Cambridge, MA, USA, pp. 110.

11. Shio, K.S. ; Singh, M.P .; Singh, D.K. (2010): Routing Protocols in

    Wireless Sensor Networks A Survey. International Journal of Computer Science & Engineering Survey (IJCSES) Vol.1, No.2, November .

12. Othman, J.B.; Yahya, B. (2010) :Energy Efficient and QoS Based Routing Protocol for Wireless Sensor Networks. Journal of Parallel and Distributed Computing, Vol. 70, No. 8, pp. 849-857.

13. Ozlem ,D.I.; Amitabha, G.; Bhaskar , K. (2011) : Scheduling Algorithms for Tree-Based Data Collection in Wireless Sensor Networks. An EATCS Series.

14. Talzi, I.; Hasler,A.; Gruber,S.; Tschudin, C. (2007) : Permasense: investigating permafrost with a wsn in the swiss alps. EmNets, Cork, Ireland, pp. 812.

15. Upadhyayula, S.; Gupta, S. (2007) : Spanning tree based algorithms for low latency and energy efficient data aggregation enhanced convergecast (dac) in wireless sensor networks. Ad Hoc Networks, vol. 5, no. 5, pp. 626648, 2007.

16. Wu, Y.; Stankovic, J.; He, T.; Lin, S.(2008) : Realistic and efficient multi-channel communications in wireless sensor networks. INFOCOM , pp. 1193120

Sivaranjani.R, Sangeetha.K, Anbuelaveni.A

456