UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The construction of a lifetime-preserving tree for data aggregation in wireless sensor networks Lee, Wi Nan Marc 2004

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2005-0069.pdf [ 5.84MB ]
Metadata
JSON: 831-1.0065301.json
JSON-LD: 831-1.0065301-ld.json
RDF/XML (Pretty): 831-1.0065301-rdf.xml
RDF/JSON: 831-1.0065301-rdf.json
Turtle: 831-1.0065301-turtle.txt
N-Triples: 831-1.0065301-rdf-ntriples.txt
Original Record: 831-1.0065301-source.json
Full Text
831-1.0065301-fulltext.txt
Citation
831-1.0065301.ris

Full Text

THE CONSTRUCTION OF A LIFETIME-PRESERVING TREE FOR DATA AGGREGATION IN WIRELESS SENSOR NETWORKS by Wei Nan Marc Lee B.A.Sc. The University of British Columbia, 2002 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES . DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA November 2004 © Wei Nan Marc Lee, 2004 Abstract To meet the demands of wireless sensor networks (WSNs) where data are usually aggregated along its way to be collected at a single source prior to transmitting to any distant user, there is a need to establish a tree structure inside any given event region. Such a tree provides event sources with a mechanism to combine their readings, so that only a minimum amount of energy is required to deliver the same amount of information to the user when data aggregation is not used. In this thesis, we propose a novel technique to create one such tree, which preserves the lifetime of event sources while they are constantly transmitting, for data aggregation in future WSNs. We use the term Lifetime-Preserving Tree (LPT) to denote this tree. LPT features in nodes with higher energy tend to be chosen as data aggregating parents so that the time to detect the first broken tree link can be extended. In addition, by constructing the tree in such a way, the protocol is also able to reduce the frequency of tree reconstruction, which incurs an additional energy cost to all the sources. Furthermore, the protocol minimizes the amount of data lost after the network is impaired by the broken tree link. By choosing Directed Diffusion as our underlying routing platform, our simulation results have shown that the functional lifetime of event sources can be prolonged by a maximum of 139% when data are aggregated via a modified spanning tree prior to transmission to distant sinks. Our proposed LPT scheme can further extend this lifetime by a maximum of additional 13% without impairing the average latency and packet delivery ratio. When tree depth is also considered in the tree construction, our results have indicated that LPT is more likely to be centered at the event region, thereby reducing its delay when comparing to the modified spanning tree model. We expect all these differences to grow with an increasing number of event sources. ii Table of Contents Abstract " Table of Contents »> List of Figures v List of Tables viii List of Acronyms * x Acknowledgements xi Chapter 1 Introduction 1 1.1 Motivations and Objectives 3 1.2 Contributions of the Thesis 7 1.3 Structure of the Thesis 7 Chapter 2 Related Work 9 2.1 Directed Diffusion 9 2.2 Data Dissemination .'. 10 2.2.1 Low-Energy Adaptive Clustering Hierarchy (LEACH) 11 2.2.2 GRAdient Broadcast (GRAB) 13 2.2.3 Geographical and Energy Aware Routing (GEAR) 14 2.2.4 Two-Tier Data Dissemination (TTDD) 15 2.3 Data-Centric Storage and Data Funneling 16 2.4 The Impact of Timing in Data Aggregation 17 2.5 Data Aggregation Trees and Clusters 17 2.5.1 Energy-Aware Data Aggregation Tree (EADAT) 18 2.5.2 Maximum Lifetime Data Aggregation 18 2.5.3 Minimum-Cost Convoy Tree 19 2.5.4 Spanning Tree over Area-Dominating Set 20 2.5.5 Balanced Convergecast Tree 20 2.5.6 Data Aggregation Clusters .20 2.6 Node Scheduling 21 2.6.1 Adaptive Self-Configuring sEnsor Networks Topologies (ASCENT).. 22 2.6.2 Connected Sensor Cover 23 2.6.3 Sparse Topology and Energy Management (STEM) 24 2.7 Discussions and Summary 25 Chapter 3 The LPT Construction 27 3.1 Network Model, Assumptions, and Definitions 27 iii 3.2 Problem Formulation 29 3.3 The Energy-Aware Spanning Tree (E-Span) 30 3.3.1 The Spanning Tree Protocol 30 3.3.2 The Energy-Aware Spanning Tree Protocol 33 3.4 The LPT: Centralized Approach 35 3.5 The LPT: Distributed Approach 40 3.5.1 Exploring the Highest-Energy Branch from every Source to any Root 40 3.5.2 Constructing a Tree Spanning all Event Nodes for every Source 43 3.5.3 Searching a Lifetime-Preserving Tree for every Source 47 3.5.4 Implementing the LPT Algorithm in Practical WSNs 49 3.6 Discussions 53 3.7 Summary 54 Chapter 4 Simulation Results 56 4.1 Performance Metrics and Methodology 57 4.2 Tree Energy: Distributed vs. Centralized 60 4.3 Controls and Tree Depths: LPT vs. E-Span 61 4.4 Performance: LPT, E-Span, and Diff 62 4.5 Summary 71 Chapter 5 Conclusions and Future Work 72 5.1 Summary of the Thesis 72 5.2 Topics for Future Investigations 74 Bibliography 76 iv List of Figures Figure 1.1: An example to show that if the residual energy is not considered in the tree construction, it can reduce the node lifetime and the amount of information gathered by the root 4 Figure 1.2: An example to show how the number of transmission paths can affect energy efficiency 5 Figure 2.1: A simplified schematic for Directed Diffusion 10 Figure 2.2: A simplified schematic for LEACH 12 Figure 2.3: A simplified schematic for the credit-adjustable mesh forwarding 13 Figure 2.4: A simplified schematic of the two-tier data dissemination 15 Figure 3.1: An example to describe branch and tree energies 28 Figure 3.2: Problem formulation. Explore the highest-energy branch from each source to the root by first assuming that every source is a root. Then, select the one with the highest tree energy for data collection 30 Figure 3.3: The distributed spanning tree protocol, which creates a graph covering all source nodes as vertices and contains no cycles 31 Figure 3.4: An example of the spanning tree protocol 32 Figure 3.5: An example of the E-Span protocol 33 Figure 3.6: The distributed E-Span protocol, which creates a graph covering all source nodes as vertices and contains no cycles 34 Figure 3.7: An example of the bottleneck node 36 Figure 3.8: An example to search the lifetime-preserving tree in a centralized manner 38 Figure 3.9: An example to search the lifetime-preserving tree in a centralized manner........ 38 Figure 3.10: The centralized LPT algorithm, which creates a lifetime-preserving tree spanning all source nodes as vertices and contains no loops 39 Figure 3.11: The ExploreBranch function, which explores the highest-energy branch from every source to any tree root using a method similar to RPF 42 Figure 3.12: An example to search the highest-energy branch between nodes 5 and 8 42 Figure 3.13: An example to construct a tree for node 8 44 Figure 3.14: An example of how a loop could have been created if the root does not compare the existing routes with the newly-arrived one 45 Figure 3.15: The NoLoop function, which takes the received branch brList^k as an input and test if attaching it to the tree in tree„ will not create a loop 46 Figure 3.16: The set of trees created by the sources in the event region. Only the one with the highest tree energy is employed for data aggregation among these nodes 48 Figure 3.17: The SearchLPT function, which searches the lifetime-preserving tree for each source 49 Figure 3.18: The distributed LPT algorithm, which creates a lifetime-preserving tree spanning all source nodes as vertices and contains no loops 52 Figure 4.1: Percentage error on tree energy generated by distributed LPT to that of the centralized one 61 Figure 4.2: Average per source controls involved in constructing the data aggregation trees. 62 Figure 4.3: Maximum and average tree depths from each participating source node to the tree root 62 vi Figure 4.4: Average dissipation energy as a function of network size 63 Figure 4.5:-Average node lifetime for each participating source with N = 50 nodes 65 Figure 4.6: Average node lifetime for each participating source with N = 100 nodes 65 Figure 4.7: Average node lifetime for each participating source with N = 150 nodes 66 Figure 4.8: Average node lifetime for each participating source with N = 200 nodes 66 Figure 4.9: Average node lifetime for each participating source with N = 250 nodes 67 Figure 4.10: Average RtoS delay between transmitting a data at the root and receiving at each sink 68 Figure 4.11: Average StoP delay between transmitting a data at a source and receiving at its parent 69 Figure 4.12: Average delay between transmitting a data at each source and receiving it at each sink 70 Figure 4.13: Average packet delivery ratio between transmitting a data and receiving it at each sink 70 vii List of Tables Table 2.1: A comparison of data dissemination protocols 12 Table 2.2: A comparison of node scheduling protocols 22 Table 3.1: The format of a tree for node n 46 Table 3.2: The packet structure of the LPT control message 51 Table 4.1: A summary of Diffusion-related parameters 58 Table 4.2: A summary of other parameters used in the simulation models 59 viii List of Acronyms ASCENT Adaptive Self-Configuring sEnsor Networks Topologies CDMA Code Division Multiple Access DCS Data-Centric Storage DCTC Dynamic Convoy Tree-Based Collaboration Diff Directed Diffusion E-Span Energy-Aware Spanning Tree EADAT Energy-Aware Data Aggregation Tree GEAR Geographical and Energy Aware Routing GPS Global Positioning System GRAB GRAdient Broadcast IA Immediate Agent ID Identifier IP Internet Protocol LEACH Low-Energy Adaptive Clustering Hierarchy LPT Lifetime-Preserving Tree MAC Medium Access Control MEMS Micro Electro Mechanical System MLDA Maximum Lifetime Data Aggregation PA Primary Agent RPF Reverse-Path Forwarding STEM Sparse Topology and Energy Management TDMA Time Division Multiple Access TTDD Two-Tier Data Dissemination WSN Wireless Sensor Network x Acknowledgements I would like to express.my sincere thanks to my supervisor, Professor Vincent W. S. Wong, for his guidance, advice, and support throughout the course of this thesis. I also wish to express my gratitude to my colleagues, particularly Joo-Han Song and Yeming Lu, for their help and comments on my simulation work. Many thanks go to my family and friends, especially C. H. Lee and Alice H. H. Lui, for their encouragement, understanding, and support throughout this difficult and yet rewarding process. xi Chapter 1 Introduction The rapid advances in wireless communication and Micro Electro Mechanical System (MEMS) have made Wireless Sensor Networks (WSNs) possible. Such environments are typically comprised of a large number of sensors being randomly and densely deployed for detecting and monitoring tasks. These sensors, developed at a low cost and in small size (mm-scale for smart dust motes [1]), are responsible for object sensing, data processing, storing, and routing activities. Applications of such networks range from battlefield communication systems (e.g. intrusion detections and target surveillance) to environmental monitoring networks such as habitat monitoring, chemical sensing, infrastructure security, inventory and traffic control etc. For example, sensors are distributed across a forest in order to report the origin of a fire event when there is a significant increase in the average monitoring temperature. Reference [2] provides a more thorough discussion on some potential WSN applications. Unlike the conventional ad hoc communication networks, energy resources in WSNs are usually scarce due to the cost and size constraints of sensor nodes. In addition, it is impractical to replenish energy by replacing batteries on these nodes. Conserving energy is thus the key to the design of an efficient WSN. WSNs may deploy several hundreds to thousands of sensor nodes. Protocols in such networks must therefore be scalable. Furthermore, since nodes are untethered and their geographic positions are not pre-determined, these nodes may also need to possess some self-organizing capabilities. Network dynamics that result from both node movement and unpredictable energy depletion also bring new challenges to the design of an efficient WSN. Since nodes can only carry limited battery resources, they usually get disconnected from the network easily. Such frequent node disconnections suggest that the design must accommodate 1 Chapter 1 Introduction 2 topology changes. In summary, the fulfillment of all the above conditions requires a unique rather than conventional ad hoc networking techniques. Perhaps the most significant difference between Internet-based distributed systems and WSNs is the collaborative efforts provided by sensors. Each node in an Internet-based system competes with all other nodes for a fair share of network resources in order to run tasks and applications of its own. Per-hop fairness is thus the primary concern. WSNs, on the other hand, are not general-purpose communication networks. They rely on the collective information provided by sensors but not on any individual sensing report. Most sensor nodes are task-specific in that they are all programmed for one common application. A node at one specific time may be granted more access to the network than all other nodes if the program objective is still satisfied. For this reason, network resources are shared but it is not necessary that they be equally distributed as long as the application performance is not degraded. Since sensors are being densely-deployed in WSNs, the detection of a particular stimulus can trigger the response from many nearby nodes. Thus, data in such networks are usually not directly transmitted to interested users upon event detection. Instead, they are aggregated with neighboring sources locally to remove any redundancy and produce a more concrete reading [3-6]. Throughout the rest of this paper, we use the term sinks to denote these interested user nodes that inject queries to the network. Intermediate nodes do not simply forward data to next hops, but can also interpret any data using their local processing abilities if required.. Reference [7] suggests that transmitting a data packet of size 1 Kb to a distance 100 m away is equivalent to executing 3 million instructions on a general-purposed computer. Therefore, it is preferable to perform any local computation or in-network processing in order to minimize communication cost and optimize energy efficiency. In this thesis, we focus on constructing a data aggregation tree among any given set of source nodes. The tree has a dedicated root for which the data from various sources are gathered. Moreover, the tree is structured in a way that can preserve the functional node Chapter 1 Introduction 3 lifetime of the event sources subject to the condition that they are constantly transmitting. The functional node lifetime is defined as the time till a node runs out of its energy. Reference [8] suggests that extending the node lifetime is equivalent to increasing the amount of information gathered by the tree root when the data rate is not time-varying. We consider a network of randomly-deployed sensor nodes in which each node has an identical transmission range. An event that triggers the sensors around it occurs at random in the network. Data reports from these sensors are clock-driven upon event detection. Furthermore, they are aggregated along their ways to be collected at the tree root and periodically sent to the sinks. To prevent data lost, the tree is periodically scanned and any broken link should be repaired whenever necessary. We therefore wish to evaluate the additional amount of time that the event sources can survive, provided that the tree is employed for data gathering. 1.1 Motivations and Objectives To enable data aggregation among event sources and to reduce the communication cost, there is a need to establish a converged tree structure inside any given event region. Such tree allows all raw data reports to be aggregated along the way to a single processing point. Only relevant information is extracted before transmitting it to any distant sink. Therefore, the converged tree construction becomes one of the fundamental issues for aggregation in WSNs. In fact, not all the trees are ideal for aggregation inside the event region. Since energy is usually scarce in WSNs, it is most power-efficient if these sources can provide data to the sinks for the longest possible time. A tree that can survive for longer duration thus naturally becomes the best choice. To better illustrate this idea, consider a simple multicast tree that is used to collect data from 5 different sources (depicted in Figure 1.1a). Since all nodes have the shortest distance to the root (i.e. node A), such a tree allows data to be gathered with minimum latency. Despite Chapter 1 Introduction 4 energy 10 J energy 10 J energy 8 •+ *• comm. link • tree link energy 81 energy 9 J energy 3 J a) Source-based multicast tree b) Lifetime-preserving tree Figure 1.1: An example to show that if the residual energy is not considered in the tree construction, it can reduce the node lifetime and the amount of information gathered by the root: a) The fact that node B has a dependent child quickly depletes its energy and thus data from node C will no longer be received, b) The time to reconstruct a tree is extended if node C is attached to D instead. this, the fact that the lowest-energy node B has a dependent child of node C can indeed deplete its valuable energy resources quicker than i f node C was attached to node D (Figure 1.1b) . O f course, node D wi l l have a higher energy dissipation rate than what it had before. However, by balancing the lifetime of each individual node, the frequency of tree reconstruction (which repairs any broken tree link and incurs an additional energy cost from each source) can be reduced. Also observe that any information generated by node C wil l never arrive at node A prior to restoring the disconnected tree. Attaching nodes C to D would have prevented it from happening. We thus conclude that residual energy during tree construction plays an important role in determining the functional lifetime of event sources and the amount of information gathered by the root. To address these problems, we construct a tree in which each parent node has the maximal-available energy resource to receive data from its children so that the time to refresh this tree is extended. We accomplish this by assigning nodes with higher energy to be the data aggregating parents for lower-energy nodes. In case this is not possible, see for example node D in Figure 1 .1b , we wil l arrange the best neighbor to be its parent. We name this tree the Lifetime-Preserving Tree or simply LPT. For the purpose of tree construction, we also define the tree energy to be the minimum residual energy of all the parents in a given tree. Such term Chapter 1 Introduction 5 shall directly reflect the time until the first broken tree connection is detected. For example, the two different trees in Figure 1.1a and Figure 1.1b have the tree energy of 3 and 8 Joules, respectively. Over the past few years, there has been a number of data routing protocols proposed for WSNs [9 - 20]. Directed Diffusion [19, 20] is among the first to provide a complete and simple routing infrastructure for large-scale WSNs. We therefore choose it as our routing platform and use it to evaluate the energy savings as well as the additional amount of time that the sources can survive by launching our proposed tree construction algorithm. Although there exists some data forwarding tree structures from sources to each sink when user queries are first flooded to the Diffusion network, such arrangements do not fulfill the purposes of data aggregation for the following reasons: • Depending on how the sinks choose the transmit paths, different sources can forward their data to the sinks via entirely different paths even if they are next to each other (see Figure 1.2a). It is thus most efficient if a single piece of aggregated data can be transmitted to each sink through only a single path (see Figure 1.2b). • Packet drop rates depend on the amount of network traffic. As the number of a) Transmission via different paths b) Transmission with aggregation Figure 1.2: An example to show how the number of transmission paths can affect energy efficiency: a) A large number of intermediate sensor nodes are involved in transmitting raw data reports to the sinks, b) Only a portion of these nodes are now transmitting data reports provided that aggregation is carried out on a pre-established tree a priori. Chapter 1 Introduction 6 transmit paths increases, areas near the sinks and the sources may become congested. Nodes thus need to spend more time and energy for retransmission. • Transmit paths in Directed Diffusion usually span wide, and therefore sources could redundantly send their data for a number of hops away before these data can actually get aggregated at intermediate nodes (see the bolded arrows in Figure 1.2a). The number of data transmissions involved can be brought to a minimum of 1 (see the bolded arrow in Figure 1.2b) for each source if a tree is properly structured inside the event area, provided that these sources are inter-connected to each other. • Diffusion nodes possess only local information, i.e. they know their data-forwarding and requesting neighbors but not any information on how the tree is being structured. It is thus unknown as to how long they should hold the sensed data for aggregating with those from other sources before passing it on to the next hop. To enable data aggregation among the sources and transmit data to each sink via a single path, research must therefore be conducted in order to construct a lifetime-preserving data gathering tree inside any given event region. The main objectives of this thesis are as follows: • Design a distributed lifetime-preserving converge tree construction protocol for data aggregation in WSNs; • Validate that the constructed tree does have a tree energy greater than other tree structures, by using a centralized approach; • Evaluate the energy savings and the additional amount of time that the sources can survive, by implementing the proposed protocol on top of Directed Diffusion, under different traffic scenarios; • .Compare other relevant network parameters such as average delay and packet delivery ratio and determine the amount of control messages incurred during the tree Chapter 1 Introduction 7 construction. 1.2 Contributions of the Thesis The main contributions of this thesis are as follows: • Spanning Tree Construction Scheme: To examine how different tree arrangements can have an impact on the functional lifetime of various event sources, we propose the spanning tree construction scheme and an energy-aware variant of it. Both heuristics are simple to implement, but may not 'be optimal in preserving the functional node lifetime. • Lifetime-Preserving Tree Construction Scheme: The term "tree energy" is introduced to reflect the time till detecting the first broken tree link of any tree created by the set of connectivity in the event area. A distributed tree construction scheme is proposed to generate an LPT spanning all event sources for data aggregation in practical WSNs. A centralized variant of the LPT construction model is also proposed to validate the correctness of the tree created by the distributed approach. 1.3 Structure of the Thesis The remainder of this thesis is organized as follows: In Chapter 2, we describe some previous work on routing, particularly Directed Diffusion [19, 20], for WSNs. Furthermore, techniques and related issues on data aggregation are introduced. A summary of some previous work on aggregation tree constructions are also presented. This chapter continues by exploring some node scheduling algorithms, which are an alternate way to conserve energy in sensor Chapter 1 Introduction 8 networks. The proposed LPT construction models, both the centralized and distributed version, are presented in Chapter 3. Moreover, a modified spanning tree protocol which we use to compare with our scheme is also described. Descriptions on simulation methodology and performance metrics used for comparison of protocols are presented in Chapter 4. Numerical results and discussion are also presented. Finally, Chapter 5 concludes this thesis with suggestions on some improvement and future work. Chapter 2 Related Work This chapter begins by reviewing the Directed Diffusion [19, 20]. Several other data dissemination protocols that focus on the construction of a communication infrastructure for successful packet delivery will also be summarized. This chapter continues by discussing some in-network aggregation techniques which are now seen as fundamental to WSNs. The timing policies that address how long a sensor should wait to receive data from its data-forwarding neighbor before aggregation can also have a significant impact on the data accuracy, and freshness. A summary of some aggregation tree construction techniques is also presented. Besides aggregation, another way to conserve energy in WSNs is to simply put some nodes into the sleep state. The only question lies in how to coordinate these sensors in a way that can maximize the energy-savings yet still preserve the initial communication capacity and sensor coverage [21 - 24]. Some node scheduling algorithms proposed in the literature are reviewed at the end of this chapter. 2.1 Directed Diffusion Over the past few years, there has been a number of data routing protocols proposed for WSNs. Directed Diffusion [19, 20] is among the first to provide sensors with a scalable and robust routing mechanism. Under large-scale and dynamic WSNs, the easiest way to achieve robustness is to flood queries and allow data to be returned to all requesting nodes. However, broadcast storms created by flooding can rapidly drain sensors' energy resources and bring down the entire network. Directed Diffusion differs in that all interests (defined as the queries injected by the sinks) and data are described using low-level abstractions rather than unique node identifiers [25]. Such data-centric naming scheme allows nodes to easily process any 9 Chapter 2 Related Work 10 data in the network. For instance: data messages with matching descriptions but different destinations are combined at intermediate nodes before they are being transmitted to upstream neighbors. In addition to such feature, aggregation and caching are also incorporated into the design. Aggregation requires only one copy of the matching interests to be forwarded to down-stream sensors, effectively scaling down the query traffic periodically injected by the sinks to the network. To increase robustness, caching is used to set up the gradients to each requesting node, allowing periodic exploratory data from each source that matches with the interests to be drawn towards the sinks through a multiplicity of different paths. To further minimize energy, path reinforcement follows to reduce these paths to a smaller number. Figure 2.1 illustrates these operations. As previously mentioned, the fact that it does not use any global information results in sub-optimal transmit paths. In the worst case, different sources can send their data to sinks via entirely different paths even if they are next to each other (Figure 1.1a). This routing scheme can be power-inefficient and is the motivation of our research. a) Interest propagation b) Exploratory data c) Reinforcement and data Figure 2.1: A simplified schematic for Directed Diffusion: a) User interests, represented by the low-level attribute-value pairs, are broadcasted and processed at intermediate nodes, b) The exploratory data set up the gradients towards the sink with the aid of data caches, c) Reinforcement reduces the multiplicity of transmit paths to a small number, allowing only high-quality data to be drawn towards the sink. 2.2 Data Dissemination Conventional ad hoc routing protocols can be divided into two main categories: proactive and Chapter 2 Related Work 11 reactive. Proactive routing maintains the shortest path but requires periodic update of the routing entries for all destination nodes. A change in link cost will trigger excessive updates of routing tables and thus waste valuable energy resources. For this reason, proactive routing cannot be directly applied to energy-constrained and dynamic WSNs. Reactive routing on the other hand creates routes on-demand. It trades off the delay of route discovery for less message exchanges and thus is suitable for WSNs. A special routing technique that has recently drawn attention is geographic routing [9, 26]. It greedily forwards data to all destinations without sacrificing much energy resources or delay. However, it does require all sensors to be location-aware. The following sections will introduce several existing data dissemination techniques that provide a similar type of routing support as Directed Diffusion for different kinds of network activities, and they are briefly compared in Table 2.1 and [27].. 2.2.1 Low-Energy Adaptive Clustering Hierarchy (LEACH) Data transmissions are not always event-triggered, and sometimes need to be performed at regular intervals and destined to a fixed location. Using conventional multihop routing would require packets to be excessively processed at nodes close to base station, which refers to a fixed location where data are destined. Using direct transmissions on the other hand would dissipate a large amount of transmit power for far-away nodes. When the transmit distance is short, direct transmission can actually achieve greater energy savings than multihop routing. LEACH [10], motivated by this result, leverages the advantage of small transmit distances to local cluster heads for most sensor nodes and requires only the cluster heads to transmit long distances to the base station (depicted in Figure 2.2). One way to reduce the amount of communication is to incorporate data aggregation on the cluster heads before sending out packets to the base station. The roles of the cluster heads are rotated randomly so that the energy loads can be shared among the sensors. Time Division Multiple Access (TDMA) schedules are also created for each cluster node in order to avoid excessive contentions of the Chapter 2 Related Work 12 Table 2.1: A comparison of data dissemination protocols Protocol name Algorithm descriptions Special remarks Network structure Location aid Directed Diffusion [19,20] On-demand flooding with interest/data aggregation, gradient caching, and path reinforcement No global information resulting in suboptimal paths Flat No LEACH [10] Dynamic clustering with periodic direct transmissions to base station, TDMA scheduling and data fusion inside clusters Require variable transmission power on sensor nodes Clusters No GRAB [11] Credit-based adjustable mesh forwarding to deal with failures and channel errors, power management using density control Per-sink cost field setup using delayed broadcast Flat No GEAR [9] Geographic and energy-aware query dissemination to target region, recursive geographic routing or restricted flooding inside target region Require knowledge of energy level to all nodes Flat Yes TTDD [12] Per-source grid construction to limit query flooding, trajectory forwarding to deal with sink mobility Redundant grid construction and maintenance Grids Yes Figure 2.2: A simplified schematic for L E A C H : Randomized rotation of local cluster heads allows load-balancing, data aggregation on all cluster heads reduces the communication costs to the base station, but all cluster heads need to directly transmit data reports to a fixed base station. Chapter 2 Related Work 13 channel and to allow sensors to effectively turn their radios off when not actively transmitting. One extension of LEACH is to use multihop routing to replace direct communication for cluster heads. Such a method removes the requirement of high-power nodes since they now only need to forward data to nearby intermediate cluster heads. Instead of choosing cluster heads randomly, one can take the residual energy into considerations. This change allows sensors with a higher energy to be selected as cluster heads. 2.2.2 GRAdient Broadcast (GRAB) GRAB [11] is a data forwarding protocol that focuses on resolving network dynamic in WSNs. The idea behind GRAB is to employ credit-based adjustable mesh forwarding (see Figure 2.3a) through the sensor nodes initially configured by a sink-initiated cost field setup. Each packet is assigned with credits in addition to the optimal shortest-path cost for transmission. Such a scheme allows data to be delivered through different overlapping paths rather than a single optimal shortest path. The packet will eventually arrive at the sink through at least one of the working paths even if some intermediate nodes malfunction or if the channel gets corrupted. In comparison with the explicit multiple path approach (depicted in Figure 2.3b), a mesh forwarding structure provides richer connectivity and increases the a) Credit-adjustable mesh forwarding b) Multipath forwarding Figure 2.3: A simplified schematic for the credit-adjustable mesh forwarding: a) Al l packets are assigned with credits for transmission through the nodes initially configured by a sink-initiated cost setup using deferred broadcast, b) Simple multipath forwarding structure does not provide the rich connectivity as credit-adjustable mesh forwarding. Chapter 2 Related Work i 14 robustness of the design. GRAB assumes a static network since node movement will require excessive updates of the cost field. As with Directed Diffusion, GRAB fails to consider aggregation among a group of sources at the early stage. When the number of sources increases, the fact that each source will be equipped with its own mesh data forwarding structure can quickly drain nodes' energy. 2.2.3 Geographical and Energy Aware Routing (GEAR) A special routing technique that has recently drawn attention is geographical routing. GEAR [9] is a protocol that further takes residual energy into consideration and is designed to efficiently disseminate queries to a destination. Motivated by the fact that queries are often geographical (i.e. they have a target area), packets are directly forwarded to the destination rather than flooded everywhere. GEAR assumes that nodes are aware of their own geographic positions, and uses energy-aware neighbor selection to aggressively route the queries toward the target region. In addition to the distance to destination, neighbor's residual energy is also considered in the cost function so that energy load among any neighborhood can be balanced. The tradeoff, however, is the increased path length used to transmit the queries since energy-efficient paths are not necessarily the shortest. Restricted flooding or recursive geographical forwarding immediately follows to disseminate packets inside the area once the queries have arrived at the border of the region. The difference of the two lies in the type of transmissions, namely broadcast and unicast. The choice of which one to use depends on the relative energy cost determined by the node density of the destination area. The conventional minimum-energy path approach differs from the GEAR energy-aware neighbor selection algorithm in that a path in the former approach is selected for transmission whenever the total energy cost along this path is the lowest among all choices. Unfortunately, doing this will only cause nodes on this path to be extensively used and nodes' energy to be depleted quickly [13]. Chapter 2 Related Work 15 2.2.4 Two-Tier Data Dissemination (TTDD) TTDD [12] is a data dissemination protocol designed to deal with the issue of sink mobility in WSNs. Mobile sink often requires frequent location updates by flooding location information throughout the entire network, so that future data can be correctly forwarded to the mobile destination. Such a repetitive broadcasting operation not only increases collisions in the transmissions, but more importantly also drains the battery of sensors resulting in a reduction of network lifetime. TTDD employs a mobile Internet Protocol (IP) -like trajectory forwarding strategy in which location information is only updated between the immediate agent (IA) and primary agent (PA) of the mobile sink. To enhance scalability, robustness, and load-balancing, a per-source grid structure is created so that only a portion of nodes, namely the dissemination nodes, is involved in delivering data reports to the mobile sink. Such an approach ensures that queries are only flooded in local cells, thereby effectively reducing the amount of traffic to be spread over the entire network. Figure 2.4 illustrates these operations. As with GEAR, location discovery is required for grid constructions. Data aggregation among the sources is also required so that multiple different grid structures will not be created for nodes that detect the same event. Q J O - Higher/lower-tier data grid/trajectory forwarding ) —g i nk O ^Higher/lower-tier query grid forwarding O 0 \ Mobile sink, o Figure 2.4: A simplified schematic of the two-tier data dissemination: A higher-tier data grid structure is created for each source allowing queries to be flooded in lower-tier grid only, and trajectory forwarding is employed so that the most recent location of the mobile sink is only updated with the primary agent. Chapter 2 Related Work 16 2.3 Data-Centric Storage and Data Funneling One way of achieving in-network aggregation is to deploy a data-centric WSN where all data are named with communication abstractions rather than unique node identifiers [25]. Unlike other conventional IP-based networks which are usually associated with a directory service, nodes in data-centric network describe their data by using attribute-value pairs. For instance: a message describing a fire event may only contain a TYPE attribute with a value set to FIRE. Such a technique not only enables efficient reduction of redundant messages that arrive with the same content description, but also avoids identifying nodes. This data-centric approach is now seen as fundamental to WSNs. The Data-Centric Storage (DSC) [28] stores data by names at some nodes. These nodes are not necessarily the ones that generate the data. In comparison with the data-centric routing where query has to be first flooded to the network before any data can be returned to the sinks, all messages with the same descriptions will be directed and stored at a designated sensor upon detection. The DCS approach avoids extensive query flooding and subsequent updates of the querying messages. However, it requires extensive routing support in order to correctly direct the sinks to the storage nodes for the desired data. Reference [4] explores the problem of minimizing the communication costs required to send the readings from a set of sensors, bounded by some geographic coordinates, to a single destination node. Data funneling which integrates both data aggregation and compression is proposed to meet the objective. This work is motivated by the fact that packet overhead often makes up a large component of sensing data. Since all sensors within the source region have a common sink, substantial savings can be achieved if different readings can be combined into a single super-packet containing only one packet overhead. All sensors within this region will select a common dynamic cluster head and have their readings aggregated along the way to the node using proper scheduling. The choice of order in which readings are arranged in the Chapter 2 Related Work 17 super-packet can also be used to convey additional information to the sink. The cluster head can thus choose to suppress some readings and arrange others in such a way that can indicate the value contained in the suppressed readings. However, the tradeoff is the additional hardware complexity required for encoding and decoding. 2.4 The Impact of Timing in Data Aggregation The timing policies that decide how long a node should wait to periodically receive data from its source neighbors can have a significant impact on data accuracy and freshness. Authors in [29] compare three different timeout models: periodic simple, per-hop, and per-hop adjusted. Periodic simple works by having each node wait a pre-defined period of time before sending out its aggregated data whereas periodic per-hop transmits the result as soon as it hears from all its data-forwarding neighbors. In their proposed periodic per-hop adjusted timing model, each node schedules their timeout right before its parent does. Such cascading timeout results in creating a data wave reaching the sink in one data collection period. Extensive simulations have shown that, among the three models, only the periodic per-hop adjusted approach can preserve the initial power-savings and maintain the highest percentage of data freshness at the same time. Their work builds on top of a simple tree establishment protocol that sets up reverse path from all nodes back to the sink after an initial querying. 2.5 Data Aggregation Trees and Clusters Our work bears some resemblance to other research efforts in the literature. In fact, a number of recent work has begun to consider collaborating nearby sensor nodes by the use of a data aggregation tree/cluster. Such tree/cluster provides event sources with a mechanism to refine their readings, so that only a minimum amount of energy is required to deliver the information Chapter 2 Related Work 18 to the user. In this section, we provide a summary of these construction techniques. 2.5.1 Energy-Aware Data Aggregation Tree ( E A D A T ) The work in [30] attempts to construct a tree rooted at a base station and spanned all network nodes by extensive use of timers. Motivated by the fact that only non-leaf nodes in the tree are aggregating and relaying traffic, radios of all leaf nodes are turned off for immediate energy savings. The nodes with higher residual energy have a higher chance to become non-leaf tree nodes, thereby enhancing the likelihood of turning off lower-energy leafs. However, when all the tree nodes are also the event sources (i.e. the tree is inside the event area), each of them possess some sensor readings and therefore all leafs cannot be put to sleep. The algorithm requires a given tree root (base station) to initially broadcast a control message and start the tree construction. Each node upon receiving this message for the first time starts a timer that expires in a time duration inversely proportional to its residual energy. A timer is refreshed if a node receives a message during the count down. After the timer expires, the node broadcasts a similar control message indicating its willingness to be a parent in the tree. During the process of timer update, each node selects an appropriate parent for communication with the root. Observe that a timer can be extensively updated when the network is large, especially for leaf nodes. The result can be a long waiting time for the tree construction. 2.5.2 Maximum Lifetime Data Aggregation Reference [31] attempts to find a schedule of various directed trees, subject to the requirement that the number of rounds during which a base station can aggregate information from all the nodes via these trees is maximized. The protocol assumes that nodes are aware of every others' positions and have the abilities to directly reach any other sensor (including the base station) in the network. Such a Maximum Lifetime Data Aggregation (MLDA) problem is Chapter 2 Related Work 19 approached by coordinating the radio ranges and data aggregating agents of various nodes in a way that the resultant flow of traffic towards the base station maximizes the system lifetime. In practice, the knowledge of exact sensor positions is usually not known a prior; due to the ad hoc manner in which nodes are deployed. By including Global Positioning System (GPS) to all the nodes can be expensive. By running an efficient location discovery scheme (e.g. [32 - 35]) on the other hand will also incur an additional control cost to all nodes. Moreover, the abilities to adjust node's radio range will not always be feasible to WSNs. A closer analysis is hence required to justify the impact of their assumptions on the system lifetime. 2.5.3 Minimum-Cost Convoy Tree More recent work has begun to consider collaborating nearby sensor nodes to generate a more concrete report of the object being traced. Such issue has been recognized by [36] which further provides a dynamic convoy tree-based collaboration (DCTC) framework for tracking a mobile target. Using some heuristics in predicting the object moving direction, they proposed a tree construction algorithm that can dynamically configure itself by adding or pruning some sensors as the target moves. The root can dynamically collect and refine the readings gathered from various tree nodes. The challenge of their work lies on finding a sequence of minimum-cost trees, so called minimum-cost convoy tree sequence, whose coverage on the moving object is above a certain threshold. The tree they have considered is the one that has the root being closest to the target. Furthermore, all other nodes are arranged in a way that the cost of sending a packet via some nodes to this root is minimized. However, the authors did not consider the ability of sensors to perform in-network aggregation of data enroute to the tree root. The cost of sending a packet to the root needs to be re-evaluated so as to account for the effort of any parent being able to combine the data gathered from all of its children. Chapter 2 Related Work 20 2.5.4 Spanning Tree over Area-Dominating Set Since the coverage area of individual sensor nodes usually overlaps, the work in [37] attempts to periodically find the smallest subset of nodes that covers the monitoring area. This group of nodes is referred to as the area-dominating set. The authors in this paper suggest the use of a spanning tree, induced by the initial interest flooding over the area-dominating set, for aggregating reply messages from various event sources. Specifically, a node belonging to this set considers the neighbor for which the first interest message comes from as its parent in the distributed spanning tree. A parent waits to receive multiple replies from all its children in the tree before sending its own aggregated reply message. The sink where the interest is originated from is the root of the spanning tree. As with DCTC, the authors did not consider nodes' residual energy in the tree construction. The result can be a reduction in the node's lifetime and the amount of information collected by the tree root (Section 1.1). 2.5.5 Balanced Convergecast Tree The work in [38] addresses the problem of convergecast (many-to-one) for data aggregation. A tree that is rooted at the base station is constructed so that the link cost from each node to the base station is minimized. The authors further improve the design by balancing the tree during the construction, thereby enhancing the likelihood of simultaneous aggregation and reducing the latency for convergecast. Furthermore, two Code Division Multiple Access (CDMA) codes are allocated to nodes for collision-free transmissions towards the base station. Unfortunately, the algorithm is centralized and the knowledge of global connectivity is required. As with [37], the base station (sink) is also the root of the tree. 2.5.6 Data Aggregation Clusters A number of recent work has begun to consider dividing the network area into small adjacent grids or clusters on which aggregation is performed. Specifically, a cluster head is usually Chapter 2 Related Work 21 associated with each cluster so that all nodes belonging to the same cluster can aggregate their readings through this node. In fact, a number of parameters can be considered in the cluster head selection. The work in [39] periodically selects cluster heads according to a hybrid of their residual energy and node degree, resulting in a set of energy-rich cluster heads being uniformly distributed across the network. However, their work assumes that nodes have variable transmission power to ensure that a certain degree of connectivity exists between the clusters. In comparison with the explicit tree approach (e.g. [31, 36 - 38]), only one layer of aggregation points exists, thereby increasing the load of each cluster head. Reference [40] presents an algorithm to find the minimum number of aggregating points connecting these cluster heads such that the energy cost of sending a packet from each cluster head via these points to a fixed base station is minimized. The benefit is the additional level of aggregation, resulting in a multi-level data aggregation hierarchy. However, extensive routing support such as the shortest-path and location information is required beforehand. 2.6 Node Scheduling After a thorough discussion on some of the existing routing and aggregation-related protocols, we now introduce an alternate way to minimize data traffic and conserve energy in WSNs. WSNs are often densely deployed in an ad hoc manner. Having a substantial amount of sensors is necessary to minimize the number of blind spots created by random deployment. In addition, since sensor may move and deplete the energy rapidly, there must be enough reserved nodes to preserve the initial sensing coverage and communication capacity. However, using all sensors at once is unnecessary and will only lead to network congestion and unwanted energy expenditure. From an application perspective, a node is redundant and can be turned off for immediate energy-savings if its sensing area is completely covered by its neighboring sensors. Reference [21] provides an analysis for the probabilistic bound of this Chapter 2 Related Work 22 redundancy and suggests that there are always a number of redundant nodes for a" particular network setting. From a network perspective, when the average node degree is high, channel contention increases and network congestion starts to occur. Nodes waste their valuable energy via transmission as packets are being dropped. Due to these reasons, a large number of sensors need to be initially deployed, yet they need to coordinate and work alternatively in order to save energy and prolong the network lifetime. The question lies in how to assign these sensors so that they can maximize the energy savings and yet still preserve the initial capacity and sensor coverage. The following subsections will introduce some node scheduling algorithms proposed in the literature, and they are compared in Table 2.2. Table 2.2: A comparison of node scheduling protocols Protocol name Algorithm descriptions Power conservation ASCENT [41] Partially or completely turn off nodes based on measured connectivity and data loss rate Duty cycle reduction of active nodes and periodic sleep of passive nodes Connected sensor cover [22] Put nodes to sleep if they are not required in preserving the initial capacity and sensing coverage Complete turn off of redundant nodes STEM [42] Coordinate periodic sleep transitions and wake up nodes when it is time to forward data Periodic sleep of all nodes 2.6.1 Adaptive Self-Configuring sEnsor Networks Topologies (ASCENT) ASCENT [41] is a self-organizing node scheduling algorithm in which redundancy introduced by dense deployment is exploited to achieve energy-savings and extend the network lifetime. Unlike other node scheduling algorithms where topology or routing information is used (e.g. [22, 24]), ASCENT requires each node to determine its participation in the network based solely on the measured connectivity and data loss rate. Active nodes either invite passive neighbors to join the network due to poor connectivity or reduce their duty cycles by passively turning" off the transmitters due to massive collisions. Passive nodes Chapter 2 Related Work 23 probe the channel and join the network only when it is helpful to do so. Radios for passive nodes are also completely turned off at a regular interval in order to conserve listening power. ASCENT differs from other approaches in that receivers are not being turned off before going to sleep, so that they can rapidly react to any network change. In addition, this protocol results in active nodes being distributed non-uniformly depending on different network states. Such a self-configuring behavior is encouraging since different traffic patterns will require different sensor population in order to make the delivery more reliable. ASCENT defines a neighbor as a node that is within the transmit range and yet has a data delivery ratio above some threshold. This definition is important since connection to a congested node can hardly be established, even if it is within the transmit range. Unfortunately, load-balancing is not being incorporated into the design. Failing to do so may result in either network partitioning or creation of blind spots. 2.6.2 Connected Sensor Cover Reference [22] introduces a technique to minimize the amount of communication incurred by query executions. Neighboring sensors often monitor close geographic areas and generate the same readings in response to a query. It may be sufficient to use only a portion of these nodes for data gathering and transmissions to the sink. This protocol exploits such redundancy and self-organizes the network into a topology that involves only a small number of sensor nodes sufficient to process the query. To minimize energy usage, the algorithm turns off unselected nodes but ensures that the initial sensor coverage and network capacity are preserved at the same time. The idea is to choose a path of sensors that connects to the already-selected sensor set with the largest coverage in the querying area. The selected path of sensors is then added to the already-selected sensor set. These steps are repeated until the set of sensors covers the entire querying region. The design can further be improved by considering residual energy in the path selection Chapter 2 Related Work 24 so that nodes with a lower energy have less chance of being selected in the query executions. Doing so can evenly distribute energy loads across the querying region and effectively extend system lifetime. This algorithm differs from ASCENT on that density dimension is exploited to minimize the energy usage. In other words, only spatial density and sensing radius of nodes can affect the performance. As we shall see later, STEM [42] schedules nodes by exploiting time dimension instead. The choice of which one to deploy depends on the network configurations and task of the network. 2.6.3 Sparse Topology and Energy Management (STEM) A typical WSN spends most of its time monitoring the environment and waiting for an event to occur. Network capacity is not required until data readings need to be forwarded to a sink. Turning off radios in the monitoring state can thus completely eliminate unnecessary energy wastage. STEM tackles this issue by coordinating sleep transitions of all nodes in order to utilize full energy savings. Unlike the connected sensor cover protocol which preserves the network capacity at all times, STEM aggressively puts nodes to sleep and wakes them up only when they need to forward data. The idea here is to periodically turn on a separate paging radio to listen if anyone is talking to this node. The data radio of this node comes back alive only if it is initiated by the wakeup procedure. Unfortunately, the tradeoff is the latency of switching back to the data transferring state incurred by both polling and initialization processes. STEM differs with other scheduling algorithms [22, 24, 43] in that setup latency, rather than the node density, is leveraged to minimize energy usage. Major'energy saving will not require a dense network. However, since algorithms under the two categories have orthogonal functionalities, running them together can combine the benefits of both and maximize the system lifetime thoroughly. Chapter 2 Related Work 25 2.7 Discussions and Summary Our work is motivated by some of issues in the existing research work. In Directed Diffusion [19, 20], nearby nodes can send their data to the sinks via entirely different paths. In GRAB [11] and TTDD [12], each source can initiate its own mesh and grid structure for data transmission. These redundancies are the major source of energy wastage, thereby motivating us to create a tree for collaborating nearby event sources. Our work differs from [4] by that we focus on tree establishment rather than aggregation technique. Such tree allows nodes to know where they should send the extracted data readings for further processing. Note that the root in our proposed scheme has the same functionality as the cluster head in [4]. However, in terms of root selection, we consider residual energy of nodes inside the local event area whereas the work in [4] compares the global distance to a common sink outside the region. Since our goal is to show how much time our proposed tree can survive rather than how fresh the data can be gathered, we consider using the periodic simple timing model in [29] to collect data readings from the sources. Another reason is to avoid the additional control overheads that would be incurred in maintaining the cascading timeout scheme [29]. A number of work has begun to consider collaborating nearby sensor nodes by the use of an aggregation tree. Among these, EADAT [30] is similar to our proposed scheme. However, EADAT requires the extensive use of timers. In addition, EADAT, MLDA[31], and the work in [37, 38] require the prior knowledge or support from a base station (or a given root) for tree construction. In an event area where a root is initially unknown, these techniques can be difficult to apply. Residual energy has not always been a concern during tree constructions or cluster formations (e.g., LEACH, DCTC, and [37, 38]). In Section 1.1, we have shown that node lifetime can be reduced if the residual energy is not being taken into the consideration. All of the above issues motivate us to construct an energy-aware aggregation Chapter 2 Related Work 26 tree with the appropriate selection of a root for collaboration. It is worth to mention that node scheduling algorithms are of the same importance as data aggregation in minimizing traffic and energy usage in WSNs. They simply put nodes to sleep and thus make no differences in the process of creating our lifetime-preserving tree. We only summarize them for the completeness of this thesis and interested readers should refer to the references for more details. In this chapter, we have described some previous work on routing, particularly Directed Diffusion, for WSNs. Some network aggregation techniques, such as DSC [28] and Data Funneling [4], and aggregated-related timing policies [29] were introduced. A summary of previous aggregation tree constructions (e.g., EADAT and DCTC) or cluster formations was also presented. This chapter ended by exploring some previous node scheduling algorithms (e.g., ASCENT and STEM) proposed in the literature. Chapter 3 The LPT Construction In this chapter, we begin our discussion on the construction of the Lifetime-Preserving Tree (LPT). We first present our network model under the considerations, the related definitions, and assumptions in Section 3.1. The details of the LPT construction problem are described in Section 3.2. We continue by investigating the use of spanning tree and an energy-aware variant of it, namely E-Span, on data aggregation in Section 3.3. Such trees are easy to construct and shall provide some insights on how different event sources should be arranged so as to collect and aggregate data reports in an optimal way. Next, we proceed to present our solution to the LPT construction problem by using a centralized approach in Section 3.4. Finally, a distributed implementation of the LPT construction algorithm for data aggregation in practical WSNs is presented in Section 3.5. 3.1 Network Model, Assumptions, and Definitions We consider a field of M randomly-deployed and identical sensor nodes. A number of K (K < M) sinks, randomly chosen among these M nodes, are requesting for data reports. A stimulus, triggering N (N < M) event sources around it, occurs at a random place in this field. We assume that these sources are interconnected to each other. In practice, an event may not trigger a set of connected source nodes. However, under such scenario, multiple independent trees will be constructed with each serving a disjoint set of event sources. Hence, for simplicity, we restrict ourselves to a set of N connected source nodes. We assume that data reports from each source are clock-driven upon event detection. Furthermore, these data are assumed to be collected at a dedicated tree root and sent to the distant sinks in a periodic manner. During data collection, nodes have the abilities to perform in-network aggregation of 27 Chapter 3 The LPT Construction 28 packets enroute to the tree root. We further assume that each node m (m e{l,2 ... MJ) awares of its energy, em. Node batteries are neither replaceable nor rechargeable. We finally assume that all nodes have an identical and fixed transmission range. We define a branch to be the route from a root node to a leaf node in a given tree. The following two terms are introduced: Branch energy - the minimum energy of all the non-leaf nodes in a given tree branch. Tree energy - the minimum branch energy of all the branches in a given tree. Let By denote the set of nodes along a given tree branch with y as the leaf node, and Ix be the set of nodes in a given tree rooted at node x. Mathematically, the branch and tree energies are calculated as: Branch energy for branch By = min {ei} (3.1) ieBy, i±y Tree energy for tree Ix= min {e:} (3.2) jefx,j*leafnode For example, the branch from nodes A to D (drawn dark) in Figure 3.1a and the tree (with the minimum-energy branch drawn dark) in Figure 3.1b shall both have energy of 3 Joules. a) B r a n c h e n e r g y b ) T r e e e n e r g y Figure 3.1: A n e x a m p l e t o d e s c r i b e b r a n c h a n d t r ee e n e r g i e s : a ) E n e r g y o f t h e b r a n c h f r o m n o d e s A t o D i s set t o 3 J, t h e e n e r g y o f n o d e B . b ) T r e e e n e r g y i s se t t o 3 J, t h e e n e r g y o f t h e b r a n c h f r o m e i t h e r n o d e s A t o D o r n o d e s A t o F. Chapter 3 The LPT Construction 29 3.2 Problem Formulation Given a number of Af connected source nodes with each source labeling n (n e {I, 2 . . . N}) and the knowledge of their own residual energy, en, our goal is to find a tree spanning all these sources and an appropriate tree root for data collection so that the functional lifetime of each source is preserved as much as possible. Recall from Section 1.1 that the time till the first link breaks in a given tree structure determines the lifetime of each source, and the term tree energy directly reflects this time. We hence tackle this problem by searching a tree that comprises the highest tree energy. In the literature, network lifetime has often been defined as either the time till the first or a set of nodes runs out of its energy [8, 31, 44, 45], or till the first loss of connectivity or coverage [46,47], or a combination of these [48]. A formal definition of network lifetime is in fact not very straight-forward and may depend on the application scenario in which the network is targeted at. However, none of these definitions deviate from interpreting network lifetime as the time before the network ceases to provide the type of service it is designed for. We therefore follow this convention, and define the branch energy as the minimum energy of all the non-leaf nodes in a given branch and define tree energy as the minimum branch energy of all the branches in a given tree. To better understand why we define them in this way, we point out that the time for an upstream link along a given branch to break directly depends on the energy of the parent on such a link. In other words, the time during which data from each source along this branch can arrive at the root will depend on the minimum energy of any parent along this branch. By using the same analogy, the time during which data from all sources can arrive at the root without having to concern about broken link repairs and tree reconstructions will depend on the minimum energy of any branch, or equivalently that of any parent, in a given tree. The only question we are left with lies on how to select an appropriate tree root and the branch leading to each other source, such that the energy of this tree is Chapter 3 The LPT Construction 30 maximized. To resolve this problem, we explore the highest-energy branch from each source to a root by first assuming that every source node is a root. This generates a total of N unique trees with each being rooted at a distinct source node. We continue by comparing the energy of these trees and only employ the one with the highest tree energy for data collection. Our LPT construction problem is thus formulated as follows: Given: N connected source nodes and the knowledge of their own residual energy, e„. Define: Pxy to be the set of possible routes, with each labelingp, from nodes x to y. brEijk to be the energy of a branch k leafed at node i and rooted at j, k e Ptj. treeEn to be the energy of a tree rooted at node n. Goals: construct a tree rooted at node r such that 1. treeEr ~£treeEn V n <=N,n & subject to the condition that 2. brE^ ^brEiiriP V i eN, V p e Pi<n p &k Figure 3.2: Problem formulation. Explore the highest-energy branch from each source to the root by first assuming that every source is a root. Then, select the one with the highest tree energy for data collection. 3.3 The Energy-Aware Spanning Tree (E-Span) Before starting to describe our LPT algorithm, we outline the basic spanning tree protocol [49] followed by presenting an energy-aware variant of it, namely E-Span. We believe that E-Span shall provide some insights on how different event sources should be arranged in the lifetime-preserving tree and is likely to satisfy our objectives for only a few participating source nodes. It is comparatively easy to implement and will later be compared with our LPT algorithm. 3.3.1 The Spanning Tree Protocol A spanning tree is a graph that spans all the nodes as vertices and contains no cycles. The tree Chapter 3 The LPT Construction 31 is structured in the way that the node with the smallest identifier is chosen as the root. At the same time, all other nodes are connecting to this selected root via the shortest-path route. The protocol requires each node to exchange configuration messages in a format that contains the identifier of itself, that of its selected root, and the distance (in hops) to this selected root. Each node updates its configuration message upon identifying a root with a smaller identifier or the shortest-path neighbor. Furthermore, the neighbor for which the shortest-path configuration message comes from is chosen as the parent of a node whenever it is detected. Node identifier is used to break ties if necessary. The above descriptions are being translated Define: r„ to be the ID of the wot selected by node n dn to be the shortest-path distance from r„ to node n gn = (n, rm dj to be the message sent by node n p„ to be the ID of the parent selected by node n trecv.nP be the time node n received the message from its parent Initialize: g„ to (n,n,0) Vn eN pnton V n e Af tremn tO 0 V « e N GetSpan (node ID n, time t, timeframe T) 1 ifn is not an event source, 2 return 3 else {single-hop broadcast g„ and start a timer P that expires every Tsec 4 while true, 5 if timer P expires and (r„=nort> tmc^+T), 6 set g„ to (n, n, 0) 7 set p„ton 8 set tKmn to t 9. single-hop broadcast g„ 10 if receiving a message gifrom node i, 11 ifri< rn, or fr, = rn and < d„), or (ri = r„, dt+l = dn, and i <Pn), 12 setg„ to (n, rt, di+1) 13 setpn to i 14 Set trecvn to t 15 single-hop broadcast g„ and restart timer PJ Figure 3.3: The distributed spanning tree protocol, which creates a graph covering all source nodes as vertices and contains no cycles. The node with a smallest ID is selected as root. Each other node picks the neighbor for which the shortest-path configuration message comes from as its parent, n is the node that runs the GetSpan algorithm and n e N. Chapter 3 The LPT Construction 32 into the GetSpan algorithm depicted in Figure 3.3 below. Note that single-hop broadcast refers to the operation of sending a packet to all single-hop neighbors. Lines 1 and 2 restrict the message exchanges to be within the event region. Line 3 starts the exchange and an additional timer for tree maintenance. Line 4 triggers an infinite loop. Lines 5 to 9 allow a root to periodically generate a message every T seconds and reset a node when it starts to lose its shortest-path neighbor. Lines 10 to 15, on the other hand, update the node itself and forward the message whenever a node identifies a root with a smaller identifier or a better shortest-path neighbor. For example, the set of source nodes depicted in Figure 3.4a will create a tree of the form shown in Figure 3.4b. Unfortunately, failure to consider the node's residual energy results in this tree having the lowest energy of 3 Joules. Furthermore, the node that is equipped with the minimum energy, i.e. node 1, is chosen as the root and is attached to three other child nodes. When the tree is deployed for data collection among these sources, the rate at which node 1 dissipates its energy is quite high and thus the time to the first node death is minimized. We hence make some changes and present an energy-aware variant of this protocol, namely E-Span. a) Connectivity diagram b) Spanning tree configurations Figure 3.4: An example of the spanning tree protocol: a) Connectivity diagram for a set of given sources, b) The spanning tree configurations will have node 1 with energy 3 J chosen as the root, resulting in the lowest tree energy of 3 J. Chapter 3 The LPT Construction 33 a) Connectivity diagram b) E-Span configurations Figure 3.5: An example of the E-Span protocol: a) Connectivity diagram for a set of given source nodes, b) The E-Span configurations will have node 8 with energy 10, J chosen as the tree root, still resulting in the lowest tree energy of 3 J. 3.3.2 The Energy-Aware Spanning Tree Protocol As with the conventional spanning tree, E-Span is a graph that covers all the nodes as vertices and contains no cycles. All other nodes are still connected to the selected root via the shortest-path route. Since the root, besides collecting data, is also responsible to coordinate the routes with distant sinks, the node with the highest energy level is now chosen as the root. Moreover, each other node is given with the choice to select its parent as the highest-energy neighbor for which the shortest-path message comes from. By using the same set of nodes as an example, the tree will now have node 8 chosen as the root and all other nodes are still talking to node 8 via the shortest-path route (depicted in Figure 3.5). Specifically, node 6 which finds itself having two shortest-path neighbors of nodes 2 and 4 will in fact attach itself to the higher-energy one (i.e. node 2). The reason is to allow a node that has more available resources to be selected as a parent node for data collection. Details of the implementation are summarized in Figure 3.6. The configuration message now involves 3 additional parameters: the residual energy of the node that sends the message, that of the node's chosen root, and the node's chosen parent. As with the GetSpan algorithm, lines 1 to 3 start the message exchanges and restrict these exchanges to be within the event area. Lines 4 to 7 allow a root to periodically generate a message every T seconds and reset a node that loses connection with its parent. Lines 8 to 11 update the list of child nodes for the receiving node. Lines 12 to 16 update the message when a node receives an energy update Chapter 3 The LPT Construction 34 Define: en to be the residual energy of node n r„ to be the ID of the root selected by node n e(rj to be the last-updated energy of the root selected by node n d„ to be the shortest-path distance from rn to node n pn to be the parent selected by node n s„ = (n, en, r„, e(rj, pn, d„) to be the message sent by node n e(pn) to be the last-updated energy of the parent selected by node n tremn to be the time node n received the message from its parent childListn to be the list of child nodes for node n Initialize: Change (n, en, n, en, 0,0) V n eN GetESpan (node ID n, node energy en, time t, timeframe T) 1 ifn is not an event source, 2 return 3 else {single-hop broadcast s„ and start a timer P that expires every Tsec 4 while true, 5 if timer P expires and (r„=nort> tKCVf„+T), 6 Change (n, e„, n, e„, 0, t) 7 single-hop broadcast sn 8 if receiving a message Sjfrom node i, 9 ifPi = n, 10 add i to childListn 11 else remove ifrom childListn 12 ifn = r„, 13 if ft = Pn)> o r (di+1 < dj, or (dj+1 = d„ and e, > efpj), or (dj+1 = dn, e,- = e(pn), and i < pj, 14 Change (i, e„ rt, e(rj), dt+l, t) 15 else if (e(rj > e(r„)) or (e(rj = e(r„) and rt < r„), 16 Change (i, e„ r„ efr^ ), dt+l, t) 17 if(en > e(rj) or (e„ = e(r„) and n < r„), 18 Change (n, em n, en, 0, t) 19 single-hop broadcast s„ if a change applied) Change (node x, energy e„ nodey, energy ep distance d, time t) 1 set s„ to (n, e„, y, ey, d) 2 set p„ to x 3' set e(p,J to ex 4 Set trecvn to t Figure 3.6: The distributed E-Span protocol, which creates a graph covering all source nodes as vertices and contains no cycles. The node with a highest energy is selected as the root. Each other node picks the highest-energy neighbor for which the shortest-path configuration message comes from as its parent, n is the node running the GetESpan algorithm and n eN. Chapter 3 The LPT Construction 35 from its parent, or when it detects a better shortest-path neighbor or a higher-energy root. Lines 14 and 15 compare the receiving node with the root, and line 16 broadcasts the message if there is a change. Again, single-hop broadcast is referred to the operation of sending a packet to all single-hop neighbors. Unfortunately, without knowing the complete set of connectivity provided by all sources, some nodes in E-Span still traverse to the root through routes with a lower branch energy. As a result, each source can more often be involved in tree reconstruction, implying that a greater portion of its available energy are consumed in repairing broken tree links over the course of its lifetime. As an example (see Figure 3.5), nodes 3 and 5 could have been attached to nodes 6 and 3, respectively, resulting in tree energy of 7 rather than 3 Joules. In addition, the energy dissipation rates for nodes 1 and 7 would have been lower if these changes are made. In other words, without making these changes, the functional lifetime of the two are shorter due to the additional energy cost involved in the tree reconstruction. This is clearly one issue we try to resolve, if possible, when we construct the LPT. We however believe that the chance for it to happen is rather rare for a small number of participating sources. When this number starts to increase, a technique that is different from E-Span is required. We shall now present our LPT construction algorithm. 3.4 The LPT: Centralized Approach In this section, we proceed to the discussion of the lifetime-preserving tree construction using a centralized approach. We assume that the complete knowledge of the event region is given, including the connectivity and residual energy of all the source nodes, prior to the start of the algorithm. The tree generated can later be used to validate the correctness of the corresponding tree constructed by the distributed approach. One way to obtain a lifetime-preserving tree is to directly run an extensive search at Chapter 3 The LPT Construction 36 every node and then compare various tree energy. However, this approach has the scalability problem when the network starts to grow or becomes dense. We hence tackle the issue in a completely different way. Recall that the lifetime-preserving tree requires a root (initially unknown) to collect data from each other node via routes with the highest branch energy, subject to the condition that these routes do not create loops. Moreover, the tree has an energy that directly depends on the minimum residual energy of all the non-leaf nodes. If there exists a way to identify this minimum-energy node, which represents the bottleneck to the network, it will then be easy to. determine what the highest tree energy will be. To illustrate the above descriptions, consider the set of nodes in Figure 3.7a. Any source node can either be a root, parent, or leaf. By assuming that node 5 is a root, the protocol must have each other node enroute to this root through either nodes 7 or 3. However, the tree must have node 6 as a parent for some nodes in c) Node 5 being a parent d) Node 5 being a leaf Figure 3.7: An example of the bottleneck node. No matter what the role of node 5 is, node 6 has to be a parent for some nodes in the network if the tree energy has to be the highest: a) Connectivity diagram for this particular event area, b) If node 5 is a root, node 6 has to collect data from nodes 2 and 4. c) If node 5 is a parent, node 6 again has to forward data for both nodes 2 and 4. d) If node 5 is now a leaf, node 6 has to collect data from node 3. Therefore, the tree energy cannot be greater than the energy of this bottleneck node. Chapter 3 The LPT Construction 37 the network if the tree energy has to be the highest (depicted in Figure 3.7b). If node 5 is now a parent, node 6 again has to forward data for some nodes, for example nodes 2 and 4, in the network (Figure 3.7c). Finally, if node 5 is a leaf, the protocol must have node 3 to forward its data to some root via either nodes 1 or 6. By using the same argument, node 6 again has to be a parent for data collection from node 3 (shown in Figure 3.7d). We therefore call node 6 as a bottleneck node for this particular network topology, since there are no better ways to route around this node, and the tree must have energy less than that of this node. Having understood the concept of a bottleneck, the question lies on how to identify this node and coordinate the given set of network connection such that a tree is obtained with this node being configured as the minimum-energy non-leaf node. To address this issue, we begin by arranging nodes in ascending energy levels. Starting from the least-energy node, we test if-the removal of all network links to this node except that from its highest-energy neighbor will disconnect the existing graph. If so, the bottleneck node is found and there are no better ways than to collect data via this node. The removed links are thus restored, and any tree rooted at one of the nodes in the remaining set shall have the energy as that of this chosen node. If not, the removed links do not contribute to the construction of the lifetime-preserving tree and we shall move on to the next node. Note that the energy of the highest-energy neighbor has to be greater than that of the node under the test. When such neighbor does not exist, the node has to be a parent for at least one of its neighbors, and thus all the links are preserved. In the case when there are more than one neighbors that have equal highest energy, either one can serve as the parent for collecting data from the node under the test without affecting the tree energy. Node ID is thus used to break this tie. Finally, when we come to the last node, i.e. the highest-energy one, we conclude that there is no bottleneck node for this particular topology and any tree rooted at this last node, on the existing graph, can have the highest tree energy. To illustrate the descriptions, consider two examples. Figure 3.8 depicts the centralized LPT search during which a bottleneck is found when the link from nodes 6 to 2 is removed. In Chapter 3 The LPT Construction 38 other words, node 6 has to be a parent for some nodes in the network. Any tree rooted at one of the nodes in the remaining set, i.e. nodes 2, 3, 5, 6, or 8, will therefore have the highest tree energy as that of this bottleneck node. Figure 3.9 depicts another example of the search where no bottleneck node is found. The reason is that those links that are removed do not contribute to -the formation of any lifetime-preserving tree and therefore any tree rooted at the highest-:) Node 4 under test d) Bottleneck found Figure 3.8: An example to search the lifetime-preserving tree in a centralized manner. Starting from the least-energy node, we test if the removal of all the links to this node except that from its highest-energy neighbor will disconnect the existing graph. For this topology, node 6 is hence found as the bottleneck. Any tree rooted at nodes 2, 3, 5, 6, or 8, on the existing graph will have the highest tree energy of 7 J. a) 4-node topology b) Node 1 under test c) Node 4 under test d) Bottleneck not found Figure 3.9: An example to search the lifetime-preserving tree in a centralized manner. Since removals of the links, except that from the highest-energy neighbor, to the source under any test does not disconnect the existing graph, there is no bottleneck for this particular network topology. Hence, any tree rooted at node 2 will be the lifetime-preserving tree. Chapter 3 The LPT Construction 39 energy node, i.e. node 2, will have the highest tree energy. The algorithm is summarized in Figure 3.10. Line 1 sorts all nodes in ascending energy levels. Lines 2 and 3 compute the highest-energy neighbor for the node under the test. Recall that the energy of this neighbor has to be greater than that of the node. When such a neighbor exists, lines 4 and 5 remove and temporarily store all links to the node except that from the highest-energy neighbor. Lines 6 to 10 restore the removed links, clear the storage, and compute a tree by running Dijkstra's algorithm [50] at one of the nodes in the remaining set when a bottleneck is found. Tree energy is set to the energy of the bottleneck node at this time. In fact, the reason to run the Dijkstra's algorithm is to ensure that the remaining set of network connections does create a tree and contain no loops. Lines 11 to 12 compute a tree Define: node„ to be the node with n least energy e(node„) to be the energy of node„ ( nodenmax to be the highest-energy neighbor of node„, subject to the condition that e(nodenmax) > efnodej linkxy to be the bi-directional link, if it exists, between nodes x and y treeEn to be the energy of a tree rooted at node n I to be a set, initially empty CentralhedLPT (connectivity and energy matrices) 1 sort nodes in ascending energy level 2 forn = 1 to N, n++ 3 getnoden,max 4 ifnode„max exists, 5 remove linkni and store i in I V i e N, i ^nodenmax, i &i 6 if the graph is not connected, 7 restore linknJ V / e / and clear I 8 set nodet to be the root and run Dijkstra s algorithm on nodek where k is any one number from ntoN 9 set treeEk to be e(node„) 10 return 11 set nodeN to be the root and run Dijkstra's algorithm on node^ 12 compute treeEN using Equation (3.2) for the tree rooted at node^ Figure 3.10: The centralized LPT algorithm, which creates a lifetime-preserving tree spanning all source nodes as vertices and contains no loops. The Dijkstra's algorithm is used to create a tree and ensure that the remaining set of network links does not contain loops. Chapter 3 The LPT Construction 40 again by running Dijkstra's algorithm at the highest-energy node, and search the tree energy by using Equation 3.2 when no bottleneck node exists in the network. 3.5 The LPT: Distributed Approach Given a number of N source nodes with each node labeling n (n e{\, 2 ... Nj) and the knowledge of their own residual energy, e„, our goal is to construct a tree spanning all these sources and select an appropriate root for data collection, in a distributed way, such that the energy of the tree is maximized. We take the approach of exploring the highest-energy branch from each source to a root, by first assuming that every source node is a root, using a method similar to Reverse-Path Forwarding (RPF) [51]. This generates a total of ./V unique trees with each being rooted at a distinct source node. We continue by comparing the energy of these trees and only employ the one with the highest tree energy for data collection. In the following sub-sections, Section 3.5.1 describes the procedure to explore the highest-energy branch among all the sources in a given tree root. In Section 3.5.2, we construct N trees with each tree rooted at a distant source by incrementally attaching any tree branch explored from the previous section. Section 3.5.3 compares these trees and employs the one with the highest tree energy for data aggregation. Section 3.5.4 synthesizes the design and presents a concrete algorithm for practical implementation. 3.5.1 Exploring the Highest-Energy Branch from every Source to any Root As previously mentioned, the time during which data from each source along a given branch can actively be received by the root depends on the minimum energy of any parent along this branch. In order to maximize this time for any pair of root and source, the connectivity between them will first have to be explored prior to getting the highest-energy branch connecting these two nodes. Let Pxy denote the set of possible routes, with each labeling p, J Chapter 3 The LPT Construction 41 from nodes x to y and brEjJik be the energy of a branch A: leafed at node i and rooted at node j. Note that k sP ( i /. We therefore wish to get a branch b for every pair of source s and root r such that: brE^ZbrE^ \/p ePs,„p *b (3.3) To do this, we employ RPF which requires each source s to initiate a configuration message in a format that contains its energy information. When a source receives this message, it appends its energy information and broadcasts the message only if it has not seen this message or if it has previously forwarded the message containing lower branch energy. Otherwise, it simply discards the received packet. Eventually, various copies of the initiated message will traverse through various different routes p and only the better ones will arrive at the root r. Define eidn to be the pair of energy level and ID of a node labeling n and brListiJk be a list containing the eid for the message initiating node i up to the last receiving node j via a route k with branch energy brEiJk, Note that brEijik can be calculated using Equation (3.1). Therefore, brList^k shall have the format of a list as follows: brListjj>k: eidt eidx eidy eidj (3.4) where nodes x and y are the intermediate receiving nodes for the message initiated by node j. Note that when node j receives the list brList^p from node y via some route p, it is as if node j is a root and node i is a leaf for the branch between nodes j and i. Our descriptions can thus be translated into the ExploreBranch function shown in Figure 3.11. Again, single-hop broadcast refers to the operation of sending a packet to all single-hop neighbors. Line 1 allows each source to initiate its control message. Lines 2 to 5 update, store, and broadcast the message when the receiving node does not recognize the initiating source. Lines 6 to 9 reset its stored list in addition to the above three actions whenever the receiving node detects a higher-energy branch. Chapter 3 The LPT Construction 42 ExploreBranch (node ID n, node energy e j / create brListnn. by appending eid„ and single-hop broadcast brListnn 2 while receiving brListijkfrom node j (k s Ptj, i e N, i 3 ifn has not seen the message initiating node i, 4 append eidn to the head ofbrListijj,, and update brEinp (p zPJ 5 store and single-hop broadcast brList^p 6 else if min {en brEyjJ > the stored brEi„q (q e Pin), 7 remove the stored brListintq and brE^nq 8 append eid„ to the head of brListjjj and update brEinp (p 9 store and single-hop broadcast brListi>np Figure 3.11: The ExploreBranch function, which explores the highest-energy branch from every source to any tree root using a method similar to RPF. n is the node running this function and n e N. e) Route dropped at node 7 f) Route dropped at node 1 Figure 3.12: An example to search the highest-energy branch between nodes 5 and 8. There are 6 possible choices in which only the route in Figure 3.12d will have the highest branch energy of 7 J. The messages traveling on the last two routes are dropped since they do not carry higher branch energy, subject to the condition that nodes 1 and 7 have previously forwarded a similar message. Chapter 3 The LPT Construction 43 To illustrate the ExploreBranch function, consider the set of sources shown in Figure 3.12. For simplicity, we will concentrate on the control message exchanges between a source of node 5 and a root of node 8. First, the function requires node 5 to initiate a control message containing its eid. There are six possible routes the message could have been possibly traveled (depicted in Figure 3.12a to Figure 3.12f). Among these routes, only nodes 7 and 1 will drop the messages with the routes through nodes 1 and 3, and node 7 respectively, subject to the condition that they have previously forwarded the messages, containing lower branch energy, initiated by node 5. The reason to drop these messages is to limit the number of control message exchanges and ensure that only the better routes will traverse through the nodes. Node 8, upon receiving the other 4 routes, will be able to identify that the route from node 5 through nodes 2, 6, and 3 indeed has the highest branch energy of 7 Joules. 3.5.2 Constructing a Tree Spanning all Event Nodes for every Source We now proceed to construct N trees with each tree rooted at a distant source by incrementally attaching any branch explored in the last section. Each source has an initial tree structure that only comprises the node itself. In order to construct a tree for each source that spans all event nodes, each source has to incrementally update its existing tree structure upon receiving any branch with an unknown initiating node. Note that the energy of the received branch directly determines the energy of the updated tree. To ensure that each tree carries the highest energy, the tree is also updated whenever the receiving node identifies a message with a higher branch energy. To illustrate the descriptions, consider Figure 3.13. For simplicity, we only concentrate on the tree construction for node 8. Initially, node 8 has a tree structure that only comprises itself. Upon receiving the messages initiated by nodes 7, 1,4, 2, and 6 (shown in Figures 3.13a to 3.13e respectively), node 8 updates its tree to a structure depicted in Figure 3.13f. Now, when node 8 receives the message initiated by node 6 through node 2 (Figure 3.13g), it Chapter 3 The LPT Construction 44 a) Highest-energy branch from node 7 c) Highest-energy branch from node 4 10 J e) Lower-energy branch from node 6 7] -v>9 j g) Highest-energy branch from node 6 i) Highest-energy branch from node 5 b) Highest-energy branch from node 1 101 5 > \ „ „ . 4J n ^ y > J f3J f . 7J - @ 9 j d) Highest-energy branch from node 2 10 J f) Tree constructed by node 8 h) Highest-energy branch from node 3 j) Tree constructed by node 8 Figure 3.13: An example to construct a tree for node 8. Each node initiates its control message and node 8 incrementally updates its tree upon receiving any higher-energy branch initiated from them, resulting in a tree spanning all sources yet with the energy of 7 Joules. Chapter 3 The LPT Construction 45 a) Branch from node 5 b) Branch from node 6 c) Loop detected Figure 3.14: An example of how a loop could have been created if the root does not compare the existing routes with the newly-arrived one. In the above figures, the arrival of the route initiated by node 5 does not necessarily imply that the route to node 6 for what node 8 has seen so far is also from node 2. Loop is hence created as a result. identifies that the message carries a branch energy of 8 Joules. This is 2 Joules greater than what it has for node 6. By replacing the old branch with the newly-received one, node 8 will be able to increase its tree energy from 6 to 8 Joules. Finally, by receiving the messages from nodes 3 and 5 (Figures 3.13h and 3.13i), node 8 will create a tree spanning all sources yet with the energy of 7 Joules. Besides attaching new branches, each source is also responsible for preserving the loop-free property of its tree during the update. In fact, some cares need to be taken in order to reject a branch that actually violates this property. Consider the same set of nodes with the energy of node 4 being changed to 8 Joules. The arrival of the branch shown in Figure 3.14a does not necessarily imply that those initiated by any parent on this branch are also received via node 2. By taking node 6 as an example, its initiated message could have first been received via node 4 by node 8 (Figure 3.14b). If the branch in Figure 3.14a is attached to the tree of node 8, a loop around nodes 8, 4, 6, and 2 (shown in Figure 3.14c) will be created. In other words, node 6 will spend twice its energy to transmit any data it generated or received. Therefore, to avoid creating loops and to reduce energy usage, each node always has to reject a branch when the already-attached ones for each parent on this branch do not match with it. We define the term initiator to be the source which initiates the message and treen be the tree created by node n. treen should have the format of a table as depicted in Table 3.1. In Chapter 3 The LPT Construction 46 other words, tree„ is where the branches are stored by the receiving node n. Also let Jj denote the set of initiators in treej and treeEk be the energy of treek. treeEk can be calculated by using the following equation: treeEk = min (brE- k } where psPk (3.5) JeJk Our description can be translated into the NoLoop function shown in Figure 3.15. This function takes the received branch as an input and tests if attaching it to the tree will not create a loop. Line 1 removes the message initiator i so that the branch only contains a list of parents. Line 2 ensures the already-attached branch for node k stored in treen matches with the route through which the received branch travels. Note that the function always accepts a branch of size less than 3 since a loop can only be created by adding a branch of size greater than 2 to its existing tree. NoLoop (node ID n, branch brList^iJ 1 remove eidjfrom brListjjj, to get a new brListiJiP where I is the node at the tail ofbrListiJp andp e PQ 2 if number of eids in brList\jP < 2 or (brListijj, \\ eid^ = brListinp (stored at tree,), 3 return true Figure 3.15: The NoLoop function, which takes the received branch brListiJk as an input and test if attaching it to the tree in tree„ will not create a loop, n is the source running this function, i is the message initiator, and j is the node sending this branch, n, i,j s A'and k e Pjj. Table 3.1: The format of a tree for node n (pa e Pa„, pb s Pb„, and pc s Pcn) Initiators Branches Branch energy node a brLista,„iPa brEan pa node b brListbi„pb brEb,„iPb node c brListc^pc hrF Chapter 3 The LPT Construction 47 3.5.3 Searching a Lifetime-Preserving Tree for every Source Since each source n carries its unique tree structure stored in treen, the protocol requires every source to broadcast its tree and select the one with the highest tree energy for data aggregation among these nodes. Our objective is to create a tree rooted at node r such that: treeEr ^treeEn V / i eN,n& (3.6) Note that treeEr and treeE„ can both be calculated using Equation 3.5. In fact, there can have multiple different trees that yield the same tree energy. To break such ties, a number of other properties can be compared. For examples: tree depth, root energy, root ID, and node degree. Tree depth can be used to minimize the data latency. Root energy can be used to maximize the available resource of the root for possible tasks such as route coordination to distant sinks. Node degree can be used to minimize the power dissipation rate. In this work, we limit ourselves to use tree depth, root energy, and then root ID to break ties whenever necessary. Further work is required to evaluate the performance of the best tree selection by using other parameters. To illustrate the descriptions, consider Figure 3.16. By having each participating node to broadcast its selection, there will be 8 trees under the comparison. Among them, only the ones constructed by nodes 2, 3, 5, 6, and 8 comprise the highest tree energy of 7 Joules. We hence wish to select the tree created by node 3 as our lifetime-preserving tree and node 3 as our root since this tree has a lower tree depth than that by nodes 5 and 8, and a higher root energy than that by nodes 2 and 6. We define lptt to be the lifetime-preserving tree that a node i currently selects and IptE/ be the energy of lptt. Note that lpt„ initially equals to treen for all sources n. The SearchLPT function shown in Figure 3.17 describes the procedures to search a lifetime-preserving tree for each source. Line 1 allows the source to broadcast its initial selection. While a message is received from its neighboring node with tree information (line 2), lines 3 to 5 update the Chapter 3 The LPT Construction 48 selection of the receiving node if the received tree is better. Line 6 rebroadcasts the selection after the update. Note that we have explicitly assumed that each node has already created a tree spanning all event sources (i.e. each tree has N rows) before the function starts. Hence, the first two lines of the BetterTree function are always skipped. In practice, the number of event sources is not known a priori and each node will simply run a new SearchLPT function g) Tree constructed by node 7 h) Tree constructed by node 8 Figure 3.16: The set of trees created by the sources in the event region. Only the one with the highest tree energy is employed for data aggregation among these nodes. By using the SearchLPT function shown in Figure 3.17, all the sources will select the tree created and rooted at node 3 for aggregation. Chapter 3 The LPT Construction 49 whenever it detects a new initiator. To ensure that only the selections with N number of rows in them are compared, we include the first two lines of the BetterTree function in order to filter out all outdated trees. In the following section, we will proceed to describe the implementation in practical WSNs. SearchLPT (node ID n) 1 single-hop broadcast lpt„ 2 while receiving Iptifrom node i (i ^n), 3 if BetterTree (Ipt), 4 , delete lpt„ and copy lptt to lptn 5 calculate lptE„ by using Equation (3.5) 6 single-hop broadcast lpt„ BetterTree (Ipt Ipt*) 1 if § rows in lptx > # rows in lpt„. 2 return true 3 if (# rows in lptx = # rows in IpQ and (lptEx > IptEJ, 4 return true 5 if (# rows in lptx = # rows in IpQ, and (lptEx = lptE„), and (tree depth oflptx < tree depth oflpt„), 6 return true 8 if (# rows in lptx = # rows in IptJ, and (lptEx = IptE^), and (tree depth of Iptx = tree depth oflptj, and (ex> e„), 9 return true 10 if (# rows in lptx = # rows in IptJ, and (lptEx = lptE„), and (tree depth oflptx = tree depth oflpt„), and (ex - e„), and x < n, 11 return true 12 return false Figure 3.17: The SearchLPT function, which searches the lifetime-preserving tree for each source, n is the node running this function, n eN. The BetterTree function takes the received tree as an input and returns true if it has more entries or its tree energy is greater than that of what node n currently has. Tree depth, root energy, and then root ID are used to break ties whenever necessary. lptEx is the energy of the tree lptx which can be calculated using Equation (3.5). Tree depth of a tree lptx is the maximum number of eids of all the branches stored in lptx. 3.5.4 Implementing the LPT Algorithm in Practical WSNs Having explained the overall design of the LPT construction, we now proceed to the Chapter 3 The LPT Construction 50 discussion of the control packet structure and any other implementation-related issue. According to what we have described earlier, a control packet should only comprise a brList and an Ipt for the ExploreBranch and SearchLPT function respectively. However, from our experiences, failure to receive a brList can lead to a tree that does not comprise the highest tree energy. We therefore choose to include the entire tree, i.e. a table containing all discovered initiators, brLists, and brEs, so as to maximize the chance of a neighbor successfully receiving each brList stored in this table. An additional restart flag for which we will describe its usage in the following paragraph is also included in the message. We define restartt to be a Boolean variable stored on node i and mn to be the control message sent by node n. The control message nij should have the format (restartj, treej, Iptj). Note that treej are Iptj can represent two different trees, treej is the tree created by node j (Section 3.5.2) whereas Iptj is the lifetime-preserving tree selected by node j (Section 3.5.3). When the algorithm converges, each source « should have an identical lifetime-preserving tree stored in lptn. Table 3.2 describes the packet structure of the LPT control message. Recall that Directed Diffusion [19, 20] is chosen as our routing platform. All control messages are hence wrapped with Diffusion packet structure. The 24-byte header contains information such as destination ID, source ID, packet number, and packet length etc. The 12-byte scope and type attributes control how Diffusion packets are being processed by the Diffusion core programmed inside each node. The 12-byte control type attribute describes the type of control messages that are being exchanged in the network. Finally, 12 bytes plus a space of variable size are allocated to encode all the LPT control information (i.e. restart,,, treen, and lpt„) for any particular network node n. Specifically, the first 12 bytes are required for the LPT control message attribute since 4 bytes are reserved for the restart whereas 8 bytes are used to specify that the LPT control message is of type BLOB. An additional space of variable size is also required since the sizes of each tree and Ipt are initially unknown. However, 4 bytes are allocated for each initiator or brE (see Table 3.1) and 8 bytes are reserved for each eid in each brList (see Equation (3.4)). Chapter 3 The LPT Construction 51 Table 3.2: The packet structure of the LPT control message 24-byte Diffusion header 12-byte Diffusion scope attribute 12-byte Diffusion type attribute 12-byte control type attribute 12-byte plus a space of variable size binary interpretation of LPT control message attribute To ensure that data from each source can constantly arrive at the root via its parent, some maintenance is required to reconstruct another tree whenever a parent runs out of its energy. The protocol requires the root to periodically broadcast a hello message. All other nodes upon receiving this message from its parent shall simply broadcast its hello message to the network. Note that only the upstream connection towards a parent is scanned since it is the direction where data are sent. A timer that expires every T seconds and runs on every source is used to periodically scan the connectivity to its parent. Whenever a node loses connection with its parent, the restart flag in its control message is set on. Any other nodes that receive this flag with its flag set off will have to restart the entire process. In this way, a new tree with the broken link being taken into considerations will then be reconstructed. A typical value of T is 25 seconds. We define h„ to be the hello message sent by node n and tKCVj be the time node i last received the hello message from its parent. Also, let Jj denote the set of initiators in treej. Figure 3.18 summarizes our algorithm. Again, single-hop broadcast refers to the operation of sending a control packet to all single-hop neighbors. Lines 1 and 2 restrict the messages to be exchanged within the event area. Line 3 broadcasts the initial control message and starts the maintenance timer. Line 4 creates an infinite loop. Lines 5 and 6, on the other hand, update the maintenance timer whenever a message is received. Since a node does not know where its parent is during the initial tree constructions, the node simply refreshes this timer upon receiving this message. Line 7 resets a node and restarts another round of tree constructions Chapter 3 The LPT Construction 52 Initialize: resettree„andlpt„ V n eJV create and append brList„t„,. to treen and lptn V n e N set restartn to be true V n e N DistributedLPT (node ID n, node energy e„, time t, timeframe T) 1 ifn is not an event source, 2 return 3 else {single-hop broadcast m„ and start a timer F that expires in Tsec 4 while true, 5 if receiving a control message mj from node j, 6 restart timer F 7 8 re-initialize if restartj is true and restartn is false for each brListij^ in treej with i e Jj and k e Ptj, 9 if NoLoop (brListjjik), 10 if initiator i ofbrListij* not found in treen, 11 append eid„ to brListijj, and update brEinp (p 12 add brListi„iP and brEinp to tree„ 13 calculate treeEn using Equation (3.5) 14 else if min {en, brEiJik} > brEUn,q (q e PtJ, 15 remove brListit„iq andbrEinqfrom tree„ 16 append eid„ to brListjjj, and update brEiinp (p 17 addbrListinp andbrEinp to tree„ 18 calculate treeE„ using Equation (3.5) 19 if a change applied to treen and BetterTree (treen) 20 delete lpt„ and copy treen to lpt„ 21 calculate lptEn using Equation (3.5) 22 if BetterTree (Ipt), 23 delete lpt„ and copy Iptj to lpt„ 24 calculate treeEn using Equation (3.5) 25 if a change applied to either tree„ or lpt„ 26 settKCVf„ to bet 27 update arid single-hop broadcast m„ 28 if timer F expires, 29 set restartn to be false 30 ifn is the root of the tree in lpt„, 31 single-hop broadcast h„ 32 else ift > tKCV,„+T, 33 re-initialize and single-hop broadcast m„ 34 if receiving a hello message hj from node j, 35 ifj is the parent of n in lptn, 36 set tnmn to be t and single-hop broadcast h„) Figure 3.18: The distributed LPT algorithm, which creates a lifetime-preserving tree spanning all source nodes as vertices and contains no loops, n is the node running this algorithm and n e N. Chapter 3 The LPT Construction 53 upon receiving a restart flag. Note that this line is only processed when a broken upstream link is detected by the transmitting node. Lines 8 to 18 correspond to the ExploreBranch function we have described in Section 3.5.1. Each node scans the brLists discovered by the transmitting node and updates its corresponding table entry if a scanned brList is new or carries higher branch energy. Note that the NoLoop function described in Section 3.5.2 is used in line 9 to ensure that the attachment of any scanned brList to the existing tree structure of the receiving node does not create a loop. The tree energy is also updated in both lines 13 and 18 by using Equation (3.5). Lines 19 to 27 correspond to the SearchLPT function described in Section 3.5.3. One major difference is the additional comparison between the Ipt and the tree that the receiving node has just updated (lines 19 to 21). The reason is to ensure the LPT that a node selects is always better than the tree it has created even after an update. Lines 22 to 24 replace the LPT with that from the transmitting node if the latter is better. Lines 25 to 27 update and broadcast the control message if a change is applied. Lines 28 to 36 correspond to the tree maintenance. Particularly, lines 30 and 31 broadcast the hello message if the node is a root when the maintenance timer expires. Lines 32 and 33 reset a node and inform all neighbors when the node loses connection with its parent. Finally, lines 34 to 36 allow a non-root node to transmit its hello message upon receiving that from its parent. Our algorithm has a complexity of 0(N2) since a node needs to scan at most N brLists upon receiving any control message (line 8) and to search at most Actable entries in either updating treeE or IptE (lines 13, 18, 19, 21, 22, and 24). All other lines can be executed in a constant number of iterations. 3.6 Discussions Our work has the same objective with EADAT [30], MLDA [31], DCTC [36], and the work in [37, 38]. Specifically, an aggregation tree that spans all event sources is constructed in order Chapter 3 The LPT Construction 54 to combine the reports sensed by them. Furthermore, the tree has a dedicated root for which data from various event sources are gathered. EADAT is similar to our scheme in that nodes with higher energy have a higher chance of becoming aggregating parent nodes. Both HEED [39] and EADAT are also similar to our approach in that residual energy are being considered in the cluster formation/tree construction, thereby enhancing the likelihood of distributing the loads of aggregation on higher-energy nodes. In contrast, EADAT differs from our approach in that timers are being extensively used. The result can be a long waiting time for the tree construction (Section 2.5.1). Furthermore, as with MLDA and the work in [37, 38], EADAT requires the prior knowledge or support from a given root (or base station) for the tree construction. Our scheme, on the other hand, does not require the root to be any particular event node. In terms of functionality, our root is the same as the base station/cluster head in [4, 37, 38] and DCTC. However, in terms of root selection, we consider residual energy of nodes inside the event region whereas they compare the link cost that associates with each of them. When a low-energy node is on the minimum-cost path, the aggregation tree will quickly get disconnected. Finally, HEED differs from the explicit tree construction approach (e.g., EADAT, MLDA, and our LPT scheme) in that only one layer of aggregation points exists, thereby increasing the loads of each cluster head. 3.7 Summary In this chapter, we have described the construction of a lifetime-preserving tree (LPT). We first introduced the spanning tree and an energy-aware variant of it, namely E-Span. While residual energy has not been fully taken into the design considerations, these trees can have lower tree energy, implying that they are more often being refreshed and more maintenance is required. Previous work using the idea of a spanning tree (e.g. DCTC and [37]) falls under this category. This chapter continued by presenting both the centralized and distributed Chapter 3 The LPT Construction 55 implementation of the LPT construction algorithms. The centralized approach works by identifying the bottleneck node whereas the distributed one identifies the highest-energy tree by performing a search of the optimal route between any pair of event sources. In the next chapter, we describe the simulation methodology, metrics, and a set of experimental results comparing LPT with other schemes. Chapter 4 Simulation Results In this chapter, we describe the results from extensive simulations of an event-driven data sensor network. A packet-level simulator is used to explore the performance of the proposed schemes under various traffic conditions. The main purpose of our experiments is to examine whether the proposed distributed LPT module can provide accurate results as the centralized one, and whether such model can provide the additional lifetime-savings over other schemes. We also compare a range of other network parameters such as data delay and packet delivery ratio; in order to determine how much the network can be affected by the amount of control messages incurred during the tree constructions. The following systems are examined throughout most of our simulations: • Directed Diffusion [19, 20], or simply Diff; • Directed Diffusion with E-Span, or simply E-Span (Section 3.3); • Centralized LPT (Section 3.4); • Directed Diffusion with distributed LPT, or simply LPT (Section 3.5). We start by first describing the performance metrics under consideration as well as a detailed explanation of the simulation methodology in Section 4.1. Next, we validate the tree energy of the distributed LPT to that of the centralized model in Section 4.2. We then compare controls and tree depths of E-Span to that of the LPT in Section 4.3. Finally, performance results on the average energy dissipation, node lifetime, data delay, and packet delivery ratio by using Diff, E-Span, and LPT are reported in Section 4.4. 56 Chapter 4 Simulation Results 4.1 Performance Metrics and Methodology 57 We implemented our tree construction modules on top of Directed Diffusion in the ns-2 [52] network simulator (the ns-2.26 release comes with diffusion support). In all of our experiments, a square sensor field with each side measuring L meters is being considered. A number of M identical nodes, ranging from 50 to 250 in the increment of 50, are randomly deployed in this sensor field such that the average node density is kept at X= 50/1602 nodes per meter square, a parameter which we borrowed from Directed Diffusion [19, 20]. Furthermore, there are five sinks randomly deployed in the field and sources are randomly chosen among the nodes, subject to the conditions that N = 0.1 M and the sources have to be interconnected to each other (to model a single stimulus). Each node is assumed to have a radio range of 40 meters. We considered an event-driven data sensor network throughout all our experiments. To model the periodic transmissions, each source generates random data reports of size fixed at 136 bytes in constant intervals of R = 1 packet per second. To introduce some randomness, data start to be generated only after a time randomly chosen between t = 0 to 5 seconds. The data are collected at the root, if it exists, and sent to the sinks. An application that computes the average of reports generated by various event sources is employed to model the aggregation behaviors. During data collection, sensors have the abilities to perform in-network aggregation of packets enroute to the root. Specifically, we meant that each sensor can combine the reports received with that from itself into a single packet containing the average of all the gathered reports. We altered the ns-2 radio energy model such that the sources carry different initial energy when the simulation starts. More specifically, for the node lifetimes to be presented in Section 4.4, we assign each source with an initial energy that is randomly chosen between 10 to 15 J in order to keep the total simulation time at a reasonable limit. In all of our Chapter 4 Simulation Results 58 experiments, all other nodes are given with an initial energy that is greater than that of any event source such that their absence in the network, due to energy depletion, do not affect the functionalities of any participating sources during data collection. Lastly, the idle time, receive, and transmit power dissipation are set at 35, 395, and 660 mW respectively. We assume a negligible energy cost to process and aggregate incoming data reports. To trace the energy, an application that logs the residual energy of each node in constant intervals of 500 ms is employed. The ns-2 simulator implements a 1.6 Mbps 802.11 MAC layer. Since Directed Diffusion is chosen as our routing platform, we also adopt a range of Diffusion-related parameters (listed in Table 4.1) in all of our experiments. Table 4.2 provides a summary of all other parameters used in our simulation models. Table 4.1: A summary of Diffusion-related parameters Interest Packet Size = 84 bytes Interest Delay = 5 sec Exploratory Data Packet Size = 132 bytes Exploratory Data Delay = 30 sec A number of metrics are used to analyze the performance of the LPT and compare with other schemes. The percentage error measures how often the distributed LPT can generate a tree with the tree energy equal to that of the centralized approach. The average per source control computes the amount of control cost, in bytes, for each source involved in constructing and maintaining the data aggregation tree throughout a simulation run. The average tree depth measures the average distance, in number of hops, between an event source and its tree root. The maximum tree depth computes the maximum distance from a leaf to the root in a given tree. The average dissipated energy, on the other hand, measures the average amount of energy consumed throughout the entire simulation. This metric computes the average work done in delivering periodic data to the sinks over a simulation run. The average node lifetime Chapter 4 Simulation Results 59 Table 4.2: A summary of other parameters used in the simulation models Item Symbol Value average node density X 50/1602 nodes/m2 number of nodes Af 50, 100,150, 200,250 number of sinks - 5 number of sources N 10% of Af network width L (MX) 0 5 node energy e„ variable data rate R 1 pkt/s protocol timeframe T 25 s E-Span control size s„ 92 bytes LPT control size m„ variable LPT hello size hn 60 bytes data packet size - 136 bytes radio range - 40 m idle time power - 35 mW receive power - 395 mW transmit power - 660 mW MAC bandwidth - 1.6 Mbps energy log period - 500 ms measures the time at which a source runs out of its available energy resource. The intuition behind this metric is to determine how much additional time that each source can suffice by collecting data via the proposed tree structure. The average RtoS delay computes the average one-way delay observed between transmitting data from the root to each of the sinks. The average StoP delay determines the delay of transmitting packets from a source to its parent. The average delay measures the delay between transmitting data from each source to each of the sinks. Observe that both LPT and E-Span combines any data enroute to the tree root with the report from the receiving node itself. Moreover, the compressed data report does not leave the receiving node right after the averaging, but is postponed to the(next transmitting period. In order to estimate this delay for both LPT and E-Span, we adopt the following equation: Chapter 4 Simulation Results 60 average delay = M a y R 2 S x r e c v S N K + (delay S2P x hop AVE + delay R2S)xrecvSRC recvSNK +recvSRC where delayR2s is the average RtoS delay, delayS2p is the average StoP delay, recvsm is the amount of data packets received by all sinks, recvSRc is the amount of data packets collected by all sources, and hopAVE is the average tree depth. Note that both application processing and queuing delays are included in all delay measurements. Finally, the average packet delivery ratio measures the ratio of the number of distinct messages received by each sink to the number originally sent (by the root if there is a tree). We study these metrics as a function of different network sizes. 4.2 Tree Energy: Distributed vs. Centralized Our first experiment compares the tree energy generated by the distributed LPT to that of the centralized approach. The intuition is to understand how often the two different schemes can i • • generate trees with equal energy. Note that the results for each network size are averaged over 100 different experiments. Our first set of results, depicted in Figure 4.1, have shown a near-100% match of the tree energy generated by the two different construction schemes, with only a little deviation when the number of participating sources is large. In fact, by logging all control message exchanges, our trace files have shown an increasing trend of message drops when network size increases. Since failure to receive a configuration message can possibly create a tree that does not have the highest tree energy, we conclude that the deviation is caused by the packet drops. However, we are able to limit this error to a small tolerable range by broadcasting the entire tree table, instead of a list of eids, in each configuration message (Section 3.5.4) so as to maximize the chance of any neighbor successfully receiving the lists stored in this table. Chapter 4 Simulation Results 61 S? 95 o fc u OJ bo B c u 90 85 80 50 • Percentage error : Distributed vs. centralized LPT 100 150 ,200 number of nodes with 10% sources 250 Figure 4 . 1 : Percentage error on tree energy generated by distributed LPT to that of the centralized one. 4.3 Controls and Tree Depths: LPT vs. E-Span Figure 4.2 shows the average per source controls involved in the constructions of LPT and E-Span respectively. Our results, averaged over 20 experiments with a 95% confidence interval, have shown that the LPT can take up to as many as 40 times the control cost of E-Span, and this difference is expected to grow with increasing network size. The reason for such trend is due to the flooding nature of LPT branch discovery. Since LPT requires the eid from each source to traverse through most of other nodes whereas E-Span only forwards it one hop away, we do expect more control exchanges in the LPT model. Figure 4.3 shows the comparison of tree depth of LPT and E-Span as a function of network size. In fact, both trees are expected to grow in tree depths since a greater network size implies a greater region bounded by the sources. With radio range set at 40 meters, the root will have to traverse more hops before it can reach all the sources when this region expands. Also observe that both the maximum and average tree depths of LPT are lower than that of E-Span. Since the selection of the E-Span root is solely based on the node's energy, it is possible that this root is located at the corner of the region bounded by the sources. LPT, on the other hand, considers tree depth in the BetterTree selection algorithm (Section 3.5.3) and Chapter 4 Simulation Results 62 is more likely to have the tree centered at this region. Therefore, we have, on average, a lower tree depth if LPT is deployed instead. 50 100 150 200 250 number of nodes with 10% sources Figure 4.2: Average per source controls (in bytes) involved in constructing the data aggregation trees. 50 100 150 200 number of nodes with 10% sources 250 Figure 4.3: Maximum and average tree depths from each participating source node to the tree root. 4.4 Performance: LPT, E-Span, and Diff To validate the impacts of data aggregation on energy savings by the use of LPT and E-Span, Chapter 4 Simulation Results 63 we measure the average dissipation energy and have the results averaged across 20 different experiments with a 95% confidence interval. Note that the simulation time is set at 200 seconds. Our results depicted in Figure 4.4 have shown a considerable amount of energy savings, down to 27% the energy dissipation of Diff, when data are aggregated via either LPT or E-Span prior to transmitting to each sink. Such a significant saving is expected since both trees efficiently suppress the amount of traffic in the network by combining data from various sources into a single packet containing the average of all the gathered reports. We expect that this difference will continue to grow with larger network size. Also observe that LPT has comparably equal dissipation energy as E-Span. This is encouraging, given that the amount of controls involved in the construction of LPT is greater than that of E-Span (shown earlier in Figure 4.2). We argue this by the fact that difference between the amount of controls for LPT i and E-Span is relatively much smaller than the total amount of data being injected. As a result, the average dissipation energy between the two will have an unnoticeable difference. In order to study the impact of LPT and E-Span on the lifetime-savings, we measure the node lifetime of each source as a function of network size for LPT, E-Span, and Diff respectively. Figure 4.5 to Figure 4.9 summarize our results. Note that each node is assigned 50 100 150 200 250 number of nodes with 10% sources Figure 4.4: Average dissipation energy as a function of network size. Chapter 4 Simulation Results 64 with an initial energy that is randomly chosen between 10 to 15 Joules so as to limit the total simulation time at a controllable range. We therefore make the following observations: 1. Both LPT and E-Span considerably extend the lifetime of each source, especially in a large network. In fact, the amount of lifetime:savings can go up to as high as 147%' and 139%2 when data are aggregated through LPT and E-Span respectively. 2. LPT has similar performance as E-Span in a smaller network. However, their difference starts to become more noticeable with increasing network size. In fact, our results have indicated a maximum of 13%3 additional lifetime-saving when there are 25 sources in the network. 3. LPT and E-Span have a more pronounced difference between the tails of the curves. In other words, most of the lifetime-savings are achieved by higher-energy nodes. The impact of data aggregation is again validated in observation 1. By combining data reports from various event sources, both LPT and E-Span are able to suppress a considerable amount of data traffic in the network. Since less energy is now consumed in forwarding data traffic (shown earlier in Figure 4.4), there should be a noticeable lifetime-saving when data are collected via a tree. And this is indeed true as shown in the figures. Next, for observation 2, we argue that the chance of obtaining an identical tree structure by using LPT and E-Span, respectively, is relatively high when there are fewer sources. In fact, when all the nodes are within the radio range of each other, both LPT and E-Span will create an identical tree with the highest-energy node selected as the root and all other nodes as leafs (only one-hop away from the root). When this happens, the amount of lifetime-saving will be quite similar. As a matter of fact, LPT only has a more remarkable lifetime-saving 1 In Figure 4.8 when there are 12 sources remaining, (191.4 - 77.4) / 77.4 = 147% for LPT. 2 In Figure 4.8 when there are 13 sources remaining, (181.6 - 75.9) / 75.9 = 139% for E-Span. 3 In Figure 4.9 when there are 3 sources remaining, (215.4 -96.1)/ 96.1 - (203.2-96.1)7 96.1 = 13% Chapter 4 Simulation Results 65 M C E 3 C i : i : i i i i 1 1 LPT E-Span Diff 1 1 i i i i i 40 80 120 160 200 240 280 320 simulation time (sec) Figure 4.5: Average node lifetime for each participating source with N = 50 nodes. 0 50 100 150 200 250 300 simulation time (sec) Figure 4.6: Average node lifetime for each participating source with N = 100 nodes. Chapter 4 Simulation Results 66 0 30 60 90 120 150 180 210 240 270 simulation time (sec) Figure 4.7: Average node lifetime for each participating source with N = 150 nodes. 0 50 100 150 200 250 simulation time (sec) Figure 4.8: Average node lifetime for each participating source with N = 200 nodes. Chapter 4 Simulation Results 67 240 simulation time (sec) Figure 4.9: Average node lifetime for each participating source with N = 250 nodes. when there are more sources in the network. Our explanation for the last observation is two-fold: First, since lower-energy nodes are usually being selected as leafs, they are unlikely to collect data from other sources. Given that these leafs have the same initial energy in both schemes, the amount of lifetime-savings due to them will therefore be similar. Second, the fact that E-Span selects the highest-energy node as the root makes this node deplete sooner than all the others (due to its additional duties in route coordination, exploratory data flood etc). Since the roles of the E-Span root are usually rotated among higher-energy nodes, we expect this group of nodes to have an energy dissipation rate greater than all the others. The result is therefore a pronounced difference between the tails of the two curves. Our next experiment compares the average RtoS delay observed between transmitting a compressed report at the tree root and receiving it at each sink as a function of network size for LPT and E-Span respectively. Our results, depicted in Figure 4.10, exhibit a trend that increases with the network size for both schemes. As the network expands, the distance between the root and the sink increases. Consequently, the average RtoS delay increases. Also Chapter 4 Simulation Results 68 observe that LPT has a similar performance with E-Span for a network of any size. Since the root selection does not depend on the positions of the 5 randomly-chosen sinks, the average distance between the root to each sink is similar for both schemes. Therefore, the difference of the delay between the two is insignificant. 50 100 150 200 number of nodes with 10% sources 250 Figure 4.10: Average RtoS delay between transmitting a data at the root and receiving at each sink. To determine the delay between any pair of a source and its parent, we measure the average StoP delay across 20 different experiments with a 95% confidence interval for LPT and E-Span respectively. Figure 4.11 depicts our results. Since more participating sources increases the MAC-layer queuing delay accordingly, the average StoP delay therefore increases with network size for both schemes. Next, observe that LPT again has a similar delay performance as E-Span. Since the rate at which the controls are generated is low (MT second), by fixing the data rate at 1 packet per second in both schemes, the amount of packets processed by the network will be quite similar. Hence, the difference of the average StoP delay between the two different schemes is negligible. Our next experiment compares the average delay, between transmitting a data packet at each source and receiving it at each sink, for Diff, LPT, and E-Span as a function of network Chapter 4 Simulation Results 69 Figure 4.11: Average StoP delay between transmitting a data at a source and receiving at its parent. size. Recall that delay in this context is based on Equation 4.1 in Section 4.1 when a tree is used. Our results, depicted in Figure 4.12, have reported that Diff has its delay built up comparably faster than both LPT and E-Span. Since LPT and E-Span combine data from various sources, it is as if only a single source is generating. This is also true in a network with a large number of data sources. Given that the rate at which nodes can process the received data is limited, data delay usually goes up when there is more traffic in the network. As a matter of fact, both LPT and E-Span should have a comparably lower delay than Diff under all our test cases. Also observe from the figure that LPT has a slightly lower delay, although quite small, than E-Span. Given that the average tree depth (shown earlier in Figure 4.3) for LPT is lower than that of E-Span, data in the former are only required to be forwarded for a fewer number of hops before it can arrive at the sinks. However, since this difference is at most one hop, we can only see a little deviation here. Our last experiment, with its result depicted in Figure 4.13, measures the average packet delivery ratio for Diff, E-Span, and LPT, as a function network size, respectively. The figure indicates that Diff experiences severe congestion when there are a lot of data sources whereas Chapter 4 Simulation Results 70 - - o - - Diff 50 100 150 200 250 number of nodes with 10% sources Figure 4.12: Average delay between transmitting a data at each source and receiving it at each sink. 1 f" .2 0.9 s 0.8 u T J U 0.7 0.6 0.5 50 100 150 200 250 number of nodes with 10% sources Figure 4.13: Average packet delivery ratio between transmitting a data and receiving it at each sink. Chapter 4 Simulation Results 71 LPT and E-Span are able to maintain their packet delivery ratios even when network expands. As we have explained in the last paragraph, Diff has its network overloaded with data traffic when more sources are sending. A considerable amount of data packets are therefore dropped as a result. LPT and E-Span, on the other hand, inject data to the sensor network as if there is only a single source. Thus, they are able to steadily maintain its packet delivery ratio even when the network is large. 4.5 Summary In this chapter, we have simulated and compared LPT with other models such as Diff and E-Span. We validated that the tree energy of distributed LPT matches closely with that of the centralized scheme, especially when there is only a few sources. We continued by comparing tree depths and have shown that LPT is more-likely to center the tree in the middle of the region bounded by all sources. Our results on the average delay also indicated that such feature efficiently reduces the delay incurred during data collection. Moreover, our next set of results have shown that both LPT and E-Span exhibit a steady increase of the average energy cost, delay, and packet drop rate when the network size increases. Finally, our main results on the average node lifetime have reported a maximum of 139% lifetime extension on the sources with E-Span, and a maximum of an additional 13% improvement when LPT is used instead. Chapter 5 Conclusions and Future Work To meet the demands where raw data readings are usually aggregated along their ways to be gathered at a single source prior to transmissions to any interested sink, we have proposed in this thesis a novel Lifetime-Preserving Tree construction algorithm for future wireless sensor networks. The tree provides a given set of sources with a mechanism to collect their data so that only a minimum amount of energy is required to deliver the same amount of information to the sinks when data aggregation is not used. The protocol features in that nodes with higher energy are tend to be chosen as data aggregating parents, whenever possible, so that the time to refresh this tree is extended and therefore less energy are involved in the tree maintenance. In addition, by constructing the tree in such a way, the protocol is able to lower the amount of data lost due to broken tree links before the tree reconstructions. Another attractive feature of the protocol is that the tree is most-likely to be centered in the middle of the event area, thereby reducing the delay during data collection. In the next few sections, we will conclude this thesis with a summary of our contributions and directions for future work. 5.1 Summary of the Thesis This research begins with an investigation to the conventional spanning tree and the energy-aware variant of it for their uses in data aggregation. We have demonstrated that: • The conventional spanning tree fails to consider residual energy of nodes in the tree constructions. There is thus a good possibility that a low-energy node is arranged to forward data for some other nodes, thereby reducing its node lifetime and fastening the energy-depletion of any subsequent event source. 72 Chapter 5 Conclusions and Future Work 73 • E-Span improves the design of tree construction by assigning root to be the highest-energy node. Such arrangement provides root with the maximum amount of energy resources for its additional duty in coordinating the route to distant sinks. However, there is still a high chance of assigning low-energy nodes to be the data aggregating agents for the other sources. To shorten the time and minimize the energy cost to tree reconstructions, and hence preserve the functional lifetime of all sources, we have proposed a lifetime-preserving tree construction algorithm which arranges all nodes in a way that each parent will have the maximal-available energy resources to receive data from all of its children. Such arrangement extends the time to refresh the tree and lowers the amount of data lost due to a broken tree link before the tree re-constructions. We have achieved the objectives by: • Introducing a distributed tree construction model to create a tree that spans all event sources and comprises the highest tree energy using a technique similar to Reverse-Path Forwarding [51]; • Proposing a centralized variant of the LPT construction scheme which identifies the node that is causing a bottleneck to the set of connectivity provided by various event sources. We have simulated and compared LPT with other modules such as Diff and E-Span. We first validated that the tree energy of distributed LPT matches closely with that of the centralized scheme, especially when there is only a few sources. We continued by comparing the amount of controls and tree depths, and have shown that LPT is more-likely to center the tree in the middle of the area bounded by all sources. Such feature efficiently reduces the delay incurred during data collection. Moreover, our next set of results indicated a relatively steady increase of the average energy cost, delay, and packet drop rate for both LPT and E-Span when Chapter 5 Conclusions and Future Work 74 network size increases, due to the amount of traffic suppressed by these two aggregation trees. Finally, results on average node lifetime have shown a maximum of 139% node-lifetime extensions on the sources with the E-Span, and a maximum of an additional 13% improvement when LPT is employed instead. In fact, LPT and E-Span have a more pronounced difference near the tails of the two lifetime curves, implying that most of the lifetime-savings are achieved by higher-energy nodes. 5.2 Topics for Future Investigations In this thesis, we have described the construction of the proposed lifetime-preserving tree and analyzed its performance when comparing with Directed Diffusion [19, 20] and E-Span. Future research work remains to enhance the proposed protocol for future wireless sensor networks. They include: • Load-Balancing Tree [53, 54]: In addition to considering residual energy in the tree constructions, the number of children that a source is being attached to can also have a significant impact on its functional lifetime. Consider a simple 4-node LPT with the root attached to 3 other inter-connected nodes. The rate at which the root dissipates is nearly 3 times that of all the others. Depending on the initial energy levels of all the nodes, the root can become energy-depleted sooner than all the other 3 nodes, even though we have already assigned the root to have the highest energy. If one of these 3 sources could have attached itself to the other two, rather than the root, the node lifetime of the root would have extended. Therefore, in order to balance and further extend the node lifetime, the load at which a node is assigned to should also depend on its residual energy level. • Disjoint Sets of Data Sources: We have simulated the performance of our proposed Chapter 5 Conclusions and Future Work 75 LPT model based on the assumption that the sources are interconnected to each other. When there are multiple disjoint sets of data sources, for example in the presence of obstacles, multiple independent data aggregation trees will be created. An interesting question now is whether the traffic from various roots should be merged together. If so, an additional amount of energy cost that depends on the number of hops between these trees will be required to coordinate the routes between various roots. If not, the amount of traffic injected by various tree roots will just increase with the number of trees in the network. • Moving Target: The issue of tree-based collaborations for mobile-target tracking has been studied by the work in [36]. The authors have proposed a model to dynamically reconfigure a tree so that the root can constantly aggregate reports from nodes that detects the mobile target even when the target moves. Our scheme, in general, does not support the tracking of a mobile target. To overcome this issue, simple heuristics in predicting the target moving direction and additional maintenance efforts to add and prune tree links will be required to reconfigure our proposed lifetime-preserving tree structure. Bibliography [1] J. M. Kahn, R. H. Katz, and K. S. J. Pister, "Next century challenges: Mobile networking for "smart dust"," in Proc. ofACMMobiCom '99, Seattle, WA, pp. 271-278, Aug. 1999. [2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and' E. Cayirci, "Wireless sensor networks: A survey," Computer Networks (Elsevier) Journal, vol. 38, pp. 393-422, Mar. 2002. [3] I. Nikolaidis, J. J. Harms, and S. Zhou, "On sensor data aggregation with redundancy removal," in Proc. of 22nd Biennial Symposium on Communications, Ontario, CA, May 2004. [4] D. Petrovic, R. C. Shah, K. Ramchandran, and J. Rabaey, "Data funneling: Routing with aggregation and compression for wireless sensor networks," in Proc. of IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03), Anchorage, AK, pp. 156-162, May 2003. [5] Q. Fang, F. Zhao, and L. Guibas, "Lightweight sensing and communication protocols for target enumeration and aggregation," in Proc. of ACM MobiHoc'03, Annapolis, MD, pp. 165-176, June 2003. [6] A. Boulis, S. Ganeriwal, and M. B. Srivastava, "Aggregation in sensor networks: An energy-accuracy trade-off," in Proc. of IEEE International Workshop on Sensor Network Protocols and Applications (SNPA '03), Anchorage, AK, pp. 128-138, May 2003. [7] G. J. Pottie and WJ. Kaiser, "Wireless integrated network sensors," Communications of the ACM, vol. 43, no. 5, pp. 51-58, May 2000. [8] E. J. Duarte-Melo, M. Liu, and A. Misra, "A modeling framework for computing 76 Bibliography 11 lifetime and information capacity in wireless sensor networks," in Proc. of 2nd WiOpt: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Cambridge, UK, Mar. 2004. [9] Y. Yu, R. Govindan, and D. Estrin, "Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks," U C L A Computer Science Dept., Tech. Rep. UCLA/CSD-TR-01-0023, May 2001. [10] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communi-cation protocol for wireless microsensor networks," in Proc. of IEEE Hawaii International Conference on System Sciences (HICSS'00), pp. 3005-3014, Jan. 2000. [11] F. Ye, S. Lu, and L. Zhang, "Gradient broadcast: A robust, long-lived large sensor network," 2001. [Online]. Available: http://irl.cs.ucla.edu/papers/grab-tech-report.ps [12] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang, "A two-tier data dissemination model for large-scale wireless sensor networks," in Proc. of ACM MobiCom'02, Atlanta, GA, pp. 148-159, Sept. 2002. [13] R. C. Shah and J. M. Rabaey, "Energy aware routing for low energy ad hoc sensor networks," in Proc. of IEEE Wireless Communications and Networking Conference (WCNC'02), Orlando, FL, pp. 350-355, Mar. 2002. [14] C. L. Barrett, S. J. Eidenbenz, L. Kroc, M. Marathe, and J. P. Smith, "Parametric probabilistic sensor network routing," in Proc. of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'03), San Diego, CA, pp. 122-131, Sept. 2003. [15] H. S. Kim, T. F. Abdelzaher, and W. H. Kwon, "Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks," in Proc. of ACM SenSys'03, Los Angeles, CA, pp. 193-204, Nov. 2003. [16] U. Cetintemel, A. Flinders, and Y. Sun, "Power-efficient data dissemination in wireless sensor networks," in Proc. of ACMMobiDE'03, San Diego, CA, Sept. 2003. Bibliography 78 [17] D. Braginsky and D. Estrin, "Rumor routing algorithm for sensor networks," in Proc. of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02), pp. 22-31, Sept. 2002. [18] W. R! Heinzelman, J. Kulik, and H. Balakrishnan, "Adaptive protocols for information dissemination in wireless sensor networks," in Proc. ofACMMobiCom '99, Seattle, WA, pp. 174-185, Aug. 1999. [19] C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: A scalable and robust communication paradigm for sensor networks," in Proc. of ACM MobiCom'00, Boston, MA, pp. 56-67, Aug. 2000. [20] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, "Directed diffusion for wireless sensor networking," IEEE/ACM Trans. Networking, vol. 11, no. 1, pp. 2-16, Feb. 2003. [21] Y. Gao, K. Wu, and F. Li, "Analysis on the redundancy of wireless sensor networks, " in Proc. of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'03), San Diego, CA, pp. 108-114, Sept.2003. [22] H. Gupta, S. R. Das, and Q.'Gu, "Connected sensor cover: Self-organization of sensor networks for efficient query execution," in Proc. of ACM MobiHoc'03, Annapolis, MD, pp. 189-200, June 2003. [23] C. Huang and Y. Tseng, "The coverage problem in a wireless sensor network," in Proc. of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'03), San Diego, CA, pp. 115-121, Sept. 2003. [24] D. Tian and N. D. Georganas, "A coverage-preserving node scheduling scheme for large wireless sensor networks," in Proc. of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA '02), pp. 32-42, Sept. 2002. [25] J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, "Building efficient wireless sensor networks with low-level naming," in Proc. of ACM Bibliography 79 Symposium on Operating Systems Principles (SOSP), Banff, Canada, pp. 146-159, Oct. 2001. [26] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, "Geographic routing without location information," in Proc. of ACM MobiCom '03, San Diego, CA, pp. 96-108, Sept. 2003. [27] T. Bokareva, N. Bulusu, and S. Jha, "A performance comparison of data dissemination protocols for wireless sensor networks," accepted for publication in Proc. of IEEE Global Telecommunications Conference (GLOBECOM'04), Nov. 2004. [28] S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and D. Estrin, "Data-centric storage in sensornets," in Proc. of ACM First Workshop on Hot Topics in Networks (HotNets-I), Princeton, NJ, Oct. 2002. [29] I. Solis and K. Obraczka, "The impact of timing in data aggregation for sensor networks," in Proc. of IEEE International Conference on Communications (ICC'04), vol. 6, pp. 3640-3645, June 2004. [30] M. Ding, X. Cheng, and G Xue, "Aggregation tree construction in sensor networks," in Proc. of IEEE Vehicular Technology Conference (VTC'03), vol. 4, Orlando, FL, pp. 2168-2172, Oct. 2003. [31] K. Dasgupta, K. Kalpakis, and P. Namjoshi, "An efficient clustering-based heuristic for data gathering and aggregation in sensor networks," in Proc. of IEEE Wireless Communications and Networking Conference (WCNC'03), New Orleans, LA, pp. 1948-1953, Mar. 2003. [32] D. Niculescu and B. Nath, "Localized positioning in ad hoc networks," in Proc. of IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03), Anchorage, AK, pp. 42-50, May 2003. [33] Y. Shang, W. Rumi, Y. Zhang, M. P. J. Fromherz, "Localization from mere connectivity," inProc. of ACM MobiHoc'03, Annapolis, MD, pp. 201-212, June 2003. Bibliography 80 [34] A. Nasipuri and K. Li, "A directionality based location discovery scheme for wireless sensor networks," in Proc. of ACM International Workshop on Wireless Sensor Networks and Applications (WSNA '02), Atlanta, GA, pp. 105-111, Sept. 2002. [35] A. Sawides, C. C. Han, and M. B. Srivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors," in Proc. of ACM MobiCom '01, Rome, Italy, pp. 166-179, July 2001. [36] W. Zhang and G Cao, "DCTC: Dynamic convoy tree-based collaboration for target tracking in sensor networks," IEEE Trans. Wireless Commun., vol. 3, no. 5, pp. 1689-1701, Sept. 2004. [37] J. Carle and D. Simplot-Ryl, "Energy-efficient area monitoring for sensor networks," IEEE Computer Magazine, vol. 37, no. 2, pp. 40-46, Feb. 2004. [38] S. Upadhyayula, V. Annamalai, S. K. S. Gupta, "A low-latency and energy-efficient algorithm for convergecast," in Proc. of IEEE Global Telecommunications Conference (GLOBECOM'OS), vol. 6, pp. 3525-3530, Dec. 2003. [39] O. Younis and S. Fahmy, "HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks," IEEE Trans. Mobile Computing, vol. 3, no. 4, pp. 366-379, Oct. 2004. [40] J. N. Al-Karaki, R. Ul-Mustafa, and A. E. Kamal, "Data aggregation in wireless sensor networks - exact and approximate algorithms," in Proc. of IEEE Workshop on High Performance Switching and Routing (HPSR '04), Phoenix, AZ, pp. 241-245, Apr. 2004. [41] A. Cerpa and D. Estrin, "ASCENT: Adaptive self-configuring sensor networks topologies," in Proc. of IEEE Infocom '02, vol. 3, New York, NY, pp. 1278-1287, June 2002. [42] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. B. Srivastava, "Topology management for sensor networks: Exploiting latency and density," in Proc. of ACM MobiHoc'02, Lausanne, Switzerland, pp. 135-145, June 2002. Bibliography 81 [43] Y. Xu, J. Heidemann, and D. Estrin, "Geography-informed energy conservation for ad hoc routing," in Proc. ofACMMobiCom '01, Rome, Italy, pp. 70-84, July' 2001. [44] A. Sankar and Z. Liu, "Maximum lifetime routing in wireless ad-hoc networks," in Proc. oflEEEInfocom '04, Hong Kong, Mar. 2004. [45] E. J. Duarte-Melo and M. Liu, "Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks," in Proc. of IEEE Global Telecommunications Conference (GLOBECOM'02), vol. 1, pp. 21-25, Nov. 2002. [46] V. Mhatre, C. Rosenberg, D. Kofman, R. Mazumdar, and N. Shroff, "A minimum cost heterogeneous sensor network with a lifetime constraint," accepted for publication in IEEE Trans. Mobile Computing, Jan. 2004. [47] H. Zhang and J. Hou, "On deriving the upper bound of a-lifetime for large sensor networks," in Proc. of ACM MobiHoc'04, Roppongi Hills, Tokyo, Japan, pp. 121-132, May 2004. [48] D. M. Blough and P. Santi, "Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks," in Proc. of ACMMobiCom '02, Atlanta, GA, pp. 183-192, Sept. 2002. [49] R. Perlman, Interconnections: Bridges, routers, switches, and internetworking protocol, 2n d ed., Addison-Wesley Professional Computing Series, Reading, MA, 1999. [50] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2n d ed., MIT Press, 2001. [51] Y. K. Dalai and R. M. Metcalfe, "Reverse-path forwarding of broadcast packets," Communications of the ACM, vol. 21, no. 12, pp. 1040-1048, Dec. 1978. [52] VINT, "The network simulator ns-2," http://www.isi.edu/nsnam/ns, November, 2001. [53] R. Guerin, J. Rank, S. Sarkar, and E. Vergetis, "Forming connected topologies in Bluetooth adhoc networks," in Proc. of International Teletraffic Congress (ITC18), Berlin, Germany, pp. 1011-1020, Sept. 2003. Bibliography 82 [54] H. Dai and R. Han, "A node-centric load balancing algorithm for wireless sensor networks," in Proc. of IEEE Global Telecommunications Conference (GLOBECOM'03), vol. l,pp. 548-552, Dec. 2003. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065301/manifest

Comment

Related Items