International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

A Novel Routing Protocol For Target Tracking In Wireless Sensor Networks

Sanjay Pahuja and Tarun Shrimali 

School of Computer and Information Science, Indira Gandhi National Open University, New Delhi, India

Abstract 


Wireless sensor networks (WSNs) are large scale integration consists of hundreds or thousands or more number of sensor nodes. They are tiny, low cost, low weight, and limited battery, primary storage, processing power. They have wireless capabilities to monitor physical or environmental conditions. This paper compared the performance analysis of some existing routing protocols for target tracking application with proposed hierarchical binary tree structure to store the routing information.  The sensed information is stored in controlled way at multiple sensor nodes (e.g. node, parent node and grandparent node) which deployed using complete binary tree data structure. This reduces traffic implosion and geographical overlapping. Simulation result showed improved network lifetime by 20%, target detection probability by 25%, and reduces error rate by 20%, energy efficiency, fault tolerance, and routing efficiency. We have evaluated our proposed algorithm using NS2.  

Keywords


WSN, HLTS, SPIN, LEACH, DD, Network Simulator 2. 

1.Introduction


The various routing scheme either based on flat or hierarchical have been reviewed in the literature. These routing schemes employ some well-known data aggregation (Meng et al., 2013, Tharini  et al., 2011) function at some level to reduce number of messages for transmission to prolong the network lifetime.  Different routing techniques are reviewed below.

Table 1. Routing Techniques inWSN

Motivation: None of the above routing protocols is suitable for target detection and tracking. This motivate us to proposed a new hierarchical localization tracking scheme to improve network lifetime, reduce energy consumption, increase probability of target detection with good fault tolerance properties and scalability.

Contribution: We have proposed a hierarchical target monitoring and tracking method for multiple moving targets. The sensed information is stored at node as well as its parent and grandparent node. This increased small redundancy but increase fault tolerance.  Some of the basic challenges of routing and as well as target tracking for WSN are discussed.

Energy Consumption: Each sensor nodes have limited energy. Thus energy uses is very important for transmission of information in a multi hop wireless environment. Each node plays a multiple role as sender, receiver and router, so energy requirement is very crucial. Some sensor nodes dead due to power failure can cause significant network partition and reorganization network topology (Ian F. Akyildiz et al., 2004).

Scalability: Scalability measures the performance while number of sensor nodes increased. For large scale network, the number of sensor nodes deployed may be in the order of hundreds or even more. The network said to be scale if does not degrade its performance even for large size (K. Akkaya et al., 2005).

Data Aggregation: Sensor nodes usually sense similar information at multiple nodes at same duration. When same information is transmitted or forwarded towards the base stations by many nodes it is aggregated at some nodes according to a certain data aggregation function, e.g., discarded suppression, mean, minima and maxima (K. Khedo et al., 2010).

Connectivity: The network connectivity is very important in sensor networks. If every sensor nodes reachable in any time, then network is always connected.  Wireless ranges decide the connectivity of WSN (S. Gupta et al., 2011).

Section 2 makes review of the some existing routing protocols Sensor Protocols for Information via Negotiation (SPIN), Directed Diffusion (DD) and Low-energy Adaptive Clustering Hierarchy (LEACH). The survey motivates to move in the direction of proposing new hierarchical binary tree based scheme for target detection and tracking for better network life time, better connectivity, reduce energy consumption and provide better probability of target detection. Section 3 best describe the proposed HLTS scheme followed by section 4 of simulation environment. Section 5 elaborates the result and discussions following by conclusion in Section 6.

2. Routing Protocols For WSNs


Routing protocols based on network structure is divided into two categories: flat routing and hierarchical routing. In a flat routing, all nodes are at same level whereas in hierarchical routing they have different level. We have reviewed some flat routing protocols Sensor Protocols for Information via Negotiation (SPIN) (Kulik et al., 2002), Directed Diffusion (DD) (Intanagonwiwat et al., 2005) and Energy-Aware Routing (EAR) etc. The typical hierarchical routing protocols in WSNs include Low-energy Adaptive Clustering Hierarchy (LEACH) (Heinzelman et al., 2000), Hybrid Energy-Efficient Distributed clustering (HEED) (Younis et al., 2004 ), Distributed Weight-based Energy-efficient Hierarchical Clustering protocol (DWEHC).

