ON-SITE TRACKING IN WIRELESS SENSOR NETWORKS by Baljeet Singh Malhotra B.Tech National Institute of Technology, Jalandhar India, 1999 THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in MATHEMATICAL, COMPUTER AND PHYSICAL SCIENCES (COMPUTER SCIENCE) THE UNIVERSITY OF NORTHERN BRITISH COLUMBIA April 2005 ©Baljeet Singh Malhotra, 2005 1^1 Library and Archives Canada Bibliothèque et Archives Canada Published Heritage Branch Direction du Patrimoine de l'édition 395 W ellington Street Ottawa ON K 1A 0N 4 Canada 395, rue W ellington Ottawa ON K 1A 0N 4 Canada Your file Votre référence ISBN: 0-494-04636-8 Our file Notre référence ISBN: 0-494-04636-8 NOTICE: The author has granted a non­ exclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distribute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. AVIS: L'auteur a accordé une licence non exclusive permettant à la Bibliothèque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par télécommunication ou par l'Internet, prêter, distribuer et vendre des thèses partout dans le monde, à des fins commerciales ou autres, sur support microforme, papier, électronique et/ou autres formats. The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. L'auteur conserve la propriété du droit d'auteur et des droits moraux qui protège cette thèse. Ni la thèse ni des extraits substantiels de celle-ci ne doivent être imprimés ou autrement reproduits sans son autorisation. In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis. Conformément à la loi canadienne sur la protection de la vie privée, quelques formulaires secondaires ont été enlevés de cette thèse. While these forms may be included in the document page count, their removal does not represent any loss of content from the thesis. Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant. Canada DEDICATED TO MY FATHER "DADYJr. 11 Abstract Tracking is one of the oldest practices that has evolved along with the advancement of technology. A similar practice, called hunting has been in existence since time immemorial. The primary objective in tracking is to find the whereabouts of a moving target. This target could be a human, or an animal, or a vehicle, etc. The task of tracking a moving target may have different objectives. Based on how these objectives are achieved, we classify the tracking problem into two broad categories: On-site tracking and Off-site tracking. The basic difference between these two approaches is the need for the physical presence of a mobile sink in the region of interest to track the target. This thesis mainly deals with the On-site tracking problem in the context of wireless sensor networks. First, we characterize the On-site tracking problem for a single target case, and propose an ant-based approach to solve the problem. Then, we generalize the problem for the multiple targets case, and extend our ant-based approach to solve the generalized problem. Next, we present the design of OSTSim, a simulation software. We devel­ oped this simulator for the performance study of the algorithms that could solve the On-site tracking problem in sensor networks. In addition to the basic ant-based algorithms, we proposed two efficient algorithms to solve the On-site tracking problem in sensor networks. Theoretical bounds for the tracking time and the number of messages generated by the sensor nodes have been derived for our algorithms. An extensive simulation study has been conducted, and the results show that our algorithms are efficient. Ill C ontents 1 2 A b s tra c t................................................................................................................ iv C ontents................................................................................................................ iv List of Figures...................................................................................................... ix List of T a b le s ...................................................................................................... x Publications from this th e sis.............................................................................. xi Acknowledgments................................................................................................ xii Introduction 1 1.1 B ackground................................................................................................. 1 1.2 Wireless Sensor Networks 2 ........................................................................ 1.2.1 A rchitecture................................................... 2 1.2.2 C h aracteristics............................................................................... 3 1.2.3 Applications..................................................................................... 5 1.2.4 Issues and Challenges..................................................................... 6 1.3 Contribution................................................................................................. 7 1.4 Thesis Organization..................................................................................... 8 Tracking 9 2.1 Introduction ...................... 9 2.2 A Taxonomy of the Tracking P roblem s.................................................. 10 2.3 Tracking A pproaches............................... 13 2.3.1 GPS Based Tracking ................... 2.3.2 Sensor Networks Based Tracking IV ................................................ 13 14 3 4 5 2.4 M o tiv a tio n ......................................... 14 2.5 Related W ork............................................................................................ 15 O n-site Tracking in W ireless Sensor Networks 17 3.1 System Model and Problem S ta te m e n t................................................... 17 3.2 A G eneralization............................................................................... 19 3.3 Generic Solutions for the On-site T ra c k in g ........................................... 20 OSTSim: O n-site Tracking Sim ulator 23 4.1 Introduction............................................................................................... 23 4.2 Problem S ta tem e n t................................................................................... 24 4.3 Use-Case Diagram ................................................................................... 24 4.4 System Specification................................................................................ 25 4.5 Entity Relationship (ER) Diagram ....................................................... 27 4.6 Class D iagram ............................................................................................ 27 4.6.1 Identification of O b je c ts ............................................................... 29 4.6.2 Abstraction of C la s s e s .................................................................. 29 4.6.3 Identification of Associations......................................................... 31 4.6.4 Interaction D ia g r a m ...................................................................... 33 4.6.5 Refinement of Classes...................................................................... 33 4.7 Activity Diagrams ................................................................................... 36 4.8 Im plem entation......................................................................................... 37 4.9 Conclusion........................... 37 Ant-Baaed On-site Tracking 38 5.1 Introduction............................................................................................... 38 5.2 Basic Idea 38 5.3 Detailed D e sc rip tio n .......................................... 39 5.3.1 Reporting the Initial P o s itio n ...................................................... 39 5.3.2 Initiation of T racking..................................................................... 39 .............. 5.3.3 T racking........................................................ 39 5.4 Theoretical A n a ly s is ................................................................................. 5.4.1 Terminology..................................................... 41 41 5.4.2 An Upper Bound on the Tracking T im e...................................... 41 5.4.3 An Upper Bound on the Number of Messages Generated by the Sensor N o d e s ........................................................ ........................ 44 5.5 Simulation S t u d y ....................................................................................... 47 5.5.1 Experimental S e tu p ........................................................................ 47 5.5.2 Results Analysis ........................................................................... 47 Conclusion................................................................................... . 53 5.6 Generalization of the Ant-based A p p ro a c h ............................................. 54 Reporting the Initial Positionsof the M T s ................................ 54 5.6.2 Initiation of Trackings by the M UT m ......................................... 54 5.6.3 Tracking the Individual Targets by the M U T s ......................... 55 5.7 Simulation S t u d y ........................................................................................ 56 5.5.3 5.6.1 5.7.1 Simulation Experiments and Results Analysis . ..................... 56 5.8 Conclusion.................................................................................................... 66 6 A daptive O n-site Tracking 67 6.1 Introduction............................... ................................................................. 67 6.1.1 Basic I d e a ........................................................................................ 68 6.2 Detailed D escrip tion .................................................................................. 69 6.2.1 Terminology ......................................................... 69 6.2.2 Tracking S trategy .................................. 70 6.2.3 Maintaining the Latest Information about theM T .................. 70 6.3 Theoretical Analysis ........................................................ 6.3.1 Terminology............................................... 6.3.2 An Upper Bound on the Tracking Time VI 74 74 ............................. 75 6.3.3 6.4 6.5 An Upper Bound on the Number of Messages Generated by the Sensor N o d e s ................................................................................. 77 Simulation S t u d y ...................................................................................... 79 6.4.1 ExperimentalS etu p......................................................................... 79 6.4.2 Results Analysis 80 ........................................................................... Conclusion...................................................................... 7 C onclusion and Future D irections 89 90 7.1 Conclusion................................................................................................... 90 7.2 Future D irections...................................................................................... 91 B ibliography 92 vu List o f Figures 1.1 An Architecture of Wireless Sensor Networks........................................ 3 2.1 A taxonomy of the tracking problem s.................................................... 12 3.1 Routing based On-site tr a c k in g ............................................................. 21 4.1 OSTSim use-case d ia g ra m ....................................................................... 25 4.2 OSTSim system setup ............................................................................. 26 4.3 OSTSim ER D iagram ................................................................................ 28 4.4 Class Digram - After first refin em en t.................................................... 32 4.5 Interaction diagram of O S T S im ............................................................. 33 4.6 Class Digram - After second refinem ent.................................................. 34 4.7 Class Digram - F i n a l ................................................................................. 35 4.8 Activity diagram of the Scheduler............................................................ 36 4.9 Activity diagram of the M T ..................................................................... 36 5.1 Ant-based On-site tracking 40 5.2 Knowledgeable area swept by MT’s p a t h .............................................. 42 5.3 Movement of MUT between two knowledgeable n o d es........................ 43 5.4 Area vs. E n erg y /N o d e............................................................................. 48 5.5 Area vs. T im e............................................................................................ 49 5.6 Speed vs. Energy/Node .......................................................................... 50 5.7 Speed vs. T i m e ......................................................................................... 51 5.8 Desired Distance vs. Energy/Node 52 ..................... vin .................. 5.9 Desired Distance vs. T im e ...................................................................... 53 5.10 On-site tracking of multiple t a r g e t s ...................................................... 55 5.11 Area vs. Number of M essages................................................................ 57 5.12 Area vs. Energy/Node ................................................................... 58 5.13 Area vs. Tracking Time ......................................................................... 59 5.14 Sink speed vs. Number of M essages...................................................... 60 5.15 Sink speed vs. Energy/N ode................................................................... 61 5.16 Sink speed vs. T i m e ............................................................................... 62 .......................................... 63 ....................................................... 64 5.19 Desired Distance vs. T im e ...................................................................... 65 6.1 Adaptive On-site tracking by M U T ...................................................... 68 6.2 Area vs. E n erg y /N o d e............................................................................ 81 6.3 Area vs. T im e ............................................................................................ 82 6.4 Area vs. T im e .................................................................. 83 6.5 Speed vs. Energy/Node ......................................................................... 84 6.6 Speed vs. T i m e ........................................................................................... 85 6.7 Speed vs. T i m e ........................................................................................... 86 6.8 Desired Distance vs. Energy/Node ......................................................... 87 6.9 Desired Distance vs. T im e ........................................................................ 88 6.10 Desired Distance vs. T im e ........................................................................ 89 5.17 Desired Distance vs. Number of Messages 5.18 Desired Distance vs. Energy/Node IX List o f Tables 4.1 Description of OSTSim classes................................................................. 30 4.2 Association among various OSTSim classes........................................... 31 X P u b lication s from th is th esis 1. Baljeet S. Malhotra and Alex A. Aravind. Energy Efficient On-Site Tracking of Mobile Target in Wireless Sensor Networks. Proceedings of International. Con­ ference on Sensors, Sensor Networks and Information Processing (ISSNIP’04), Melbourne, Australia, pp. 43-48, 14-17 Dec.2004. 2. Baljeet S. Malhotra and Alex A. Aravind. A Master-Sink Based Model for On-Site Tracking of Multiple Mobile Targets in Wireless Sensor Networks. Pro­ ceedings of International Conference on Intelligent Sensors and Information Pro­ cessing (ICISIP’05), Chennai, India. 4-7 Jan.2005. 3. Baljeet S. Malhotra and Alex A. Aravind. Path-adaptive On-Site Tracking in Wireless Sensor Networks. Submitted to the lEICE Transactions (Special Section on Parallel and Distributed Computing and Networking), 2005. 4. Baljeet S. Malhotra and Alex A. Aravind. OSTSim: Simulation Software for the On-site Tracking in Wireless Sensor Networks. Proceedings of the Western Canadian Conference on Computing Education (WCCCE’05), Prince George, BC, Canada, 5-6 May, 2005. XI A cknow ledgm ents Thanks are due to my mentor, Dr. Alex Aravind without whom I could not have finished this thesis. I am very much indebted to him for his erudite supervision throughout my research pursuits at UNBC that produced this thesis. I am also very thankful to Dr. Waqar Haque and Dr. Patrick Montgomery for serving on my graduate committee and providing me with their valuable suggestions. I extend a special thanks to Dr. Jernej Polajnar for his assistance and interest in my research work. I am very thankful to Dr. Staffen Lindgren for his interesting talk on the ants that triggered some of the initial thoughts outlined in this thesis. The work carried out in this thesis is financially supported by the Advance System Institute of BC, Canada, through the ASX graduate scholarship. Here, I would like to take this opportunity to thank Dr. Bob Tait, Dean of Graduate Studies at UNBC for encouraging me to successfully compete for the ASI scholarship, and for the Graduate Travel award and a continuing TA. One more time many thanks to Dr. Waqar Haque, Chair Computer Science program, for generously supporting my research via RA and travel grants. I am also thankful to SPEATBC for their support via a scholarship. Thanks to Rob Lucas and Paul Stokes for providing me with computer related resources. My thanks are also due to the external examiner for his/her time to read this thesis. I want to thank Dr. Rezaei, Dr. Deo, Dr. Brown, and Dr. Zahir for their general guidance and encouragement. I must thank my friends at UNBC, Sharmin, Sean, Tyler, Jey, Travis, and Jaco for engaging me in useful research discussions. A warm thanks to Dr. Mahi for her dinner invitations, and Abhinav, Pruthvi and Srinivas for giving me nice company. I will be forever thankful to my most loving brother Navjot and most loving friend Manav, who have influenced my life in so many ways. Lastly but most importantly I can not thank enough my parents and my wife without whom my existence is meaningless. Their love and support will always be a driving force behind me. X ll C hapter 1 Introduction 1.1 Background In the past few decades, advances in computer science and engineering, miniaturiza­ tion of hardware devices, and technological improvements in network and communi­ cation infrastructure have revolutionized the computing and communication environ­ ment around us. The eighties and nineties of the past century have seen the rapid growth of the world wide web that has a significant impact on our day-to-day lives. In the last one-and-a-half decades ubiquitous computing has led the way to embed tiny devices in various physical objects and places. Wide spread usage of mobile devices like lap-tops, palm-tops, PDAs, mobile phones, etc. is redefining the ways in which information is exchanged between such devices in diGerent parts of a geographical region. Integration of local and global information provided by thousands or even millions of such devices has started to make an impact on the information processing systems. Moreover, the opportunistic usage or on-demand availability of such useful information wiU change the way the world wide web works today. Mobile computing is a technology which enables people to connect their mobile computing devices to network whenever and wherever they go[l]. Today most of the wireless networks, such as cellular telephones, personal communications systems, and wireless local area networks, are supported by static infrastructure (also called 1 backbone). The infrastructure consists of fixed base stations or access points, which are connected either through wires or by long range wireless transmissions to act as gateways and bridges in the network. To cope with the demands of mobility and portability in using computers, mobile computing technologies are being enabled by rapidly emerging wireless communi­ cation systems based on radio and infrared transmission mechanisms. The history of wireless networks started in the early sixties[2] and the interest has been growing ever since. Ubiquitous access to information, anytime and anywhere, will characterize whole new kinds of information systems in the 21st century. Some of the challenges faced by these networks are the issues of mobility, energy efficiency, and security. 1.2 W ireless Sensor N etw orks Wireless sensor networks (WSN) present a promising opportunity for realizing many practical applications that will become part of our daily lives[3, 4, 5]. Small, inex­ pensive, intelligent devices equipped with processor, memory, and radio components would work together in a coordinated fashion to report the phenomena of interest happening around them. These miniature sized devices (generally referred to as sen­ sor nodes) are characterized by their limited power source and ad-hoc deployment in abundance due to cost effectiveness. Since recharging or replacing batteries for these sensor nodes is normally difficult because of various practical reasons, energy is considered as the most crucial resource in sensor networks. 1.2.1 Architecture Due to specific objectives of various applications, WSNs do not have a fixed “fit-forall” architecture. As surveyed in [6], the architecture of such WSNs would drastically differ at a node level as well as at the network level. At the node level chip size, storage capacity, and computational and communication power, are some of the important design considerations. At the network level nodes organization, and their communi- cation strategies on a collective basis would influence the architecture. However, a common desirable characteristic across all the WSNs is minimal power consumption. S e n so r N e tw o r k s G a te w a y s G a tew a y s T ransit N e tw o r k B a se S ta tio n U ser In ternet U ser Intranet Figure 1.1: An Architecture of Wireless Sensor Networks In most cases WSNs are required to be integrated with the existing wired or wireless networks. Figure 1.1 represents a typical design of the WSN architecture. In such networks observers sitting at various locations would be able to access the sensor nodes remotely. 1.2.2 Characteristics WSNs have been characterized according to several parameters like node deployment, node capabilities, applications, energy and communication constraints etc. [3, 6, 7]. Some of these general characteristics include: # Ad-ifoc Deployment Nodes are generally designed to be deployed in a random fashion. An example of such deployment is where the nodes are dropped from an airplane onto a geographical region of interest, hence creating ad hoc networks. # Dymomtc TopoZogy The network topology may change randomly and rapidly at unpredictable times. # Scalability: Due to their size and cost-effectiveness, nodes can be deployed in abundance. Nodes in hundreds or even thousands would cover a large geo­ graphical region. Their abundance would provide more accurate and up-to-date information about their physical environment. # Application Specific: It is very likely that sensor nodes are designed for specific applications. That means functionality of nodes would be highly dependent upon the type of applications for which they are designed. # Energy Constraints: In most cases, sensor nodes in a network rely on a limited supply of energy from the batteries or other exhaustible means. Furthermore, energy consumption of individual sensor nodes account for the overall lifetime of the deployed network. « Bandwidth Constrained: Sensor nodes will primarily be dependent on their wire­ less radio components for communication. These components normally would have a limited bandwidth of communication channels. # Robustness: In many applications, sensor nodes will be deployed to perform in extreme conditions that are not suitable for human interactions. In such cases, physical damages and individual failure of nodes will be common. In spite of this, WSNs are expected to perform well. e Self-Reconfiguration: Due to energy constraints, ad hoc deployment, and ro­ bustness, WSNs are expected to have self-reconfiguration capabilities. Since in most of the cases sensor nodes would be stationary, the tasks of networking and self-reconfiguration would mostly depend on nodes' knowledge about their relative positions. 1.2.3 Applications A future has been envisioned in which these sensor nodes would play crucial roles around us [8]. Surveillance, tracking, and smart spaces are some of the important applications of these networks. We list some of the most popular applications next. # Military Applications: Military appUcations are one of the promising areas in which WSNs are being explored on a large scale. Such applications include tracking of moving objects, and monitoring of hostile environments. Deploy­ ment of sensor nodes in a hostile environment will reduce human injuries and other monetary costs. Nodes can be dropped from a plane over a vast geo­ graphical region to detect harmful and dangerous materials. Tracking of tanks and other vehicles in a war zone may provide the observer with better strategic decisions. ® Environmental Studies: Nodes capable of measuring variations in temperature, humidity, pressure, etc. can be very useful in environmental health monitoring systems. For example sensor nodes can be deployed for an early warning system to check the spread of forest fires. Habitat monitoring is one such application in which sensor nodes deployment have been experimented with successfully [9]. Environmental studies that involve visits to regions of harsh weather can be benefited greatly from the help of sensor nodes. Sensor nodes in such regions may be deployed to collect data over a period of time without involving human experts. This might reduce the operational costs. Also, such networks would avoid human interference with the natural habitat, which otherwise, in most cases require continuous study and hence frequent visits to the region of interest. This way WSNs tend to reduce the negative side effects of such studies, and at the same time, are capable of providing useful information about the habitants in the deployed region. # Ciwlion Applicafmna: In civilian applications, sensor nodes can be deployed to solve many urban problems like traffic congestion, vehicular parking, and security. Sensor nodes can be deployed along the busy highways for route in­ formation and traffic diversions in case of accidents. Sensor nodes can also be deployed within the vehicles to collect and exchange useful information as they cross each other while they are moving along the roads/highways. Parking management is another apphcation where sensor nodes can be used for effective parking services in busy urban places. « Industrial Applications : Tracking inventory through sensor nodes in a ware­ house is another application which has generated interest in retail and other related industries. Based on the information available with these sensor nodes, deployed in a large warehouse, inventory items can be managed efficiently. Despite the feasibility and practicality of WSNs, there are some issues and many challenges to overcome to realize these applications in the near future. We list some of these issues and challenges next. 1.2.4 Issues and Challenges ® The foremost challenge posed by WSNs is the development of energy effi­ cient sensor nodes. A major energy consumer in a sensor node is the radio component[10]. In a comparison study it is revealed that 3000 instructions can be executed for the same cost as the transmission of one bit over 100m[10]. In most cases nodes are battery operated and expected to be in deployed in a large number. In such condition changing batteries is not feasible when power is exhausted. Therefore conservation of energy posses a great challenge in these networks. • Sensor nodes are expected to be deployed in a large number in most of the applications. The unpredictable nature of deployment conditions introduces significant scalability and reliability concerns [11]. Exposure of the hardware components to their deployed environment in extreme conditions, poses a great challenge for making these sensor nodes durable and robust. e On the software front providing a high degree of efficiency to application level software, while keeping the precise control of various components at the lower level of sensor nodes, is still challenging[12] due to their deployment in a large number. However, the software development is extended to provide libraries for routing, tracking, synchronization and querying to support various applications. As the technology evolves, sensor networks must provide a unified architectural platform for existing as well as future applications. e Nodes are expected to perform multiple tasks of sensing, processing and com­ munication. Hence all these components are required to be on a single chip due to their size restrictions and energy constraints, which is one of the design issues. • In most of the WSN related simulation studies a wide variety of simulation soft­ wares is in common use, and that includes ns2[13], GloMoSim[14], Qualnet[15], Opnet[16]. Some of the challenges in using these simulation tools are discussed in Chapter 4. This thesis deals with a particular type of tracking application that we have termed On-site tracking. An outline of the organization of the thesis is presented in the following section. 1.3 C ontribution This thesis contains the following contribution. • We classify the tracking problem into two broad categories of On-site tracking and Off-Site tracking problem. • Based on our classification, we present a taxonomy of the tracking problems. • We characterize the On-site tracking problem for a single target case in the wireless sensor networks context, and propose an ant-based approach to solve the problem [17]. • We generalize the On-site tracking problem in sensor networks for the multiple target case and extend our ant-based approach to solve the problem [18]. • We propose two efficient algorithms to solve the On-site tracking problem in sensor networks[19]. • We present the design of a simulation software, which we call OSTSim[20] that we built for the performance study of the proposed algorithms. 1.4 T hesis O rganization The fundamentals of tracking and a taxonomy of the tracking problems is presented in Chapter 2. Next, in Chapter 3, we discuss On-site tracking in wireless sensor networks. In Chapter 4, the design of the OSTSim, a simulation software that we built and implemented for conducting a performance study of the methods that could solve the On-site tracking problem. The next two Chapters 5 and 6 can be read independently of Chapter 4. In Chapter 5, we present our ant-based approach to solve the On-site tracking problem. Next in Chapter 6, a path adaptive approach for On-site tracking has been discussed, and two efficient protocols have been proposed to solve the problem. Finally, in Chapter 7, we conclude the thesis while outlining some future directions to extend the work carried out in this thesis. C hapter 2 Tracking 2.1 Introduction Tracking is one the oldest practices that has evolved along with the advancement of technology. A similar practice, called hunting has been in existence since time immemorial. The very survival of a large majority of animals and other species is de­ pendent on their tracking and hunting skills. For example, ants are considered a highly sophisticated and organized species, because of their ability to track down their food sources by an effective communication mechanism with the help of pheromones[21]. The adaptability to learn and invent new techniques for tracking with the help of sensing capabilities, power, and speed has proved to be very useful for many species, including humans. In ancient times humans used various techniques, like identiGcation of foot prints, to track down animals for hunting purposes. In the modem world, tracking techniques are used to locate the objects of interest. Sniffing capabilities of dogs are utilized to locate harmful and dangerous materials. Sophisticated scientific equipment can be seen in use at airports, public places, buildings etc., for tracking people, goods, vehicles, and other objects. Today the term “tracking” is used in various contexts, e.g. tangible and intangible entities such as tracking a parcel, economic growth, messages on the Internet, animals in the forest, and so on. In this thesis, we mainly deal with the tracking of tangible 9 entities in which the primary objective is to track the whereabouts of moving objects in WSN context. Next, we present a taxonomy of the tracking problem. 2.2 A Taxonom y o f th e Tracking Problem s The tracking problem has received considerable attention from the research community[22, 23, 24, 25, 26, 27]. There are two main entities that are involved in a typical tracking problem. They are: • Target and • Tracker (Sink). A target is an entity of interest that is required to be tracked. This entity could be a living or non-living object such as human, animal, vehicle, etc. A tracker is an entity that is interested in tracking the moving target. Having said that, a tracker could be a stationary or non-stationary, living or non-living object. Examples of a tracker could be a human sitting in a fixed base station where the information about the target is being collected, or a moving vehicle that is receiving the information about the target. For generality, we often use the term sink to refer to the tracker. The task of tracking a moving target may have different objectives. One such objective could be reporting the latest position of the moving target to a sink. Upon receiving the information, appropriate actions are anticipated. Imagine the situation of a battlefield, and consider that there are unfriendly vehicles that are roaming in the region of interest that are required to be tracked. Providing information about the unfriendly vehicles to the friendly forces would help them to make better strategic decisions. In this case the objective is to just report the position or any other relevant information to the sink. The sink may utilize this information to take appropriate actions that may include alarming the friendly forces. In such cases the sink need not actually be present in the region of interest. 10 Now consider another scenario of habitat monitoring in which a team of life scien­ tists are riding in a vehicle (mobile sink) to track an animal to provide it with medical treatment. Here the vehicle has to actually move around in the region of interest to track the animal. Several approaches can be applied to provide the scientists with the latest information on the moving animal. In this case, a sink has to be physically present in the region of interest where the target is located. We have seen two examples of tracking in which the moving target is being tracked; but each has a different objective. The basic difference in these two approaches is the need for the actual presence of a sink in the region of interest. Based on this observation, we classify the tracking problem into two broad categories. # On-Site Tracking: In which a sink is eventually required to be present in the vicinity of the target, and e Off-Site Tracking: In which a sink is not required to be present in the vicinity of the target. Based on the awareness of the target and the sink, i.e. their knowledge about each other, we can further classify the tracking problem. There are four possibilities that can be considered here. Cl: The sink is aware of the target, andthe target is unaware of the sink. C2: The sink is unaware of the target,and thetarget is aware of the sink. C3: Both are aware of each other. C4: Both are unaware of each other. A taxonomy based on the above classifications is presented in Figure. 2.1. Some of the combinations presented in the taxonomy have interesting applications and some of them do not. For example: 11 Awaie S it Unaware S it Aware SM Uniwarc Taiget Aware Target Aware Target cr C2’ C3' ' Aware S it Unaware S it Unaware Target Aware Target Unaware SiÉ Unaware Target C4’ Ci" cz Aware S it Unaware S it Aware Target Unaware Target C3' C4" Figure 2.1: A taxonomy of the tracking problems # Class C l’ has several interesting applications such as tracking of vehicles, hu­ mans, etc. Ant-based On-site tracking presented in this thesis is an example of this class. • Class C3’ is a more challenging problem than C l’. In this class, a target is aware that it is being tracked, and hence it may devise an escape strategy, which makes the tracking harder. The pursuer-evader problem[27] is an example of this class. e Class C l” has several interesting applications such as the tracking of vehicles, humans, etc. in which a moving target is unaware of being tracked. In such applications information can be collected at a base station and appropriate actions can be initiated subsequently. m Again, class C3” is more challenging than C l” as in this case a target is aware of being tracked. For example, intruding activities at a border of a country where intruder might be aware that he or she is being monitored. ® To the best of our knowledge, we are not aware of any interesting applications for other classes C2’, C4\ C2”, and C4”. Based on specific applications a sink can assume various roles such as pursuer, tracker, observer, etc. In the next section we discuss some of the popular tracking 12 approaches. 2.3 Tracking Approaches 2.3.1 GPS Based Tracking The majority of today’s tracking applications are based on Global Positioning Systems (GPS). With the advancement of technology it has become more viable and affordable, but GPS has its limitations. Some of the major constraints are the high costs and bulkiness of GPS receivers, and its non-usability in most indoor environments. The other key factor involved is the accuracy. The effects of the position accuracy in a GPS based tracking system as mentioned in [28] are: # Clock Errors: Both the satellite and the receiver require very precise clocks to function properly. In that, the receiver’s clock is typically a weak link due to cost considerations. « Atmospheric Errors: Satellite signals travel over 20,000km, including a trip through the Earth’s ionosphere and troposphere, and in both these regions charged particles distort the signal. In particular, for northern users such as Canadians, this error becomes greater due to the longer signal path through these latitudes. # MwAipof/i .Bmors: These result when the satellite signal is rejected oE a nearby object, like a person, a building, a roof, trees, dense foliage, a mountain, etc. Unless the GPS device has a clear sky view, i.e. unobstructed in all directions and a minimum of 4 satellites in view, multipath errors are very likely. # Receiver Noise: This depends on the quality of the electronics employed in the GPS unit and translates into the cost of the unit. Consumer GPS units are lower cost and higher noise devices. 13 e Relativistic Corrections: Both of Einstein’s theories of general relativity and special relativity must be incorporated into the software/firmware built into the receivers. Expert physicists have questioned the correctness of the soft­ ware/firmware. Errors in the subtle relativistic corrections lead to errors of tens of meters or larger in positional accuracy. 2.3.2 Sensor Networks Based Tracking Recently, sensor networks have emerged as an alternative to the GPS based tracking systems due to their accuracy and versatility in sensing a variety of physical phenom­ ena. Also, sensor network based tracking provides a viable option for other types of tracking where GPS based tracking may not be applicable such as indoor tracking. Sensor networks are typically designed to monitor phenomena of interest happen­ ing around them. This task can be achieved as sensor nodes sense these phenomena, collect the data, and report to the observer at desired times. One of the fundamental utilizations of this collected data is that it can be used to track the moving targets. Since sensor networks are also equipped with radio components, they can spread the information about the target as soon as they detect its presence. We discuss in detail WSN based tracking in Ghapter 5. 2.4 M otivation As emphasized before, conserving energy is one of the main objectives of any sensor network application. Applying traditional routing based solutions to solve the tracking problem is generally costly. Moreover, the mobility of the sink introduces additional communication and computational overheads to keep track of its location in the network[29]. Recently, mobility has been explored in sensor networks for energy eÆcient data collection[30, 31, 32]. Physical mobile entities such as humans, robots, vehicles, and animals equipped with specialized sensor nodes may move around in the sensor field to collect the data by direct interactions with the sensor nodes. This 14 effectively reduces the communication costs. Consider the On-site tracking of a moving target (C l’ in Figure 2.1). In this particular class of application the mobility of the sink may be dependent on the mobility of the target. Recall our previous example of habitat monitoring in which a team of life scientists are riding in a vehicle to track an animal. Here the vehicle has to follow the movement of the animal to track it. The vehicle can be equipped with a powerful sensor node (making it a mobile sink) to collect the data from the sensor nodes along the track of the animal, instead of these nodes continuously routing the information to the moving sink. We believe that, this mobility dependency between the sink and the target can be effectively exploited to reduce the communication overheads. 2.5 R elated Work The tracking problem in general has been addressed in many previous attempts and various solutions have been proposed[22, 23, 24, 25]. In [22], a clustering based approach is proposed in which sensor nodes perform the task of sensing, predicting and communicating, and then they repeat these tasks as required by the cluster heads. In another approach[23], sensors detect the presence of a target for a threshold value. Nodes broadcast an alert message when this threshold value is reached and three similar messages have been received from their neighbor nodes. A trajectory of moving target is estimated as nodes alert their neighbor nodes while broadcasting these messages. In [26], a data centric approach called directed diffusion is presented in which named data is used to diffuse the interest in the network. Data returns on multiple paths of gradient setup. Enforcing the return data to use the most optimum path is one of the key features of this approach. In [29], the authors present a grid based approach to address the problem of continuous delivery of data from the source to the mobile sinks. Recently mobility for data collection has been explored in sensor networks[30, 31, 15 32] for energy efficient data gathering. In [30], a University bus shuttle is being used as a mobile observer for data collection from the nodes deployed in the region of interest. An approach, which exploits the mobile nodes present in the sensor region as data forwarding agent is presented in [31]. Software based mobile agents have been proposed to solve the tracking problem in [24]. Our approach is different from [22, 23, 24, 25] in the way the sink communicates with the sensor nodes. In all of these approaches, the communication is based on multi-hop routing in contrast to the single-hop approach in which the mobile sink directly communicates with the sensor nodes. The primary objective of [30, 31, 32] is to exploit the mobility for data collection in sensor networks; but our focus is to utilize the mobility dependency for tracking the moving target. In this thesis we propose a set of algorithms that can be used to solve the On-site tracking problem. These algorithms include ant based-tracking and adaptive On-site tracking methods that are presented in chapters 5 and 6 respectively. Before we present these algorithms, we formally characterize the On-site tracking problem in the next chapter. 16 C hapter 3 O n-site Tracking in W ireless Sensor N etw orks In this chapter, we formally characterize the On-site tracking problem in the wireless sensor networks context. In order to do this, next we present the system model and the problem statement. 3.1 S ystem M odel and Problem S tatem en t We consider the sensor network system as a quadruple S = < N R , SN , MUT, M T >, where # WÆ represents the network region, m g N is a set of stationary sensor nodes deployed in WA, # MI/T is the mobile unit for tracking the moving target, and # MT is the mobile target. We make the following assumptions. Assum ption 3.1 The neftuort WA w connected. Thot w, a sensor node in N R can communicate to any other sensor node in N R . 17 Assum ption 3.2 6'enaor nodes ore soifobfy depZo^ed Zo cofer JVA. TAoZ is, et;ery point in N R is in the sensing range of at least one sensor node. A ssum ption 3.3 Each sensor node is aware of its position and has limited energy, memory, and computing power. A ssum ption 3.4 The M U T is not constrained by energy, memory, and computing power. Assum ption 3.5 The speed of the M U T is greater than the speed of the M T. A particular target may be tracked in many time periods, each time for a particular mission. For example, a wounded animal might require continuous monitoring and treatment until its wound heals. The same animal might be tracked in a later time period for a different purpose that might require less frequent observations. Based on this observation we introduce the concepts of tracking mission and mission period. Definition 3.1 A tracking m ission is the task of tracking a particular mobile tar­ get, and the duration in which the target is to be tracked is called its mission period. Next we characterize the On-site tracking problem in sensor networks. To for­ malize the problem, we introduce the concepts of desired distance and frequency of closeness as follows. Definition 3.2 The desired distance Ô is defined as a threshold value of distance between a moving target (say M T ) and a tracking sink (say M U T), required to initiate some actions at a particular time during the mission period, if necessary. Definition 3.3 The frequency of closeness f between the target M T and its the tmcting aint MC/T ia denned oa (Ae number o/ t:mea MT ond M i[/T ore udtAin ZAe desired distance S, during the mission period. 18 The value of desired distance, S, is application specific and normally much smaller than the diameter of the tracking region. Similarly, the frequency of closeness f is also application specific. Some applications might require one time closeness to the target, and others might require closeness for a finite number of times or may remain closer to the target during the entire mission. Different tracking missions of a same mobile target may have different values of S and f . Definition 3.4 If the tracking of a moving target achieves the frequency of closeness, f , then we say that it is On-site tracking. The problem is to devise a method to achieve the On-site tracking for a single target. We present the algorithms to solve the On-site tracking problem of class C l’ (shown in Figure 2.1) in Chapter 5 and 6. 3.2 A G eneralization On-site tracking of multiple targets by multiple sinks require coordination among the sinks, mainly to determine which sink tracks which target. Next we present the modified system model for the multiple targets case. We consider the sensor network system as a quadruple S = < f/TZ, SM, M U T , M T >, where: # represents the network region, # SJsf is a set of n stationary sensor nodes deployed in the target region, ® M U T is a set of I mobile units (sinks) for tracking the moving targets. The tracking units are labeled as M UT\, MUT 2 , ..., MUTi, and # A fT is a set of m moving targets that is to be tracked. The moving targets are labeled as MTg,..., 19 All of the assumptions except Assumption 3.5 considered in the single target case are assumed to hold for the multiple targets case. We substitute Assumption 3.5 with the following assumption. Assum ption 3.6 The speed of any mobile target (MTi) is less than the speed of any mobile tracking unit (MUTj). Next we characterize the On-site tracking problem for multiple targets case by restating the definitions of the desired distance and the frequency of closeness. Definition 3.5 The desired distance ôÿ is defined as a threshold value of distance between a mobile target (say M Ti) its corresponding tracking sink (say MUTj), required to initiate some actions at a particular time during the mission period, if necessary. Definition 3.6 The frequency of closeness fÿ between any target MTi oud its corresponding tracking sink MUTj is defined as the number of times MTi and MUTj are within the desired distance 5ij, during the mission period. Definition 3.7 I f the tracking of a M Ti by a M U Tj, \/i,j, achieves the frequency of closeness fij then we say that it is On-site tracking. The problem is to devise a method to achieve the On-site tracking of multiple mobile targets. We present the algorithms to solve the C l’ class (shown in Figure 2.1) of this problem in Chapter 5. For simplicity, in this thesis we assume that the network region is a two dimensional plane with no obstacles in it, and the number of sinks is greater than or equal to the number of targets (i.e, I > m). 3.3 G eneric Solutions for th e O n-site Tracking On-site tracking can be solved by many existing general tracking methods. However, due to their generality these methods can be costly. In this section, we sketch some of these methods that will be used later as references for a comparative analysis. 20 The way the nodes and the sink communicate about the target, and how the sink makes a move to track the target based on the obtained information are the two factors that significantly affect the performance of the On-site tracking methods. The simplest approach to solve the On-site tracking problem would be continuously flooding the network with the target information. Another approach is to use an optimized routing method in which the messages travel to many intermediate nodes for every update. Such an approach is presented in [29]. LMT 0 0 0 A i 0 •-'A ° OiMUli 0 o - - - O o 0 0 0 0 ° ____________ ^ 0 , mut O ' -- ^ 0 \0 0 .../ ° ° .......o . # : o ' « T > ...... o '" C Track of MT ^ ............. 0 \c-' i O -- i-- O 0 0 ° T ' ' MUT ; ^ 0 0 0 0 0 ( mut A o 0 0 0 0 ([MT^ Mobile Target InformationFlow Çm U T) Mobile Sink Figure 3.1: Routing based On-site tracking The nodes surrounding the MT initiate the routing and then by multiple hopping the information about the M T reaches the mobile sink. Continuous reporting about the target is required by the nodes as the sink continuously changes position. A situation is depicted in Fig. 3.1. The arrows from the trace line toward M U T refer to a continuous communication between the mobile sink, M U T, and the sensor nodes. Depending on the information obtained, the M U T changes its direction to reach the mobile target, M T. Maintenance of some logical structure, like a grid[29] is normally required to effec­ tively keep track of the location of the sink as well as the target. This complicates the solution and it is costly because mobile sink requires a continuous update from the 21 sensor nodes to effectively keep track of the target in the network region. Previously discussed approaches (flooding and grid based) for the On-site tracking normally re­ quire multiple hopping of messages, which might waste a considerable amount of energy, and subsequently that would reduce the life time of the network. The objective in this thesis is to explore the solutions for the On-site tracking problem th at can effectively exploit the mobility dependency inherent in the problem. Before we discuss about these solutions in Chapters 5 and 6, in Chapter 4 we present OSTSim, a simulation software that we built for the performance study of the methods discussed in this thesis. However, Chapters 5, 6 and 7 can be read independently of Chapter 4. 22 C hapter 4 OSTSim : O n-site Tracking Sim ulator 4.1 Introduction This chapter presents the architecture of a simulation software, which we call OSTSim. We developed OSTSim to evaluate the performance of the algorithms that can solve the On-site tracking problem. As mentioned in Chapter 1, there are many public domain softwares available to conduct the simulation studies in wireless networks. Since most of these simu­ lators were initially developed for specific studies and then modified thereafter by the contributions of other researchers in an ad-hoc fashion, they lack structure and proper documentation. Their minimal documentation, increased size, and generality normally: # make the learning curve steep, # incur huge execution time, # allow less control for certain modifications and extensions, and # lack features required for the specific studies. 23 Therefore, during our search for a simulator, we eventually chose to develop our own simulation test-bed. The major advantage we have with this decision is a better understanding of the underlying design of the software that has in fact provided us a better control over the simulator. OSTSim is limited to conducting the performance study of the On-site tracking methods in wireless sensor networks. For the On-site tracking methods, we are mainly interested in the energy spent by the sensor nodes and the tracking time of the sink. We compute the energy expenditures based on the messages sent and received by the sensor nodes. We assume that the communication network is reliable. To develop OSTSim, we systematically followed a methodology that we present next. 4.2 Problem Statem ent A sensor network with specified number of targets and sinks are assumed. For a given tracking approach for a specified set of parameters such as sink speed, desired distance, and area size, the simulator should compute the tracking time of the sink and the energy consumption of the sensor nodes. We develop the simulation system through analysis and design. The analysis phase involves making the use-case dia­ grams, gathering the system specifications, and constructing the ER diagrams. The design phase involves constructing the class diagrams. We start with the use-case diagram[33]. 4.3 U se-C ase Diagram Constructing an use-case diagram involves; (i) identification of the actors, (ii) identification of the use-cases (the ways of using the system), and (iii) refining the use-cases and setting the relationships. The researcher who is interested in evaluating the per­ formance of the algorithms, is the only actor in the system. This actor can use the system by setting the parameters of the simulator and getting the results on defined 24 metrics. Figure 4.1 represents the use-case diagram of OSTSim. Set MT Parameters Set Set Sink Parameters Parameters Researcher Collect Energy per Node Collect Statistics Collect Messages Count Figure 4.1: OSTSim use-case diagram 4.4 System Specification The sensor network consists of the following. # A geographical region of area size o. # A set of n sensor nodes with communication range r. « A set of 1 mobile sinks each with a maximum speed # A set of m mobile targets each with a maximum speed Umt and a random mobility pattern. We make the following system assumptions. 25 e The geographical region is a two-dimensional rectangular plane without obsta­ cles. # The sensor nodes are suitably deployed to cover the network region. • The targets never cross the network boundary. ® We assume the same radio model as referred in [34]. In this model Er = h^nJ/bit nJ/hit, where and E , = 50 4- .1 X is the energy required to receive one bit and E, is the energy required to send one bit at R distance. Figure 4.2 represents the setup of three main constituents of OSTSim. 0 0 0 0 (m ut) 0 0 0 0 0 u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ( mut ) 0 0 0 0 0 0 0 0 (MUT ) (E) 0 0 0 0 0 0 0 0 0 ° ® 0 0 0 0 (m ut) 0 0 0 0 0 (MUT ) 0 0 0 (M u r) Mobile Target 0 Mobile Sink 0 0 0 0 Sensor Node Figure 4.2: OSTSim system setup Following are the main activities in the system. • Sensor nodes collect and store the information of the targets. « Sensor nodes supply the information about the targets when sinks request them. ® The system (simulator) collects the statistics. • Direct Inputs: 26 - Transmission range of a sensor node, r. - Size of the network region, a. - Sink and Target speeds, nmot and «mt respectively. - Desired Distance, 5. - Mission Period, Pm- Number of simulation runs. • Derived Inputs; - The number of sensors required is computed based on the network area and the transmission range of a sensor node. - The sensor nodes are placed in such a way that they cover the region. - The initial positions of the sinks and targets are determined randomly. Based on the system specifications, next, we construct the entity relationship (ER) diagram for the system. 4.5 E n tity R elationship (E R ) D iagram The design of an ER diagram involves: (1) identification of the entities in the system, (ii) identification of the characteristics of these entities, and (iii) identification of the relationships between these entities. Figure 4.3 represents the ER Diagram of system. Next, based on the use-case diagram, the system specifications and the ER diagram, we construct the class diagram. 4.6 Class D iagram A class diagram depicts the structural aspect of the system. A class essentially has three logical components: data attributes, operations that involves services from other 27 M T Spee^ l ^ a S i z e ^ ( StnkSpeed ) C MTSpeedJ) ( ArcaSizc Statistics CoUeetcï Average ctreshRate TractangTi Scheduler Pœition Position Queries Observe(s) Position Figure 4.3: OSTSim ER Diagram classes, and operations to access the member attributes of the class. Its development involves mainly the following steps. 1. Identification of the objects and their data attributes. This can be obtained by analyzing the problem specification, the use-case diagram and the ER diagram. 2. Abstraction of the objects into the classes. 3. Identification of the relations among various objects (referred to as lints), and abstracting them into the relations between the corresponding classes (referred to as associations). This involves finding the relation, labeling it properly, and determining its cardinality. 4. Refine the class diagram to identify all the main operations using suitable interaction diagrams. 5. Further refining the class diagram to get a final class diagram. 28 4.6.1 IdentiÊcation of Objects Mainly there are three classes of objects involved in the system. 1. Objects in the simulation system. • Simulation-Interface, • Scheduler, • Statistics-Collector, • Simulation-Clock, and • Event-Queue. 2. Objects in the sensor network. • Sensor Node. 3. Objects in the On-site tracking methods. • Mobile Target, MT and • Mobile Sink, MUT. 4.6.2 Abstraction of Classes In this system, each object has its corresponding class. Description of all the classes is given in Table 4.1. 1. Simulation-Interface, 2. Scheduler, 3. Statistics-Collector, 4. Simulation-Clock, 5. Event-Queue, 29 Class SimulationInterface Scheduler StatisticsCollector Sensor-Node MT MUT Data Members (attributes) int: NofNodes, NofSimulations, NofMT, NofSink float: Length, Breadth, SensingRange, CellSize, DesiredDistance object: EventQueue, Clock, StatisticalData object: StatisticalData int: NodelD, NodexPos, NodeyPos object: TargetData int: MTTD float: MTxPos, MTyPos, MTNewxPos, MTNewyPos, MTSpeed bool: MTCaptured object: StatisticalData int: MUTID float: MUTxPos, MUTyPos, MUTNewxPos, MUTNewyPos, MUTSpeed object: StatisticalData Table 4.1: Description of OSTSim classes 6. Sensor-Node, 7. MT, and 8. MUT. Next, we identify various associations existing among these classes. 30 Simulation- Scheduler Interface SimulationInterface Scheduler Initiates (1StatisticsCollector SensorNode MT MUT 1) Supplies (1- Initiates (11) StatisticsCollector SensorNode MT MUT Initiates (1- Initiates (1- Initiates 1) n) Updates (1- Updates (1m) Initiates (1-1) Updates (1-m) (1-m) 1) (1-1) Updates - (1-1) 1) - (m-1) - — - Requests (m-m) Tracks (1-1) Reports (m-m) — Table 4.2: Association among various OSTSim classes 4.6.3 Identification of Associations Table 4.2 contains the association among the various classes. This table allows us to draw the first level class diagram representing the association among various classes, as shown in Figure 4.4. Classes in this diagram contain the main data members. The next step is to identify the operations of these classes, which invoke services from other classes. This can be achieved through building and analyzing interaction diagrams that we do in the next section. 31 MUT M TID : int xPos ; float M T ID : int xPos : float yPos : float NewxPos : float NewyPos : float M TSpeed : float StatisticalData : object MTCaptured : bool yPo5 : float NewxPos : float N ew yPos : float MUTSpeed : float StatisticalData : object U p d a te s S c h e d u le Updates .Scheduler., 1..* 1..^ Scheduler Schedule-Queue object Clock : object StatisticalData : object Updates Scheduler 1.,* Nodes 1..* TargetID : int TargetHitTime ; long TargetHit : bool NodelD ; int xPos ; int yPos : int TargetData : object 1..* 1..* I 1..* llpdateStatislics Simulationlnterface NofSimulations : int Lengdi : float Breadth : float NofNodes : int SensingRange ; float CellSize : float M TSpeed ; float StnkSpeed ; float RefreshRale ; int DesiredDistance ; float 2 ,„J?rnvideSel.up..,. 1 StatisticsCollector PrnvideSemp StatisticalData : object ...EmyideSetop.,. Pm vidcSetup Figure 4.4: Class Digram - After Grst re&nement 32 StMisticalData DiscardReason ; String DiscardData ; bool TTDDOvertiead : int MUTOveriiead ; int SPCEnergyCosts ; float TTDDEnergyCosts : float M UTEnergyCosts : float PADMTEnergyCosts ; float DistanceByTTDD : double DistanccByM UT : double DistffliceByPADMUT : double 4.6.4 Interaction Diagram Interaction diagrams illustrate the dynamic behavior of a system. That is, showing interaction among the objects. In this context, only the objects which have non­ trivial interaction are considered. Objects considered in the interaction diagram are: (1) Nodes (2) Mobile Target, MT, (3) Mobile Sink MUT, and (4) System Interface. The interactions of these objects are given in Figure 4.5. System Statistic Collector Scheduler Node MUT MoveMUT ReportMTPosition Figure 4.5: Interaction diagram of OSTSim 4.6.5 Reûnement of Classes Based on the interactions between various objects as shown in the interaction dia­ gram in Figure 4.5, we refine the classes to include the operations. After the first 33 refinement and then including the operations, the class diagram is presented in Fig­ ure 4.4. Further refinement involves carefully walking through the operations given in the class diagram as shown in the Figure 4.4 to check their completeness. This refinement is shown in Figure 4.6. Complete class diagram listing all the required operations and the member variables required to perform the system operations is given in Figure 4.7. MT MUT MTID : int xPos : float yPos : float NewxPos ; float NewyPos : float M U TSpeed: float StatisticalData ; object CollectlnitalMTPositionO MoveMUTO RequestMTPositiooO IJ lIpdatRS Schedulfir M T ID : int xPos : float yPos ; float NewxPos : float NewyPos : flo ^ M TSpeed : float StatisticalData : object M TCaptured ; bool ITpdnlfts .Scheduler I.." 1..* MoveMTQ Scheduler 1..* S chedule-Q ueue : object Clock : object StatisticalData : object —Llpdflte.-L.Schedidfir.. 1.,* CollectStatisticsO 1..* TargetData Nodes TargetID : int TargetHitTime : long TargetHit ; bool N odelD : int xPos : int yPos : int TargetData : (* jec t 1.. * 1.. * ObserverMTO ReportMTPositionO I 1..* -UpdatgStaiistics SimuMionlnterface NofSimulaticms ; int Length : float BreM th : float NofNodes ; int SensingRange : float CellSize : float M TSpeed ; float StnkSpeed ; float RefreshRale ; int DesiredDistance : float 1 .. .PmvldeSetup... StatisticsCollector _ P ro v id e.S R tu p - StatisticalData ; object , PmvidfiSefiip AggergateSiatisticsO P ro v id e S e tu p -_ InitializeNodeO InitializeSdiedularQ InitializeMUTO InitializeMTO Figure 4.6: Class Digram - After second refinement 34 1..* StatisticalData DiscardReason ; String D iscardD ata : bool TTDDOverhead ; int M UTOverhead : int SPC E nergyO jsts : float TTDDEnergyCosts : flo ^ MUTEnergyCosts : float PA DM TEnergyCœts : float DisttmceByTTDD : double DistanccByM UT : double DistanccByPADM UT ; double MT MUT___________ M TID : int xPos : float yPos ; float N ewxPos : float N ew yPos : float M U TSpeed : float StatisticalData : object MUTO CollectlnitialM TPositionO MoveMUTO RequestMTPositionQ MakeNffliKNMoveQ : void 1..* i..=> .Updates Scheduler U p d a r ü t Stcheriuter M T ID : int xPos ; float yPos : float NewxPos : float NewyPos : float MTSpeed : float StatisticalData : object MTCaptured : to o l 1..* IJ 1./ MTO MoveMTQ StartingPosition moveMTTorwanlO MoveMTBackwardQ ManipulateNodesQ SelectlDNodesO sleepForQ CheckCellMovetiKDtO ; void CheckPositionStatusQ : void Recovery RomLostPosilionO Q iooseNewPositionO : void sleepForO : void U pdateSchedularO ; void Scheduler 1..* S chedule-Q ueue : object C lock : object StatisticalData ; object .llpdatas-Stiieduler.,- L.* SchedulerQ CollectStatisticsO : CollectlnputParamt tereO : void 1..* ProvideStatislicsO M TEncounteredO : MTCapturedStatus 3 : void TargetData Nodes TargetID : int TargetHitTime ; long TargetHit : bool NodelD : int xPos : int yPos : int TargetData : object MoveMTQ : void M oveMUTO : void IncrementClockQ ; void 1..* TargetDataO : void [71* NodeQ ObserverMTO : void ReportMTPositionO : void i 1..* . I!pdatflStat,istics Simulationlnterface NofSimulations : int Length ; float Breadth : float NofNodes ; int SensingRange : float CellSize : float M TSpeed : float SinkSpeed ; float R efreshR ^e ; int DesiredDistance : float 1..* PrnvidfiSeiup, StatisticsCollector Pm videS eiup, StatisticalData : object -EDayidsSgbip... AggregateStalisticsQ : void CollectMUTStidisticsO : void CollectNodeStatisticsO : void CollectM TStatisticsO : void -ProYidsSgup.... SimuIationtaterfaceO ProvideInitiaiSetup(Objea) GetValuesO;void ReadFromPileO^void WritelntoFileQivoid mainO:void StatisticalData DiscardReason : String DiscardData ; bool TTDDOverhead ; int MUTOverhead : int SPCDiergyCosts : float TTDDEnwgyCosts : float MUTEnergyCosts : float PADMTEnergyCosts : float DistanceByTTDD : double DistanceByM UT : double DistanceByPADM UT ; double StatisticalDataO Figure 4.7: Class Digram - Final 35 4.7 A ctiv ity Diagram s Finally, we identify and expand the key functions of the system in terms of the activity diagrams. Next, we draw the activity diagrams for the following; # Scheduler (Figure 4.8), and ® Mobility of MT (Figure 4.9). Figure 4.8: Activity diagram of the Scheduler to new position Update System Figure 4.9: Activity diagram of the MT 36 4.8 Im plem entation We used Java 2 (SDK, SE v l.4.2.03) to develop OSTSim. We effectively utilized the Java thread programming to build this model. It was a fruitful learning experience on concurrent programming. 4.9 C onclusion In this Chapter we elaborated the steps that we followed to develop our simulation test bed OSTSim. It is used to evaluate the performance of the algorithms discussed in the next two Chapters 5 and 6. 37 C hapter 5 A nt-B ased O n-site Tracking 5.1 Introduction This chapter presents an ant-based method that exploits the mobility dependency between the M T and the M U T to solve the On-site tracking problem. Ant-based approaches have been adapted to solve the routing problems in computer networks and mobile ad hoc networks[35, 36]. 5.2 B asic Idea To solve the On-site tracking problem, the derives its tracking strategy based on the behavior of ants. While locating food, an ant leaves a trail of a substance called pAeromones for other ants to follow and End the food source [21]. The direction of the path to the food source is guided by the intensity of pheromones. In our system a M U T inherits this ant behavior to track the moving target M T. Each node stores information about the target with a time stamp. M U T collects and uses these time stamps hom the stationary sensor nodes, along the track of the MT, to compute the direction of its velocity vector. 38 5.3 D etailed D escription Our On-site tracking method consists of three logical steps: (1) Reporting the initial position of the M T , (2) Initiation of tracking, and (3) Tracking. We will explain these three steps in detail next. 5.3.1 Reporting the Initial Position A sensor node, say s, which observes the M T first, reports this information to the M U T to initiate the tracking, and also inhibits other sensor nodes from redundant reporting. To achieve this, s sends a message about the M T to the entire network, and hence, to the M U T. The nodes that encounter the M T and have already received this message will only record the information about the M T, and not report to the network. It is possible that more than one node could observe the M T and report simultaneously; but eventually the nodes will stop the redundant reporting. For our later references, we call the nodes which encounter the M T as the knowl­ edgeable nodes. For example s becomes the first knowledgeable node in the network. 5.3.2 Initiation of Tracking Once the M U T receives the information about the M T, it has to visit a knowledgeable node &om where it can start tracking the MT. To achieve this M f/T moves towards the hrst tnowfedgeoWe node. On the way if it encounters another tnowfedgeoWe node then it starts tracking the M T from that position. 5.3.3 Tracking The main objective of the ant-based tracking is to avoid the huge communication costs incurred by the sensor nodes due to frequently updating the M U T with the location of the M T. This requires intelligent decision-making on the part of the M UT. An ant uses the pheromones to locate the food source whereas M U T uses the 39 information collected from the knowledgeable nodes to reach the M T. Data available at the knowledgeable nodes is the useful information about the M T with an associated timestamp. The value of this timestamp is the latest time at which that node has encountered the M T. M U T computes its direction of velocity vector based on the timestamps collected from the knowledgeable nodes. The order between the timestamps of two knowledge­ able nodes sets the direction for the M UT. If the collected timestamps are equal, then the M U T randomly chooses one of the knowledgeable nodes and move towards that node. There it collects data from the neighbors of the chosen knowledgeable node. If it finds data with a larger timestamp, then it moves in that direction. Otherwise, it retreats back to one of the unchosen knowledgeable nodes and repeats the process until it finds a knowledgeable node with a larger timestamp. By Assumption 3.2, the M U T will eventually find such a knowledgeable node, and then proceed in its direction. m ut; Track of Moving Target Mobile Target Information Flow Mobile Sink Figure 5.1: Ant-based On-site tracking A typical scenario of ant-based On-site tracking is depicted in Figure 5.1. The dotted smooth rectangles around the M [/T and the MT refer to their past positions, and the solid smooth rectangles indicate their current positions. The solid line across the diagonal region indicates the track of the M T. First, the initial position of the 40 M T is reported to the M UT. Then, M U T moves towards the M T ’s reported position and follows the track of the M T as shown in the Figure 5.1. 5.4 T heoretical A nalysis 6.4.1 Terminology We introduce the following parameters for our analysis. • r - transmission range of the sensor nodes and the M UT. • do - diameter of the network region N R . That is, the distance between the farthest points in the network. • a - area of N R. • n = IS'A^I - the number of stationary nodes in N R . • d - distance traveled by the M T, from its initial position, before it is tracked. • Vmt - velocity of the M T. • Vmut - velocity of the MUT. • ( - tracking time. • - total number of messages generated by the sensor nodes during the tracking time, t. 5.4.2 An Upper Bound on the Tracking Time Based on the parameters outlined in subsection (5.4.1), we derive an upper bound on the tracking time, t. D efinition 5.1 The nodes that are within the transmission range of a node, say uq, are called the neighbors of 41 Theorem 5.1 Ant-based On-site tracking approach assures that the tracking time, Proof: To cover the maximum distance, assume that the M T travels in a straight line and does not repeat its path as shown in Figure 5.2. It is easy to infer from Figure 5.2 that the maximum number of knowledgeable nodes beyond Ôdistance from the M T is: 2r{d — 6) -n (5.1) --0 *0 Figure 5.2: Knowledgeable area swept by MT’s path By Assumption 3.2, during tracking, the M U T will be either within the desired distance 5 to the M T or the M U T will have a message from at least one of the neighbor tnotuWgeaWe nodes with a higher timestamp. In the later case, if the Mf/T has only one neighbor with a higher timestamp, then the Mf7T can move to that particular neighbor and proceed thereon. Note that only the knowledgeable nodes with higher timestamp will reply. If more than one knowledgeable node have equal timestamps, then the M U T may have to visit all these knowledgeable nodes. Consider Figure 5.3, in which the MC/T’s current position is represented by the black circle in the center. The M U T might have visited this position from any of the four neighbor nodes, L, U, D, and R. Without loss of generality, we assume that the M U T has moved to its current position from L. Now to move to the next position the 42 Figure 5.3: Movement of MUT between two knowledgeable nodes M U T may get a maximum of two replies with equal timestamps from the remaining three knowledgeable nodes. That is, either from the pair U and R, or from the pair D and R. In either case, the maximum distance that the M U T should travel to visit the pair is: (5.2) This pattern of traveling r + y/2r distance to visit a pair of knowledgeable nodes, as explained through Figure 5.3, could repeat until the tracking is complete. Since we have —1 tnowledgeuAk nodes, the maximum distance that the AfUT could travel to visit all the tnowledgeoWe nodes is: (r + V2r) For brevity we use p = (5.3) By adding do, the maximum distance traveled by the M U T to reach the first knowledgeable node, into the equation (5.3), we get the total distance traveled by the M U T as follows. 43 (5.4) Since the distance traveled by the M U T in time t is, tVmut, we get the following inequality. t < ------ ^ (6. 5) '^mut By substituting d = tVmt in the equation (5.5), we obtain: ^ ^ ado + - 5)rpn - ap Finally, by solving the equation (5.6) for t, we get: t< (5.7) aVfxiut ‘^Vffi£rpn Hence the proof. Corollary 5.1 Ant-based On-site tracking approach assures that the target can be tracked in a finite time, if v^ut > 5.4.3 An Upper Bound on the Number of Messages Gener­ ated by the Sensor Nodes In this section we derive an upper bound on Theorem 5.2 On-aife fmcAing oppmocA oaaurea (Aof (Ae number o/ mea- sages generated by the sensor nodes during t, mt < do—2rn p S —ap—anp)-^ 2 mpS ap anp)fa nvmut. a{avmut -2 r n p v m t ) where p = Ant-based tracking involves two logical stages of message generation by the sensor nodes: (i) initial flooding and (ii) direct communication with the M U T during track­ ing. Let 772.3, and my, respectively, be the messages generated in these two stages. We 44 compute the upper bounds for and rriy separately and then add them to get the upper bound for mtAssume that initially there are more than one sensor node that capture the po­ sition of the M T (first knowledgeable nodes). Even if all of the first knowledgeable nodes send messages simultaneously, rest of the sensor nodes would choose only one of the first knowledgeable nodes to forward their message. Therefore, each node in the network will forward at most one message during the flooding. Hence, we get the following first equation. rux = n (5.8) During tracking, the M U T can get response from at most all the knowledgeable nodes. The number of knowledgeable nodes is ^ n , where d = tVmt- Substituting for d, we get: my < -n (5.9) By adding equations (5.8) and (5.9), we obtain the following inequality. m. < (5.10) By substituting the value for t from Theorem 5.1 in the equation (5.10), we get: ^ 2rrmMd(odo - mt < - op - onp) -t- o^nUmut n \ • - 2rnpUmf) . /r 1 1 \ (5.11 j This completes the proof. From Theorem 5.2, an upper bound on the total energy spent by the sensor nodes during tracking can be easily calculated. These upper bounds reflect the costs for worst case scenarios. Average case analysis would help to understand the normal behavior of the system. Computing the average case values for t and m* is quite complex. The complexity arises due to the variabilitiesof the parameterssuch as the 45 initial positions of the M U T and the M T (they can be at any position in the entire network), mobility pattern of the MT, the speed of the M T (may vary from 0 to Vjnt), etc. However, to see the closeness to the simulation results we derive the upper bounds for a simplified average case. T h e o rem 5.3 Assume that (i) The total number of messages generated initially n, (ii) M U T travels y to reach the first knowledgeable node, (Hi) M T travels with an average velocity of and (iv) M U T visits only half of the total number of knowledgeable nodes. Then, (d ) I < ' ■' — /L ) I / a à o -'lS rn p —2a'p 2avm iit—Vm irnp ^ rn v m t M o —2 a p (l+ 2 a n )—2Srnp]+8a^nVm.ii,t * — 2 a {2 a V m u t-T n p V m t) The proof is similar to the proofs of Theorems 5.1 and 5.2. In the next section we present our simulation study. 46 5.5 Sim ulation S tudy In the simulation, we are mainly interested in studying the performance of our antbased On-site tracking method. In addition to that, we are also interested in com­ paring it with other existing methods that can be used to solve the On-site tracking problem. Though the On-site tracking problem has been introduced in this thesis, the methods like TTDD[29] and shortest path communication (SPC) can be used to solve the problem. TTDD uses a logical grid structure for the communication. SPC is a theoretical method that uses a shortest path between two nodes for the commu­ nication with zero path-maintenance cost. In this section, we compare our ant-based approach with TTDD and SPC. 5.5.1 Experimental Setup The parameters for the simulation are set as follows. 1. Speed of the moving target is fixed as Im /s. 2. Speed of the moving sinks varies from 5m /s to 15m/s. 3. a, square area, varies from 100m x 100m to 2000m x 2000m. 4. Transmission range r is computed as (1/10)*^ of the side of the square region. 5. Desired distance, varies from 5m to 30m, and frequency of closeness, / , is fixed as 1. 5.5.2 Results Analysis Simulation results are mainly collected for three performance metrics: (i) average number of messages generated by the nodes, (ii) average energy consumption per node, and (iii) average time taken for tracking the MT. We investigate these three metrics by, (1) varying the size of the area, (2) varying the speed of the Sink or MUT, and (3) varying the desired distance, S. Results obtained for each value of 47 these varying parameters are an average of 100 simulation runs. For the comparison purposes in the graphs, we refer our ant-based approach as M UT. E x p erim en t 1 {Area vs. Energy used per sensor node): In this experiment, we are interested in computing the average amount of energy spent by the sensor nodes for message communication. Sensor nodes spend energy for both sending and receiving the messages as mentioned previously. Therefore, we first calculate the number of messages sent and received by the sensor nodes in the entire network, and then compute the average energy spent per sensor node. The results are summarized in graphs as shown in Figure 5.4. No.of nodes = 200. MUT/Sink speed = 10m/s, Update rate = 7. Desired Distance = 20m 50 SPC TTDD — MUT - •» 45 40 Î z s I 35 30 10 5 0 0 500 1000 Lengtti of the square field (m) 1500 2000 Figure 6.4: Area vs. Energy/Node Observation 1: The average energy consumption per node is quite small in the case of and it increases slightly as the area increases. On the other hand, the energy consumption in C and TTDD increases rapidly as we increase the area size. We note that for an area size of 2000 x 2000 the average energy consumption per node for SPC, TTDD and MDT are 43.618 /^Joules/bit, 19.045 //Joules/bit and 0.63 /IJoules/bit respectively. This shows that M U T is highly energy efficient. 48 Experim ent 2 (v4reo w. TViacting Time): In this experiment, we are interested in comparing the average time taken for tracking the M T in our method with that of TTDD. The results are summarized in graphs as shown in Figure 5.5. No.of nodes = 200. MUT/Sink speed = lOtn/s. Update rate = 7. Desired Distance = 20m 500 TTDD MUT - 450 400 350 I 300 g 250 1 H 200 150 100 0 500 1000 Length of the square field (m) 1500 2000 Figure 5.5: Area vs. Time O bserv atio n 2: The average tracking time in the case of TTDD increases steeply with the increase in area, and so is the case with M U T but with a random behavior. This is because M U T normally travels a larger distance than TTDD while trying to achieve the desired distance. Note: We conducted the study by hxing the value of r and increasing the number of nodes when area increases. We observed a similar behavior. In the next two experiments, we consider the varying speed of the sink. In these experiments we consider the network area to be a square of size 2000 x 2000 with 200 nodes in it. The maximum speed of the moving target is fixed at 3 m/s, though, we allowed the M T to have a random movement. 49 E x p e rim e n t 3 {Sink speed vs. Energy used per sensor node): In this experiment, we are interested in finding how sink’s speed affects the energy consumption by the nodes. The results are summarized in graphs as shown in Figure 5.6. Area = 2000m x 2000m. No.of nodes = 200. Refresh rate = 7. Desired Distance = 20m 90 SPG — TTDD —*■ MLtT a 80 70 60 I 50 1 40 30 20 10 0 4 6 10 8 12 14 Sink speed (m/s) Figure 5.6: Speed vs. Energy/Node Observation 3: As we vary the speed of the sinks from 5 m /s to 15 m/s, we observe that message generation reduced in the case of SPC. As the sink’s speed increases it is expected to track the target faster. There is a slight decrease in the case of TTDD, but MUT’s average number of messages remains almost constant. In terms of energy consumption, there is a decrease in energy consumption per node in SPC and TTDD, but it remains almost constant in the case of M[/T. In 100 simulation runs with the sink speed of 10 m/s, the average energy consumption per node in SPC, TTDD and MI/T, respectively, are 40.489 pJoules/bit, 19.406 pJoules/bit, and 0.345 /iJoules/bit. 50 E x p e rim e n t 4 {Sink speed vs. Tracking Time): In this experiment, we vary the sink’s speed to observe its affect on the tracking time. The results are summarized in graphs as shown in Figure 5.7. Area = 2000m x 2000m. No.of nodes = 200. Refresh rate = 7. Desired Distance = 20m 600 TTDD MUT -- 500 400 E a 300 I 200 100 4 6 8 10 12 14 Sink speed (mfs) Figure 5.7: Speed vs. Time Observation 4 The average tracking time in the case of TTDD decreases sharply with the increase in speed as it is obvious that the sink with more speed will be able to track the target faster. In the case of M UT, though, the average tracking time is quite random and is comparatively higher than that of TTDD as expected, but it also decreases as MC/T’s speed increases. Next, we evaluate the performance by taking third parameter which is desired distance, In this experiment we vary J while keeping the speed of sinks and the network area hxed. In the network area of 2000 x 2000 with 200 nodes in it, we vary S from 10m to 50m while keeping sink speed fixed at 10 m/s. 51 E x p e rim e n t 5 {Desired Distance vs. Energy used per sensor node): In this experiment, we evaluate MC/T’s performance in terms of energy consumption. As we vary 5, we observe its impact on the average energy consumption by nodes. The results are summarized in graphs as shown in Figure 5.8. Area = 2000m x 2000m. No.of nodes = 200. MUT/Sink speed = lOm/s. Refresh rate = 7 MUT e Desired Distance (m) Figure 5.8: Desired Distance vs. Energy/Node Observation 5: There are small variations in energy consumption in the case of MUT. However, it is quite efficient than SPC and TTDD that can be deduced from Figure 5.8. Like other experiments we ran 100 simulations for the varying parameter, which is S in this experiment. We observe that the average energy consumption per node in SPC, TTDD and MUT is 40.196 /iJoules/bit, 18.549 pjoules/bit and 0.219 pJoules/bit respectively for a 6 value of 20m. 52 E x p e rim e n t 6 (Desired Distance vs. Tracking Time): In this experiment, we are interested in observing the average tracking time of M U T against the varying value of S. The results are summarized in graphs as shown in Figure 5.9. Area = 2000m x 2000m. No.of nodes = 200. MUT/Sink speed = lOm/s. Refresh rate = 7 TTDD MUT —©■ I 15 20 Desired Distance (m) Figure 5.9: Desired Distance vs. Time O bservation 6: Like previous experiments for the average tracking time of M UT, in this experiment also, M U T's average tracking time is random and higher than that of TTDD. However, it gradually decreases as the value of 5 increases. This is expected, because M U T has to capture the target from a large distance instead of following it closely. 5.5.3 Conclusion From the simulation results, it is easy to see that energy consumption in our antbased approach is quite less than that of TTDD based approach. On the other hand tracking time in our approach is higher than that of TTDD. In the next section we generalize the ant-based approach to solve the On-site tracking problem for the multiple targets case. 53 5.6 G eneralization o f th e A nt-based Approach On-site tracking of multiple targets by multiple sinks requires coordination among all the sinks, mainly to determine which sink tracks which target. For such coordination, we introduce a master sink called M U T m - A s described previously in the single target case, our On-site tracking method consists of three logical steps. Here, we modify those three steps to generalize the ant-based approach for the multiple targets case. These three modified steps are: (1) Reporting the initial position of each target MTi, to the master M U T m , (2) Initiation of trackings by the M U T m , and (3) Tracking the individual targets by the M U T s. Next we explain these three steps in detail. 5.6.1 Reporting the Initial Positions of the MTs The initial reporting is based on the demand of the master M U Tm - A sensor node, say s, which observes the M T i first (at a time equal or greater than the time specified by the M U T m ) reports this information to the master M U T m to initiate tracking and also inhibits other sensor nodes from redundant reporting. To achieve this, s sends a message about the M T i to the entire network and hence to the M U Tm - The nodes which encounter the MTi and have already received the reporting message will only record the information about the MTi and do not report again to the network. It is possible that more than one node could observe the MTi and report simultaneously; but eventually the nodes will stop the redundant reporting. In this case for all i (i.e. 1 to m), each MTi will have a set of knowledgeable nodes. It is quite possible that one particular node is a knowledgeable node for more than one MTi. 5.6.2 Once the Initiation of Trackings by the MI/TM receives the information about all the MTî from the sensor nodes, it allocates each M U T j with the mission to track a particular MTj. The M U T m makes this decision based on the reported positions of the first knowledgeable nodes 54 corresponding to all the MTs and the starting positions of all the M U T s. 5.6.3 Tracking the Individual Targets by the M(7Ts Once the M U T j has been assigned to track the M T i , it has to reach a knowledgeable node corresponding to the MTi, and from there it can start tracking the MT,. To achieve this, the M U T j move towards the first knowledgeable node corresponding to the MTi. On the way if it encounters another knowledgeable node of the MTj, then it starts tracking the MTi from that position. ^ 0 o Track of Moving Target Ü Information How Mobile Target Mobile Sink Figure 5.10: On-site tracking of multiple targets Tracking a target from its first node is similar to the single target case as discussed in the Section 5.3.2. That is, the MC/T, computes its direction of velocity vector based on the timestamps collected from the knowledgeable nodes. The order between the timestamps of two knowledgeable nodes sets the direction for the M U Tj. If the collected timestamps are equal then the M U T j randomly chooses one of the knowledgeable nodes and move towards that node. There it collects data from the neighbors of the chosen knowledgeable node. If it finds data with a larger timestamp, then it moves in that direction. Otherwise it retreats back to one of the unchosen knowledgeable nodes and repeats the process until it finds a knowledgeable 55 node with a larger timestamp. By assumption 3.2, M U T j will eventually find such a knowledgeable node and then proceed in that direction. By assumption 3.6, the M U T j will reach the MT* in a finite time and thereon it can be within the desired distance, if necessary. A typical scenario of ant-based On-site tracking of multiple targets is depicted in Figure 5.10. The dotted smooth rectangles around the M U T and the M T refer to their past positions, and the solid smooth rectangles indicate their current positions. The solid line across the diagonal region indicates the track of the M T . 5.7 Sim ulation S tudy In the simulation, we are mainly interested in studying the performance of ant-based On-site tracking method for the multiple targets case. In addition to that, we also compared it with the TTDD [29], and SPC as discussed previously. The experimental setup is same as given in the Section 5.5.1. In addition to that setup, in the following experiments we consider the simplistic case of five M U T s and five M T s. 5.7.1 Simulation Experiments and Results Analysis Again simulation results are mainly collected for three performance metrics: (i) average number of messages generated by the nodes, (ii) average energy consumption per node, and (iii) average time taken for tracking the MT. We investigate these three metrics by, (1) varying the size of the area, (2) varying the speed of the Sink or M[/T and (3) varying the desired distance, 6. Results obtained for each value of these varying parameters are an average of 100 simulation runs. Next, we discuss our experiments. 56 E x p e rim e n t 7 {Area vs. Number of messages generated by nodes) : In this exper­ iment, we are interested in calculating the average number of messages generated by the sensor nodes for various sizes of the network area. The results are summarized in graphs as shown in Figure 5.11. No.of nodes = 200, MUT/Sink speed = lOm/s, Refresh rate = 7, Desired Distance = 20m 5000 SPC —XTTDD —»■ MUT —e 4500 4000 I 3500 3000 i 2500 I« 2000 Ia 1500 I •5 1000 d z 500 1000 1200 1400 1600 Length of the square field (m) 1800 2000 Figure 5.11: Area vs. Number of Messages O bservation 7: The message generation in SPC increases rapidly as the area in­ creases. There is a slight increase in TTDD, but M U T has the lowest communication overhead and remains almost constant as the size of the area increases. 57 E x p e rim en t 8 {Area vs. Energy used per sensor node): In this experiment, we compute the amount of energy spent by the nodes for message communication. The results are summarized in the graphs as shown in the Figure 5.12. No.of nodes = 200, No.of MUT/MT = 5, MUT/Sink speed = lOm/s, Refresh rafe = 7, Desired Distance = 20m SPC TTDD —* 100 mut e f I I e I 1000 1200 1400 1600 Length of the square fieid (m) 1800 2000 Figure 5.12: Area vs. Energy/Node Observation 8: The energy consumptions for both S P C and T T D D increases sharply as the area increases. In contrast to that, the energy consumption is quite less in the case of M U T, and it increases slightly as the area increases. We note that for an area size of 2000 x 2000 m^, average energy consumption per node for SPC, TTDD and are 60.489 pjoules/bit, 86.311 /fJouIes/bit and 2.548 pjoules/bit respectively, which shows that M U T is highly energy efficient. 58 E x p e rim e n t 9 (Area vs. Tracking Time): In this experiment we compare the average tracking time in our method with the average tracking time in TTDD. The results are summarized in graphs as shown in Figure 5.13. No.of nodes = 200, No.of MUT/MT = 5, MUT/Sink speed = 10m/s, Refresh rale = 7, Desired Distance = 20m 1600 TTDD MUT —s- 1000 1200 1400 1600 Length of the square fieid (m) 1800 2000 Figure 5.13: Area vs. Tracking Time O bservation 9: The average tracking time in the case of TTDD increases with the increase in area and so is the case with M U T but with a random behavior. This is because M U T normally travels a larger distance than TTDD while trying to achieve the desired distance. In the next three experiments we consider the varying speed of the sinks. 59 E x p e rim e n t 10 (Sink speed vs. Number of messages generated by nodes): In this experiment we compute the number of messages transmitted by nodes for a varying value of sink’s speed as specified previously. The results are summarized in graphs as shown in Figure 5.14. Area = 2000m x 2000m, No.of nodes = 200, Refresh rate = 7, Desired Distance = 20m SPC TTDD fVlUT 6000 I » I 5000 8 .g- I I 5, 4000 3000 2000 o z 1000 6 10 8 12 14 Sink speed (m/s) Figure 5.14: Sink speed vs. Number of Messages O bservation 10: As shown in Figure 5.14, the sink’s speed does not greatly affect the message generation in the case of M UT. There is slight decrease in the case of TTDD and a sharp decrease in the case of SPC. Overall M U T has the least communication overhead. 60 E x p erim en t 11 {Sink speed vs. Energy used per sensor node): In this experiment, we are interested in finding how sink’s speed affects the energy consumption in nodes. The results are summarized in graphs as shown in Figure 5.15. Area = 2000m x 2000m, No.of nodes = 200, Refresh rate = 7, Desired Distance = 20m SPC — TTDD —*■ MUT e 140 120 "o' 8 i f i5 6 10 8 12 14 Sink speed (m/s) Figure 5.15: Sink speed vs. Energy/Node O bservation 11 : As we vary the speed of the sinks from 5 m /s to 15 m/s, we observe that average energy consumption decreases quite rapidly in the case of SPC. On the other hand in the case of TTDD and M UT, it remains almost constant. For 100 simulation runs, we observe that the average energy consumption in SPC, TTDD and M [/T is 39.453 pJoules/bit, 83.03 pJoules/bit, and 5.575 /^Joules/bit respectively for the sink speed of 10 m/s. 61 E x p e rim e n t 12 {Sink speed vs. Tracking Time)-. In this experiment we vary the sink’s speed to observe its affect on the tracking time. The results are summarized in graphs as shown in Figure 5.16. Area = 2000m x 2000m, No.of nodes = 200, Refresh rate = 7, Desired Distance = 20m 4500 Û TTDD MUT —* 2000 8 10 12 Sink speed (m/s) Figure 5.16; Sink speed vs. Time Observation 12: The average tracking time in the case of TTDD decreases as the sink’s speed increases. In the case of M U T the tracking time decreases as well, but it is comparatively higher than that of TTDD as expected. It is interesting to note that an increased sink’s speed improves the tracking time much faster in both the cases of TTDD and M UT. On the other hand increased sink’s speed has lesser impact on the energy consumptions in both the cases of TTDD and Aff/T. In next three experiments we evaluate the performance by varying the value of 62 E x p e rim e n t 13 {Desired Distance vs. Number of messages generated by nodes): In this experiment we vary 5 and observe its impact on the message generation by the nodes. The results are summarized in graphs as shown in Figure 5.17. Area = 2000m x 2000m, No.of nodes = 200, MUT/Sink speed = lOm/s, Refresh rate = 7 SPC — TTDD — MUT —e 5000 I ! 4000 I 3000 & s 2000 ? I o z 1000 20 25 30 Desired Distance (m) 35 40 Figure 5.17: Desired Distance vs. Number of Messages O bservation 13: There are variations in the number of messages generated in all the three cases of SPC, TTDD and M UT. But overall message generation by the nodes in the case of M U T is much less as compared to SPC and TTDD. 63 E x p e rim e n t 14 {Desired Distance vs. Energy used per sensor node): In this experiment we vary 6 to observe its impact on the average energy consumption in nodes. The results are summarized in graphs as shown in Figure 5.18. Area = 2000m x 2000m, No.of nodes = 200, MUT/Sink speed = 10m/s, Refresh rate = 7 120 SPC — TTDD — MUT —®' 100 "œ g i I 10 20 25 30 Desired Distance (m) 35 40 Figure 5.18: Desired Distance vs. Energy/Node Observation 14: There are small variations in energy consumption in the case of M U T, but it is quite efficient than SPC and TTDD as shown in Figure 5.18. We observe that the average energy consumption per node in SPC, TTDD and M U T is 57.089 yuJoules/bit, 86.845 pJoules/bit and 2.036 pJoules/bit respectively for a S value of 20m. 64 E x p e rim e n t 15 {Desired Distance vs. Tracking Time): In this experiment ob­ serve the tracking time of M U T against the varying value of 5. Results are summa­ rized in graphs as shown in Figure 5.19. Area = 2000m x 2000m, No.of nodes = 200, MUT/Sink speed = lOm/s, Refresh rate = 7 3000 TTDD — MUT — A, 2500 S I? I A 2000 - 1500 - V V" - V" •A 1000 - 500 20 25 30 Desired Distance (m) 35 40 Figure 5.19: Desired Distance vs. Time Observation 15: Like previous experiments for the tracking time of the M UT, in this experiment also M U T ’s average tracking time is random and higher than that of TTDD, but it gradually decreases as the value of S increases. This is expected as MUTs have to capture their target from a large distance instead of following it closely. It is interesting to note that in the experiments for the tracking time, Mf/T's tracking time is quite random as compared to the TTDD based approach. The reason is that M U T follows the track of the M T. Since the M T is allowed to have a random movement, and therefore M T 's traced path highly influence the tracking time of the 65 5.8 C onclusion In this chapter, we proposed an ant-based approach to solve the On-site tracking problem for a single target case, and then we generalized the ant-based approach to solve the problem for the multiple targets case. In our simulation results, it is shown that energy expenditures of the sensor nodes in our approach is quite less than that of the TTDD and SPG based approaches. However, in our approach the M U T takes a longer time to track the target as compared to the TTDD based approach. The next step in our research was focused on reducing the tracking time of the MUT, which we discuss in the next chapter. 66 C hapter 6 A d ap tive O n-site Tracking 6.1 Introduction The basic solution proposed in Chapter 5 to solve the On-site tracking problem is shown to be energy efficient. In that approach, sensor nodes simply store the infor­ mation about the target with a timestamp. The M U T visits these sensor nodes and collects these timestamps to compute a direction towards the moving target. Since the velocity of the M U T is assumed to be greater than that of the target; the M U T would eventually capture the target. This approach reduces the communication over­ head tremendously, but has the hmitation of increased tracking time. The reason for the increased tracking time is that target by visiting a large number of follows the track of the nodes along the track of the target. Consider the case in which the initial position of the target has been reported to the sink. By the time the sink reaches the reported position, the target may have moved to another position in the network region. Even though the sink would move faster than the target, the sink would have to visit a maximum number of sensor nodes to collect the timestamps, and compute the direction of its velocity vector. That would increase the tracking time significantly. We believe that the tracking time can be reduced, if the information possessed by the sensor nodes is the latest. Consider the case in which the initial position of 67 the target has been reported to the M UT. Now, by the time the M U T moves to the reported position, the target may have moved to a new position; but the sensor node at the initial position would report the latest position of the target, and hence the M U T would be able to track the target faster by moving directly to the reported position. Updating the M U T with the latest information can be achieved by routing the latest information of the target along the track. 6.1.1 Basic Idea The main objective of the adaptive On-site tracking is to reduce the tracking time in the basic approach proposed in Chapter 5, while conserving the energy of the sensor nodes. This can be achieved by a strategy of supplying the latest information about the M T when the M U T visits a knowledgeable node in the network. Using the latest information, the MUT can move directly towards the latest position as reported by the sensor nodes bypassing the intermediate knowledgeable nodes. This way the M U T ’s tracking time is reduced as it does not visit all the knowledgeable nodes along the track of the M T. The energy efficiency of the sensor nodes depends on the information maintenance strategy. o I mut r MUT O' \l MUT, •G - Track of MT T MT Track of adaptive MOT mut MUT Figure 6.1; Adaptive On-site tracking by MUT 68 A typical scenario of adaptive On-site tracking is depicted in Figure 6.1. The dotted smooth rectangles around the MUT and the MT refer to their past positions, and the solid smooth rectangles indicate their current positions. The solid line across the diagonal region indicates the trace of the MT. First, the initial position of the MT is reported to the MUT. Then, the MUT moves towards the M T ’s initial position and adaptively follows the track of the MT as shown in the Figure 6.1. 6.2 D etailed D escription The algorithms presented here for the adaptive On-site tracking consists of three logical steps; 1. Reporting the initial position of the MT, 2. Maintaining the latest information about the MT in the knowledgeable nodes along the M T ’s track, and 3. Deciding the MUT’s tracking strategy using the latest information collected dur­ ing the previous step. Initial reporting remains same as described for the ant based algorithm given in Chapter 5. The main contribution in this approach is in steps 2 and 3. 6.2.1 Terminology We introduce some terminology that will be used to describe the adaptive On-site tracking approach. DeAnition 6.1 A latest knowledgeable node is o sensor node hos mos^ recently o6ser«ed tAe MT. It is quite possible th at there could be more than one latest knowledgeable node in the network at any instance of time during the tracking. 69 D efinition 6.2 Let the M U T ask a knowledgeable node, say A, for the latest infor­ mation about the M T . If A has that information then it will supply the information immediately. Otherwise, it will initiate a request message for the latest information in the network, obtain the information, and then supply this to the M U T. Here, we call A the guide, and the knowledgeable node that supplied the latest information about the M T the re p o rte r. A latest knowledgeable node can assume the role of reporter that will be explained in the next section. With this terminology, first we explain MC/T’s tracking strategy. 6.2.2 Tracking Strategy The reporters might change as the guides change over the time. In our adaptive On-site tracking, the first knowledgeable node that M U T visits is the first guide. Then, it performs the following tasks repeatedly until it encounters the M T within the distance, Ô. 1. It asks the guide for the latest information about the M T supplied by the reporter. 2. Then the M U T travels straight to the reporter. 3. The reporter becomes the guide. This way the MC/T visits only the ^rat tnotuIedgeoAIe node and the reporters. This brings us to the question of maintaining the latest information about the MT in the network. 6.2.3 Maintaining the Latest Information about the MT Updating the AnotoIedgeoWe nodes along the track of the MT can be achieved in number of ways. We list two of them next. 1. Self Updated Path: The sensor nodes continuously update the path. 70 2. On-demand Updated Path: The sensor nodes update the path only when the MUT demands. In the first approach, the MUT is lazy in its nature, and it assumes that knowl­ edgeable nodes along the path of the MT would always be updated in advance before the MUT visits them to get the information of the latest knowledgeable node. Hence, we named it as (L)azy (AD)aptive (M)obilt (U)nit for (T)racking {LADMUT). In the second approach, the MUT pro-actively asks the sensor nodes to build a path for the messages to travel and get the latest information of the MT. (PA)th is updated on (D)emand by the (M)obile (U)nit for (T)racking, and hence named as PADMUT. This approach is simple modification of the first approach; but it is more energy efficient. Self U pdated Path Approach (LADMUT) In this approach, the MUT achieves the task of tracking as each node in the network does the following. ® Whenever a node encounters the MT it stores the information about the MT (along with the timestamp) and becomes the latest knowledgeable node. Then it sends its observation to its neighbors. • If a node is a knowledgeable node and it receives the information about the MT from its neighbor, then it does the following. If the received timestamp is larger than its own timestamp, then update the information about the lofesf tnowZ- edgeable node and forward this new information to its neighbors. Otherwise ignore the message. In summary, the value of the timestamp possessed by a particular knowledgeable nodes at any given point of time is the latest time at which that particular tnowf- edgeable node or the latest knowledgeable node has encountered the MT. Any other knowledgeable node receiving information from two different knowledgeable nodes may 71 choose either of them to store and forward the information of the selected knowledge­ able node. This way all the knowledgeable nodes in the network would have the latest information about the M T. An O ptim ization of LA D M U T In LAD M U T, the communication flow between the latest knowledgeable node and the rest of the knowledgeable nodes is continued until the M U T reaches the M T within the 5 distance. This would unnecessarily cost more energy. Instead, if the flow of information between two reporters on the track of the M T is stopped once M U T has reached the later reporter; it would save the energy of the knowledgeable nodes. To achieve this, the reporters that have already been visited by the M U T could simply stop forwarding the information to their neighbors. That is, the M U T initiates the stoppage of message flow incrementally as it visits the reporters along the path of the M T. On-Demand U pdated Path Approach (P A D M U T) In this approach, the M U T demands the latest information when it visits the knowl­ edgeable nodes. This way, the information about the latest position is routed only when needed and that would save considerable amount of energy. The update in­ volves subtle details. For example, when the M U T visits a knowledgeable node along the track, we do not want the request message to travel along the downstream track. Processing of the request for the latest information by the MUT involves three steps: (1) Sending an upstream request message along the track of the MT, (2) Determining the latest knowledgeable node, and (3) Forwarding a downstream reply message along the track of the M T. Next, we explain these three steps in detail. 1. Sending an upstream request m essage along the track of th e MT A guide initiates a request message to get the latest information of the M T after receiving a query message from the M UT. Initiating a request message 72 involves simply forwarding the timestamp to its neighbor knowledgeable nodes. The nodes that receive the request compare the received timestamp with their own timestamp and perform the following task. e If the received timestamp is less than its own timestamp, then forward the request message with its own timestamp. This step is repeated until the request message reaches the latest knowledge­ able node, the reporter. The timestamp of the guide assures that the request message does not travel (i.e. downstream) towards the nodes that have older timestamp than the guide. It is quite possible that there may be more than one guide during any demand; but knowledgeable nodes would respond to just one guide. 2. D eterm ining the latest knowledgeable node (reporter) A knowledgeable node would choose to become a reporter after it has received a request message, and if it has not received a timestamp greater than its own timestamp within a thresh hold value of time. Obviously, the latest knowledge­ able node would not receive such a message. However, the converse need not be true. That is, a node which does not receive such message need not be a latest knowledgeable node. For example, a knowledgeable node, say A, which is neither the latest nor has any neighbor with a higher timestamp would also not receive such a message. This problem can be solved if one of A’s neighbors could notice the problem and alert its neighbors. The problem can be noticed by a knowledgeable node if it receives an equal timestamp and a larger timestamp from its neighbors. When a knowledgeable node notices this problem, it could immediately send an alert message to its neighbors, to Inform of the existence of correct reporters. 3. Forw arding a downstream reply m essage along th e track of th e MT. 73 After receiving the request message, the reporter sends the downstream reply message. The downstream reply message travels as follows. @If the received timestamp is greater than its own timestamp and has par­ ticipated in the upstream request, then forward the reply message with its own timestamp. This process avoids forwarding the redundant messages and also assures that the reply message does not travel beyond the guide. 6.3 T heoretical A nalysis 6.3.1 Terminology We introduce the following parameters for our analysis. • r - transmission range of the sensor nodes and the M UT. • do - diameter of the network region N R . That is, the distance between the farthest points in the network. • a - area of N R . • n = |5'IV| - the number of stationary nodes in WÆ e d - distance traveled by MT, from its initial position, before it is tracked. « Urn* - velocity of the MT. • - velocity of the MC/T. • t - tracking time. • rrit- total number of messages generated by the sensor nodes during the tracking time, t. 74 • k - the maximum number of reporters that the MUT would visit (number of reportings) to achieve the desired distance. 6.3.2 An Upper Bound on the Tracking Time Based on the above parameters, we derive an upper bound on the tracking time, t, for On-demand updated path approach. First we derive an upper bound for k. Lemma 6.1 On-demand updated path approach for the On-site tracking assures that the maximum number of reportings in which MUT can reach within the desired dis­ tance of the MT, k < [log„^(<5/do)l, where Vr = Proof: We consider the worst case scenario that the MT always travels in a straight line between two consecutive reporters. Let dj represent the distance between the i^ and (i + 1)*^ reporters. The distance traveled by the MT between the first and second reporter can be computed as follows. di = d o f - ^ | (6.1) V ‘^ m u t ) Similarly the distance between the second and the third reporter is: 4 = * ( — ) = * (— )' V j (6.2) V '^m ut ) In general, we have: d, = d „ ( ^ ) ' V '^m ut ) 75 (6.3) reporter, the M U T must be within the Ôdistance from the After reaching the M T . Therefore we have: dk Vmt- 6.3.3 An Upper Bound on the Number of Messages Gener­ ated by the Sensor Nodes In this section we derive an upper bound on for the On-demand updated path approach for On-site tracking. T h eo rem 6.2 On-demand updated path approach for the On-site tracking assures that the number of messages generated by the nodes during t, mt < where % = Vmut On-demand updated path approach for tracking involves three logical stages of message generation by sensor nodes: (i) initial Êooding, (ii) sending the upstream query message by the reporting tnowIedgeoAIe nodes on the demand of the MUT, and (iii) sending the downstream reply message initiated by the latest knowledgeable nodes. Let my, and respectively, be the messages generated in these three stages. We compute the upper bounds for mx, my, and m^ separately and then add them to get the upper bound for m*. The value of m , is given in the equation (5.8). Total number of upstream query messages generated by the knowledgeable nodes would be the total number of tnowZedgeoWe nodes between the guide and the reporter during any request by the M UT. Therefore the total number of upstream query 77 ^ messages generated during any reporting (for i = 1, 2...k) gives us the following inequality. Similarly, is: mz < « (6.12) An upper bound on the total number of messages generated by the senor nodes during the tracking time, t, can be computed by adding all the upstream query messages, downstream reply messages during all the reportings along with the total number of messages generated during the flooding phase. From equations (6.10), (6.11) and (6.12) we have; mt < n + 2 ^ i~l ” ^ (6.13) ^ By substituting the value of YlLi ^ &om equation (6.7) into equation (6.13), and then by simplifying it, we have: _ ^ o » ( l - «r) + 4rndo(l - n /)u r ^ This completes the proof. From Theorem 6.2, an upper bound on the total energy spent by the sensor nodes during tracking can be easily calculated. These upper bounds reflect the costs for worst case scenarios. Average case analysis would help to understand the normal behavior of the system. As discussed previously, computing the average case values for tracking is quite complex. The complexity arises due to the variabilities of the parameters such as the initial positions of the M U T and the M T (they can be any at position in the entire network), mobility pattern of M T, speed of the M T (may vary from 0 to Vmt), etc. However, to see the closeness to the simulation results, we 78 compute a simplified average case values for t and next. T h eo rem 6.3 Assume that (i) M U T travels ^ to reach the first knowledgeable node, (ii) M T travels with an average velocity of and Then, / j , ^ d o ( l —Vr'‘ )Vr+{