Heuristics Based Tree Switching in Two-sink Sensor Networks

Abstract

In sensor networks, tree is a well-known topology formation method and TDMA is a desirable MAC protocol due to guaranteed channel access and no collisions. Many times node distribution across the region is not uniform. If finer observations are required in a region, node density is kept high. But in other regions where accurate readings are not needed, network may be sparse. Often multiple sinks are deployed in WSNs. Use of multiple sinks provides fault tolerance and load balancing. When multiple sinks are deployed, more than one sink-rooted trees are formed. The trees with dense node deployment would have higher schedule lengths than the trees with sparse node deployment. Thus trees part of the same network have different schedule lengths. In other words, schedule lengths are not balanced. As a result, nodes of some trees (with higher schedule length) have to wait for longer duration for transmission turn compared to the nodes of the other trees (with lower schedule length). As all the nodes belong to the same network, it is desirable that the waiting time for transmission turn should not be very different. So, schedule length balancing is required to ensure fairness. In this work, an algorithm known as HTSTSN (Heuristics based Tree Switching in Two-sink Sensor Networks) algorithm for two-sink network is proposed. It helps every node to decide which sink (i.e. tree) to join such that schedule lengths of trees remain balanced. The HTSTSN algorithm executes before actual scheduling algorithm. It is shown through simulations that the proposed algorithm results in average 13%  to 74% reduction in schedule length difference and maximum 12% increase in energy consumption. It is found that the HTSTSN algorithm balances schedule length without much affecting the network lifetime.