2.1 Sensor Protocols for Information via Negotiation

Sensor Protocols for Information via Negotiation (SPIN) is one of the flat routing protocols based on data centric negotiation. The SPIN protocol is designed to disseminate the data of individual nodes to all other sensor nodes. The main idea is to reduces duplicate information and prevent redundant data. For negotiation and data transmission, SPIN first uses ADV message to its neighbor nodes. Second message REQ is generate by the nodes those are interested. Third message DATA is send by the node to the requested neighbors (XuanTung Hoang et al., 2009). SPIN is event driven based negotiation. The data delivery ratio is lower but also has low routing overhead.

2.2. Directed Diffusion 

Directed Diffusion (DD) is categories as flat routing protocol which is data-centric protocol for dissemination. Directed diffusion is work in close proximity to localized the message exchanges within the limited network vicinity.  The main parts of direct diffusion are request, message, reply and reinforcement.  Directed diffusion is demand driven and it is improvement over SPIN using attribute-value pair. Direct diffusion has multiple path, so data delivery ratio is higher than SPIN but suffer higher routing overhead.

2.3 Low Energy Adaptive Clustering Hierarchy

Low-Energy Adaptive Clustering Hierarchy (LEACH) is the first clustering routing algorithms proposed for sensor networks. It is based on hierarchical routing. In a hierarchical routing, nodes are at different level and according to level they have different tasks. The main tasks of LEACH are prolong network lifetime reducing the number of transmission messages by using data aggregation. LEACH partition the entire network into a set of clusters. Each cluster has a randomly selected cluster head. Once a node become a cluster head is no more allowed to become a cluster in any subsequent round. Each node has a time slot to transmit its data to cluster head using time division multiple access (TDMA) based schedule (Feng Wang et al., 2011) 

3. Hierarchical Localization Tracking Scheme


The proposed Hierarchical Localization Tracking Scheme (HLTS) scheme is based on hierarchical routing. The scheme is for target detection where sensor nodes are static and target are dynamic. This type of application required large messaging.  Here we have considered the routing scheme for target detection and tracking. We have used complete binary tree data structure to store the sense information at the node, parent and grandparent node of the sensor, which locate the target. The sensed information is further aggregate and transmits to base station. The redundancy improved the fault tolerance properties of the algorithm. We have used system model which include

Network model: In network model we assume that sensor nodes are deployed in a two-dimensional terrain.  They are placed randomly with density of λ using Poisson distribution (Demigha et al., 2012) as in equation (1).

 

Target motion model: Assuming the target moves in a two-dimensional plane, the target motion model is described as in equation (2)

 

where Xk is the target state at the kth time stamp, Fk is the state transition matrix, and wk ∼ N(0, Qk) is the noise factor support Gaussian distribution and Qk is variance (Chen et al., 2011).

 

Where T represent the sampling time of discrete time interval.

 

Target localization model: In   general, a target can be detected by its nearby sensors. Therefore, we have used the simple centroid algorithm (Jie Li et al., 2015) to calculate the position of the target, which is described as in equations (4) and (5)

 

and

 

where ( ,  ) is the estimated location of the target t, (( , ) is the location of sensor node si detecting the target, and n  is the number of sensor nodes detecting the target. This localization algorithm is simple and works for all kinds of sensors

In our proposed scheme we have used complete binary tree structure for positioning the nodes in the grid. As object is sensed by the sensor nodes, than its parent and grandparent nodes are selected to monitor the movements of the object.  A target trajectory is calculated. Nodes tracking the object keep changing as the object moves and subsequent parent and grandparent nodes. The detection process is constantly track based on the location of the object at different time stamp.

A target will be detected by sensor node si when it appears in sensing region R (si, rs). Conversely, sensor nodes in the distance of rs can only detect the target.

Algorithm- Target Detection

  1. Define a two dimensional grid with 1000mx1000m.
  2. Generate coordinates (x, y) of the sensor nodes at

           in the terrain using Poisson distribution.

  1. Define all possible paths in the terrain
  2. Start simulation by placing the object at a random

           position.

  1. Trace the location of the objects in track.
  2. Find the nearest sensor node‘s’, that detected the

          object‘t’.

  1. Let sensor node ‘s’, locate the target ‘t’

          Xk [s] [t] [s] = 1

          Xk [s/2] [t] [s] = 1

          Xk [s/4] [t] [s] = 1

  1. Repeat step 3 to 7 until all target detect or

          simulation exhaust

  1. End Target Detection

Algorithm: Target Trajectory

  1. Let t is the target object
  2. Start from the any sensor node in the grid

                                  Repeat step 3 & 4 until node = NULL

  1. For i =1 to number  of sensor nodes

                                If  Xk [node] [t] [i] = 1

           Then store node i position in tracking path.

  1. node =node->Lchild

                             Start from the next node (say node)

                             Repeat step 5 & 6 until node = NULL

  1. Same as step iii
  2. node = node->Rchild
  3. Display path with trajectory
  4. end Target Trajectory

4. Simulation Environment 


4.1 Performance Metric   

We evaluated the following performance metrics.

Network lifetime: The network lifetime is indirectly proportional to simulation time. Network has less energy consumption that means higher the network lifetime. The number of live nodes in the network is higher even after some simulation time.

Average energy consumption: The average energy consumed by network is the total energy required by the nodes in receiving, forwarding and transmitting the information. Initially each node assigned initial energy and its energy level is computed each time as per energy simulation parameters.

Scalability: A protocol is scalable if it is applicable to large as well as small populations. A crucial issue for WSN is the handling of a large number of nodes.

Routing Overhead: The routing overhead measures the total number of bytes sent extra as compared to actual bytes sent. We have scale routing overhead between 0 to 1.

Target detection probability: Target detection probability measure how accurate the target detected. This required low false alarm rate and bounded detection delay. It is measure the sensing performance of the network. 

Error rate: Number of time false target detected or mismatched.

4.2 Simulation Parameters 

We have used following simulation parameters as mention in Table II.

5. Results And Discussion


Fig. 1 show the snapshot of nodes in the network where protocols are implemented. A 1000m*1000m square terrain dimension is considered and sensor nodesare placed using Poisson distribution. The sink node, which is represented x, is located at the center of the network (500m, 500m).

Table II: Simulation parameters

Here, the advance nodes are shown by a plus symbol (+) and the normal nodes by a circle (0). In Fig. 1, 500 nodes are placed randomly in the network. Initially all nodes are live. The performance comparison is done in NS-2. Various performance metrics is computed to compare HLTS with the SPIN, DD and LEACH protocols.

5.1 Network Lifetime 

Fig. 2 show performance graph between numbers of sensor nodes with network lifetime while transmission range is 100m and 300m. As increasing number of sensors, the network lifetime increases. The network lifetime is not well scalable for any of these protocols. In this comparison network lifetime is measures as active number of nodes in the network. The HLTS has 10-20% higher network lifetime as compared to SPIN, LEACH and DD even when sensing range is higher. SPIN is worst hit as more messages generated for negotiations. SPIN and DD both not suitable for large scale network due to flat routing. LEACH and HLTS however have some scalable properties due to hierarchical properties.

Fig. 3 shows the comparisons between numbers of nodes vs. number of rounds. Increase in the network lifetime as number of nodes is increases. As number of nodes increases, more cover set generated. Thus excessive messaging is generated among the nodes.  When number of nodes reached around 250-300 all protocols network lifetime (number of rounds) decreases. HLTS drops its number of rounds to 1100 when number of nodes reached 500.  LEACH drops its number of rounds to 950 when number of nodes reached 500. DD drops its number of rounds to 850 when number of nodes reached 500. SPIN drops its number of rounds to 800 when number of nodes reached 500. Hence HLTS has 15-20% higher network lifetime as compared to these protocols.

5.2 Total Energy Consumption 

Fig. 4 shows the graph comparing the number of rounds vs. total energy consumption among SPIN, DD, LEACH and HLTS. In the proposed algorithm HLTS the total energy consumption is 95 Joules around at rounds 600, whereas SPIN protocol consumed 150 Joules, DD consumed 120 Joules and LEACH consumed 107 Joules. HLTS reduces energy consumption since only activated nodes in the network are involved in network and rest of nodes remains in standby mode.

 

Fig. 1 Sensor nodes distribution in 1000m x 1000m field

Fig. 2 Number of Nodes vs. Network Lifetime

Fig. 3 Number of Sensor Nodes vs. Number of Rounds

Energy consumption increases for all routing scheme as number of nodes increase. But HLTS has 20% less consumption because its uses two level hierarchy of binary tree to store the redundant information.

 

Fig. 4 Total Energy Consumption vs. Number of Rounds

5.3  Scalability 

The routing protocol is said well scaled when it experiences minimal performance degradation when used in increasingly large networks. Fig. 5 measure the scalability against the data delivery ratio by varying the number of nodes. HLTS, DD and LEACH routing scheme well scale up around 250- 300 nodes. Packet delivery ratio more decreases for LEACH, SPIN and DD protocols as compared to proposed HLTS scheme while increasing the number of nodes. Packet delivery ratio is 0.76 for SPIN, 0.8 for DD, 0.82 for LEACH and 0.85 for HLTS when nodes 500 in the network.

5.4 Routing Overhead 

Routing overhead can be define as a ratio of total number of bytes sent in overhead as compared to the total number of bytes sent in data transmission successful. It is normalized to measure between 0 to 1. Figure 6 shows number of nodes vs. normalized routing overhead. When number of nodes around 100 in the network, the routing overhead is less for all protocols. As number of nodes increases routing overhead also increases. When number of nodes 500, SPIN protocols has 70% normalized routing overhead i.e. 70% extra bytes sent as compared payload. At the same scene HLTS has 38%, DD has 62% and LEACH has 45% normalized routing overhead.

As the number of nodes increased, normalized routing overhead increased sharply especially when number of nodes is high. DD suffer highest routing overhead as its nature is flooding, while leach has moderate routing overhead. HLTS has higher overhead but it is 20-30% less as compared to these two routing schemes.

 

Fig. 5 Data Delivery Ratio vs. Number of Nodes

Fig. 6 Normalized Routing Overhead vs. Number of Nodes

5.5 Target Detection Probability 

Fig. 7 shows the transmission range vs. probability of target detection. When a target is sensed by a sensor, a three dimension array is used to store the location of target. Xk store the target state at k step.  Target state is toggle between 0 and 1. When state is fixed i.e. either target is in or out from the trajectory.  This is to   minimizing false alarms. Up to transmission range 150m, all protocols have almost 90% target detection probability. As transmission range increases the target detection probability sharply decreases.

Figure 8 shows the number of sensor nodes vs. probability of target detection with 100m transmission range and target speed is 10m/sec. As the number of nodes increasing all protocols have higher probability of target detection. Initially, as network density increased the connectivity as well as scalability also increased. As the number of nodes increases to high the performance of target detection draw back due to traffic implosion and geographical overlapping.  SPIN and DD protocols suffer very badly due to multiple copies of data is delivered. LEACH and HLTS both have limited traffic implosion but both affect from geographical overlapping. HLTS performance degrades by 10% whereas SPIN and DD suffer by 30%.

Figure 9 shows the target speed vs. probability of target detection with 100m transmission range and number of nodes 100. When target are static the probability of target detection is almost 90% for all four protocols. As the target speed increases the target detection probability decreases. SPIN and DD has 40% of target detection probability due to lots of multiple path generated due to crossing of target to various nodes. HLTS also suffer with the same problem but it store sensed information at node, parent node and grandparent node only. Thus it performance degrade slowly to 60% at target speed 40m/sec.

5.6 Error Rate 

Error rate are measure against the target speed in fig.e 10. As the target speed increases the error rate also increases for all the algorithms.  When target are less mobile the error rate i.e. target not detected or wrongly  detected  or misplaced is 5% but when speed of target is 50 km/hour the error rate increase to 30%. At target speed 20m/s, average error rate for HLTS is only 5%, LEACH 8%, DD 10% and SPIN 18%.  But as speed increased to 35m/s, average error rate for HLTS is only 10%, LEACH 30%, DD 33% and SPIN 45%.  SPIN suffer badly due to excessive traffic implosion as target move with high speed.

 

Fig. 7 Transmission Range vs. Probability of Target Detection

Fig. 8 Number of Sensor Nodes vs. Probability of Target Detection

Fig. 9 Target speed vs. Probability of Target Detection

Fig. 10 Target Speed vs. Average Error Rate

6. Conclusions


Simulation result proved that proposed HLTS scheme improved network lifetime by 20%, target detection probability by 25%, and reduces error rate by 20%, energy efficiency, fault tolerance, and routing efficiency over the SPIN, DD and LEACH protocols. In future other hierarchical data structures like cube, hypercube, extended cube can also be studied for the target tracking. To study the profile-based or objective-based approach which is a intelligent heuristics to track a node/ sensor depending on its predefined objective and profile at the time of installation. The work can also be extended to study other challenges of WSN such as Hardware constraints, production cost and operating environment

Acknowledgements 


We thank vice chancellor and director SOCIS of Indira Gandhi National Open University, New Delhi for always encouraging for the best. 

References


[1]     Heinzelman, W.R., Chandrakasan, A. and Balakrishan, H. : “ Energy Efficient Communication Protocol for                   Wireless Microsensor Networks”, Proceedings of the International Conference on System Sciences- 2000, pp.              3005-3014

[2]     Haas, Z.J.; Halpern, J.Y.; Li, L.: Gossip-Based Ad Hoc Routing, In Proceedings of the 19th Conference of the                  IEEE Communications Society (INFOCOM), New York, NY, USA, 23–27 June 2002; pp. 1707–1716.

[3]     Younis, O. and Fahmy, S. “HEED: A Hybrid Efficient, Distributed Clustering Approach for Ad-hoc Sensor                      Networks”, IEEE Transactions on Mobile Computing, Vol.3, Issues. 4, Oct. 2004, pp. 366-379

[4]     Kulik, J.; Heinzelman, W.R.; Balakrishnan, H.:  Negotiation based protocols for disseminating information in             wireless sensor networks,  Wirel. Netw. 2002, 8, 169–185.

[5]     Intanagonwiwat, C.; Govindan, R.; Estrin, D.; Heidemann, J. Directed diffusion for wireless sensor networking.            IEEE/ACM Trans. Netw. 2003, 11, 2–16.

[6]     Heinzelman, W.R.; Chandrakasan, A.; Balakrishnan, H.: Energy-Efficient Communication Protocol for                          Wireless Microsensor Networks,  In Proceedings of the 33rd Annual Hawaii International Conference on                      System Sciences, Maui, HI, USA, 4–7 January 2000; pp. 10–19.

[7]     Meng, Jin-Tao, Jian-Rui Yuan, Sheng-Zhong Feng, and Yan-Jie Wei. “An Energy Efficient       Clustering                       Scheme for  Data Aggregation in Wireless Sensor Networks.” Journal of Computer     Science and Technology               28, no. 3 (2013): 564-573.

[8]     Tharini, C., Vanaja Ranjan, P.: An Energy Efficient Spatial Correlation Based Data Gathering Algorithm for                    Wireless Sensor Networks. International Journal of Distributed and Parallel Systems 2(3), 16–24 (2011)

[9]     Ian F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE                              Communications Magazine, volume 40, Issue 8, pp.102-114, Aug. 2004

[10]   K. Akkaya and M. Younis, “A Survey of Routing Protocols in Wireless Sensor           Networks, ” in the Elsevier               Ad Hoc Network Journal, Vol 3/3, pp.325-349, 2005.

[11]   S. Gupta, N. Jain, and P. Sinha, “Energy Efficient Clustering Protocol for Minimizing Cluster Size and Inter                   Cluster Communication in Heterogeneous Wireless Sensor Network,” Int. J. Adv. Res. Comput. Commun. Eng.,           vol. 2, no. 8, 2013, pp. 3295–3305.

[12]   K. Khedo, R. Doomun and S. Aucharuz, “READA: Re- dundancy Elimination for Accurate Data Aggregation in             Wireless Sensor Networks,” Wireless Sensor Network, Vol. 2, No. 4, 2010, pp. 302-308.

[13]   XuanTung Hoang and Younghee Lee “An Efficient Scheme for Reducing Overhead in Data-Centric Storage                   Sensor Networks” IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, 2009 pp. 234-240.

[14]   Feng Wang, Student Member, IEEE, and Jiangchuan Liu, Senior Member, IEEE “Networked Wireless Sensor             Data Collection:Issues, Challenges, and Approaches” IEEE COMMUNICATIONS SURVEYS & TUTORIALS,                 VOL. 13, NO. 4, 2011 pp. 308-315.

[15]   Demigha, O., Hidouci, W.K., Ahmed, T., 2012. On energy efficiency in collaborative target tracking in wireless             sensor network: a review. IEEE Commun. Surv. Tutor., 99:1-13. [doi:10.1109/SURV.2012.042512.00030]

[16]   Chen, J.M., Cao, K.J., Li, K.Y., Sun, Y.X., 2011. Distributed sensor activation algorithm for target tracking with              binary sensor networks. Clust. Comput., 14(1):55-64.  [doi:10.1007/s10586-009-0092-0]

[17]   Demigha, O., Hidouci, W.K., Ahmed, T., 2012. On energy efficiency in collaborative target tracking in wireless             sensor network: a review. IEEE Commun. Surv. Tutor., 99:1-13. [doi:10.1109/SURV.2012.042512.00030]

[18]   Jie Li; Xiucai Ye; Li Xu “Collecting all data continuously in wireless sensor networks with a mobile base                          station” IJCSE, InderScience  2015 Vol. 11 No. 3 pp. 239-248 [DOI: 10.1504/IJCSE.2015.072645.]

[19]   Asgarali Bouyer; Abdolreza Hatamlou; Mohammad Masdari “A new approach for decreasing energy in wireless           sensor networks with hybrid LEACH protocol and fuzzy C-means algorithm” Int. J. of Communication                           Networks and Distributed Systems, InderScience 2015 Vol.14, No.4, pp.400 – 412 [DOI:                                                     http://dx.doi.org/10.1504/IJCNDS.2015.069675%5D

[20]   W. S. Zhang and G. H. Cao. “DCTC: Dynamic Convoy Tree-Based Collaboration for Target Tracking in Sensor              Networks,” IEEE Transactions on Wireless Communications, Vol. 3, No. 5, September 2004, pp. 1689-1701.

[21]   C.-Y. Lin, W. -S. Peng and Y.-C. Tseng, “Efficient In  Network Moving Object Tracking in Wireless Sensor                      Networks,” IEEE Transactions on Mobile Computing, Vol. 5, No. 8, August 2006, pp. 1044-1056

[22]   Chen, J.M., Cao, K.J., Li, K.Y., Sun, Y.X., 2011. Distributed sensor activation algorithm for target tracking with            binary sensor networks. Clust. Comput., 14(1):55-64. [doi:10.1007/s10586-009-0092-0]

[23]   Fayyaz, M., 2011. Classification of object tracking techniques in wireless sensor networks. Wirel. Sens.                            Network, 3(4):121-124. [doi:10.4236/wsn.2011.34014]

[24]   Karakaya, M., Qi, H.R., 2011. Distributed target localization using a progressive certainty map in visual sensor              networks. Ad Hoc Networks, 9(4):576-590. [doi:10.1016/j.adhoc.2010.08.006]

[25]   Li, Z.N., Li, H.B., Zhang, F., Chen, J.M., Ling, Q., Fu, Y.F., Tian, Z., 2011. Localized sensor management for                    multi-target tracking in wireless sensor networks.Inf. Fus., 12(3):194-201. [doi:10.1016/j.inffus. 2011.01.003]

[26]   Zhang, X., 2011. Adaptive control and reconfiguration of mobile wireless sensor networks for dynamic multi-                target tracking. IEEE Trans. Autom. Control, 56(10):2429-2444. [doi:10.1109/TAC.2011.2163862]

Authors


Sanjay Pahuja received M.E. degree at Panjab University, Chandigarh, India. He Received his Bachelor’s degree from Rajasthan University, Jaipur, India. He is currently working as Lecturer in Government Women Polytechnic College, Kota under the technical education Rajasthan, India. His area of interest is MANET’s and WSN.

Tarun Shrimali received his PhD from Rajasthan Vidhyapeet Udaipur, India. He received master degree from the same university. He is currently working as principal at Sunrise Group of institution, Udaipur. His area of interest is Networking, Data analyst and algorithm design.

%d bloggers like this: