DESIGN AND IMPLEMENTATION OF MDELUGE MULTICAST CODE DISSEMINATION SYSTEM FOR WIRELESS SENSOR NETWORKS by Xiao Zheng BEng., Shanghai JiaoTong University (China), 2004 THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in MATHEMATICAL, COMPUTER, AND PHYSICAL SCIENCES (COMPUTER SCIENCE) THE UNIVERSITY OF NORTHERN BRITISH COLUMBIA August 2006 ©Xiao Zheng, 2006 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Library and Archives Canada Bibliotheque et Archives Canada Published Heritage Branch Direction du Patrimoine de I'edition 395 W ellington Street Ottawa ON K1A 0N4 Canada 395, rue W ellington Ottawa ON K1A 0N4 Canada Your file Votre reference ISBN: 978-0-494-28415-5 Our file Notre reference ISBN: 978-0-494-28415-5 NOTICE: The author has granted a non­ exclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distribute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. AVIS: L'auteur a accorde une licence non exclusive permettant a la Bibliotheque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par telecommunication ou par I'lnternet, preter, distribuer et vendre des theses partout dans le monde, a des fins commerciales ou autres, sur support microforme, papier, electronique et/ou autres formats. The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. L'auteur conserve la propriete du droit d'auteur et des droits moraux qui protege cette these. Ni la these ni des extraits substantiels de celle-ci ne doivent etre imprimes ou autrement reproduits sans son autorisation. In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis. Conformement a la loi canadienne sur la protection de la vie privee, quelques formulaires secondaires ont ete enleves de cette these. While these forms may be included in the document page count, their removal does not represent any loss of content from the thesis. Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant. i*i Canada Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. APPROVAL Name: Xiao Zheng Degree: Master o f Science Thesis Title: DESIGN AND IMPLEMENTATION OF MDELUGE MULTICAST CODE DISSEMINATION SYSTEM FOR WIRELESS SENSOR NETWORKS Examining Committee: ...... Chair: Dr. Robert Tait Dean o f Graduate Studies University of Northern British Columbia Co-supervisor: Dr. Behcet Sankaya, Professor Mathematical, Computer, and Physical Sciences Program University o f Northern British Columbia Co-SupeevisoT?br. Siamak ifezaei, Associate Professor Mathematical, Computer, and Physical Sciences Program University o f Northern British Columbia C om m itteeN L^ber^iJ/^ou^TalTK fbham ed, Associate Professor Mathematical/Computer, and Physical Sciences Program University of Northern British Columbia Comrriittee Member: Di^ Alex Aravind, Assistant Professor Mathematical, Computer, and Physical Sciences Program University o f Northern British Columbia External Examiner: Dr. Vincentl Wong, Assistant Professor Department o f Electrical and Computer Engineering University o f British Columbia Date Approved: Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Abstract In today’s wireless sensor networks there is a need to improve macro pro­ gramming of the sensor nodes so that sensor nodes can execute various applica­ tions in a flexible manner. There is a need to contribute to macro programming of wireless sensor networks by developing new network programming techniques which can disseminate the code into designated sensor nodes. We present a new network programming application called Multicast Deluge (MDeluge) which can be used to disseminate the code image into a designated subnet of a wire­ less sensor network. MDeluge disseminates code in the sensor network using a tree which is formed when the source node broadcasts the code version mes­ sage. The source node keeps the code and sends it based on the requests. MDeluge also supports code dissemination in the sensor networks that are ge­ ographically distributed and with moving nodes. Assuming a grid structured wireless sensor network, we present an analysis of various message costs as well as the overall cost of data messages of MDeluge. Experiment and simulation of MDeluge shows that MDeluge can disseminate the code image into designated sensor nodes and also shows how the performance will be influcenced by the parameters of MDeluge. ii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table of C ontents 1 A b stra c t.............................................................................................................. iii Table of C ontents............................................................................................... iii List of T a b le s ..................................................................................................... vi List of Figures..................................................................................................... viii Acknowledgments............................................................................................... ix Introdu ction 1 1.1 Wireless Sensor Networks ...................................................................... 1 1.2 Macro programming in W S N s ................................................................ 3 1.3 Soft State Protocol D esig n ...................................................................... 6 1.3.1 C A P W A P H P ............................................................................... 6 1.3.2 SIP Paging and Tracking protocol.............................................. 7 Structure of the T h e s is............................................................................ 8 1.4 2 3 N etw ork Program m ing and W ireless M esh N etw orks 9 2.1 Early Approaches..................................................................................... 9 2.2 Deluge and VM based approaches......................................................... 12 2.3 M ulticast A p p ro a ch ................................................................................................ 14 2.4 Wireless Mesh Network S u p p o rt............................................................ 15 D esign o f M D elu ge 19 3.1 Problem D e sc rip tio n ............................................................................... 19 3.2 Code Segm entation.................................................................................. 21 iii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4 5 6 7 8 3.3 Tree Based R outing.................................................................................. 21 3.4 Code Propagation..................................................................................... 24 3.5 In-network Aggregation............................................................................ 25 3.6 R eliability................................................................................................. 26 3.7 Securing MDeluge..................................................................................... 27 3.8 Support for Moving S e n s o rs ................................................................... 28 M D elu ge In tern et P rotocol 30 4.1 Passive M o d e ........................................................................................... 32 4.2 Active M ode.............................................................................................. 34 M D elu ge Im plem en tation 36 5.1 Operating Systems and P latfo rm s......................................................... 36 5.2 Formats of M essag es............................................................................... 38 5.3 Implementation of MDelugeS e r v e r ........................................................ 40 5.4 Implementation of MDelugeClient ........................................................ 41 5.5 E x p e rim e n t.............................................................................................. 44 Perform ance A nalysis 46 6.1 Message Cost and Grid S tru c tu re .......................................................... 46 6.2 Analytical R e s u lt..................................................................................... 47 Sim ulation o f M D elu ge 49 7.1 Stationary WSN ..................................................................................... 49 7.2 WSN with Moving Sensors..................................................................... 52 C onclusions 59 8.1 60 Future D irections..................................................................................... A pp en d ices 68 iv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. A U ser M anuals A.l 68 Simulation of Stationary Sensors....................................................... 68 A.2 Simulation of MovingS e n s o rs ........................................................... 69 A.3 Use M D e lu g e ........................................................................................... 70 B List o f A cronym s 72 v Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. List of Tables 3.1 Comparison of MDeluge and Main Code Dissemination Applications in T in y O S .................................................................................................. 20 4.1 Encoding of LF F ie ld ....................................................................... 35 5.1 Code Dissemination Time of MDeluge Experim ent.............................. 45 7.1 Message Cost for Different Sink N o d e ................................................... 50 7.2 Code Dissemination Time for Different Sink N o d e ............................. 51 7.3 Code Dissemination Time for Different Numbers of Sink Nodes . . . . 51 7.4 Message Cost for Different Numbers of Sink Nodes ......................... 51 7.5 MDeluge P a ra m e te rs ............................................................................... 53 vi Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. List of Figures 3.1 Gradients set by node table after flooding of code version message . . 22 3.2 sink node by sink node dissem ination.................................................... 25 4.1 Wireless Mesh Network T o pology .......................................................... 31 4.2 Format of general TinyOS Packets and TelosB P a c k e ts ..................... 32 4.3 Communication Stacks for Micro Servers in Passive M ode.................. 33 5.1 Format of Code Version Message ........................................................... 39 5.2 Format ofRoute Update M essage........................................................... 39 5.3 Format of Code Request M essag e........................................................... 40 5.4 Format of Code Data M essage................................................................. 40 5.5 Component Relationships of MDeluge C lie n t....................................... 42 5.6 Component Relationships of MDelugePageTVansfer in MDeluge Client 42 6.1 Grid Topology of sensor network............................................................. 47 7.1 500m*500m city area environment.......................................................... 52 7.2 Code Dissemination Time for Different Numbers of Sink Nodes with Mesh Network S u p p o rt............................................................................ 7.3 Message Cost for Different Numbers of Sink Nodes with Mesh Network S u p p o r t..................................................................................................... 7.4 54 Code Dissemination Time for Different Server Wait Time with Mesh Network S u p p o r t...................................................................................... 7.5 53 55 Message Cost for Different Server Wait Time with Mesh Network Support 56 vii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 7.6 Code Dissemination Time for Different Request Intervals with Mesh Network S u p p o r t...................................................................................... 56 7.7 Message Cost for Different Request Intervals with Mesh Network Support 57 7.8 Code Dissemination Time for Different Beacon Intervals with Mesh Network S u p p o r t...................................................................................... 58 7.9 Message Cost for Different Beacon Intervals with Mesh Network Support 58 viii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. A cknow ledgm ents I would like to give my deepest thanks to my supervisor Prof. Behcet Sarikaya, who influenced me most during my years at UNBC. Throuthout my two years’ studying and researching, he gave me effective guidance with his knowledgeable suggestions. Prom him, I learnt how to develop new ideas from the papers, how to analyze and simulate network protocols, and how to write a well structured paper. I feel grateful to him for any future success I may have. I also want to thank to Dr. Siamak Rezaei, Dr. Alex Alagarsamy, Dr. Moustafa Mohamed and Dr. Vincent Wong for their suggestions and comments on this thesis. These valuable comments helped a lot to complete this thesis. Finally I will give my deep appreciation and thanks to my parents Wei and Pingping, for sharing their unconditional love with me and giving me the courage for pursuing my research goals at UNBC. ix Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 1 Introduction In this chapter, We will introduce the wireless sensor network (WSN) and a new programming technique for the wireless sensor network called macro programming. We will introduce basic protocol design principles such as soft state approaches with two applications to CAPWAP Handover, and SIP Paging and Tracking Protocols. 1.1 W ireless Sensor N etw orks With the prolonged exponential growth in the underlying semiconductor technology, the number of transistors on a cost-effective chip doubles every year or two. This is called Moore’s law. Therefore, the processing and storage capacity of that chip also increases fast. Having the devices with more computing power, researchers now are able to apply this technology in lots of new areas of computer science. Wireless wensor network [CES05] is one of them. The notion of sensor networks has come up for more than two decades [CK03]. Early sensor networks included radar networks used in air traffic control systems and national power grids. However, these are all wired networks. Although some scientists envisioned that a larger number of small sensing devices might be used at that time, it became true only in the recent years. The sensors are usually small and cheap devices with radios and can be used to sense fields and forces in the 1 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. physical world. These inexpensive, low-power communication sensor devices can be deployed throughout a physical space, and can provide dense sensing close to physical phenomena, process and communicate this information, and coordinate actions with other nodes to achieve certain tasks. Combining these capabilities not only makes it possible to instrument the world with increasing fidelity, but also brings lots of new challenges to the scientists. Although computer-based instrumentation has existed for a long time, the density of instrumentation made it possible by a shift to mass-produced intelligent sensors. The use of pervasive networking technology gives WSNs a new kind of scope that can be applied to a wide range of uses. In [CES05], these applications are roughly differentiated into three categories: monitoring space, monitoring things, and moni­ toring the interactions of things with each other and the encompassing space. The first category includes environmental and habitat monitoring, precision agriculture, indoor climate control, surveillance, treaty verification, and intelligent alarms. The second includes structural monitoring, condition-based equipment maintenance, med­ ical diagnostics, and urban terrain mapping. The most dramatic applications involve monitoring complex interactions, including wildlife habitats, disaster management, emergency response, ubiquitous computing environments, asset tracking, healthcare, and manufacturing process flow. WSN is a new class of distributed systems that operates under a new set of constraints. Many tasks become complicated because of the unique requirements and constraints of WSNs, e.g. energy efficiency, resource limitations in computing and communicating, scalability, automatic adaptation to environmental dynamics. In most settings, the network must operate for long periods of time and the nodes are wireless, so the available energy resources limit their overall operation. That is why we need to minimize the energy consumption for WSN applications. To achieve that, most of the device’s components, including the radio will likely be turned off most of the time. The sensors have substantial processing capability in the aggregate, but not individually, so we must combine their various vantage points on the physical 2 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. phenomena within the network itself. WSN is closely coupled to a changing physical world. The nodes forming the network will experience wide variations in connectiv­ ity and will be subject to potentially harsh environmental conditions. Assuring the reliable communication between the sensor nodes for data transferring is a significant challenge. The sensors are relatively cheap devices which makes it possible to deploy a large scale sensor network. With the increasing of the number of sensors, the ap­ plication running in WSN needs to be scalable. The application running on sensors may need to be changed according to the environmental dynamics. For example, after an event is detected, such as pine beetle attack in the forests, it is desirable that the sensor nodes become environmental monitoring nodes reporting different signals they receive, such as temperature and humidity. Despite these operational factors, deploying and maintaining the nodes must remain inexpensive. Because manually configuring large networks of small devices is impractical, the nodes must organize themselves and provide a method of programming and managing the network as an ensemble, rather than administering individual devices. 1.2 M acro program m ing in W S N s There are two main approaches to developing applications for WSNs - micro program­ ming and macro programming. Micro programming in WSN focuses on programming every single sensor node. The programmer needs to translate the global behavior specifications of the WSN application into a set of local actions for each node in the system. Each node is programmed individually and the program will represent the behavior of that single node. The program includes the application level func­ tionalities and all the details of system level control and coordination functionalities although these functionalities may not be relevant to the application itself. The pro­ grammer needs to be aware of the distribution issues in WSNs, such as routing and in-network aggregation. Without the knowledge of distributed computing, and wire­ less networking in WSN domain, a programmer would have difficulties to accomplish 3 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. the programming. Macro programming in WSN focuses on programming the entire sensor network. It provides higher-level abstractions of WSN to the programmer and allows the programmer to express the desired global behavior of a distributed compu­ tation on the entire network in a centralized fashion. The programmer normally does not see the single nodes with macro programming, but only their aggregate effects in the network. Typically the program is based on the adaptation of different layers of abstraction. Distribution issues are largely hidden from the programmer. After the program is developed by the programmer, it is compiled for individual sensor nodes and disseminated into the sensor network. Macro programming will eventually enable the sensor nodes to execute different programs as needed in different times, and to disseminate new versions of the programs. The Abstract Task Graph (ATaG) [BPP05] is a macro programming model for WSN. ATaG employs a data driven programming model and mixed imperativedeclarative program specification. The data driven programming model defines tasks in terms of their input and output data objects. Task scheduling and inter-task communications will be managed by the underlying runtime system. Availability of operands will trigger task execution, subject to firing rules. This model provides programming convenience in the domain of distributed system programming and the modularity and extensibility of the programs [THNOO]. The programmer will view the network as a domain-specific transformation system of sensor data. The mixed imperative-declarative specification enables the program to be compiled for a differ­ ent network size and topology by interpreting the declarative part in the context of that network architecture, while the imperative part remains unchanged. After the programmer completes an ATaG program, the program is compiled into a specified network. The compiler translates the annotations in the context of that specific de­ ployment, and generates a ’configuration’ for each node in the target network. The configuration is then disseminated into each node and interpreted by the Data Driven ATaG Runtime on each node. Kairos [GGG05] is another macro WSN programming model. It provides pro4 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. grammer abstractions of node, one-hop neighbors and remote data access. With node abstraction, programmers can explicitly manipulate nodes and lists of nodes. By calling a getneighbors() function, the programmer can easily get the current list of the node’s radio neighbors from the Kairos runtime environment. The remote data access abstraction gives the programmer the ability to read variables at named nodes at any time. After the centralized version of the program is written, it is processed using a preprocessor which resides as an extension to the language compiler and an­ notated source code is generated. The annotated source code is then compiled into a binary using the native language compiler. The binary is a node-specific version of code that contains code for what a single node does at any time, and what data it manipulates. The binary is linked to the Kairos runtime and can be distributed to all nodes in the sensor network. There may be sensor nodes in the network that have different behaviors for the application. The binary for these sensor nodes will also be different. To support micro programming in WSN, we need a network programming appli­ cation which has the ability to disseminate and load the code image into the des­ ignated nodes in the network. Otherwise, the code image needs to be downloaded into sensor nodes one by one. The sensor nodes may be deployed over wide geo­ graphic areas [HKL+06] or a remote area [WAJR+05, JOW+02, BOSR04] and will operate unattended. This makes manual programming unusable. The most popu­ lar network programming applications now like Deluge [HC04, LPCS04] and Mate [LGC05, LPCS04] all use an epidemic approach. With the epidemic approach, the code image will spread over the whole sensor network and finally all the sensors will hold the same code image. Within some of WSN applications, the sensor nodes may be stationary, which means after deployment they do not change their positions frequently, e.g. most environmental monitoring WSNs, structural monitoring WSNs. Within some other applications, the sensor nodes move with the objects they are monitoring, e.g. medical sensors will be planted into patients’ bodies and move with the patients, wild life 5 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. tracking sensors will move with the animals. The network programming application needs to adapt to both situations. The code size is relatively large compared with the sensing data. The reliable code transmission is also a challenge to the design of the code dissemination application. The code dissemination application also needs to be scalable with different sizes of WSNs. In this thesis, we propose a new network programming application called MDeluge which can disseminate and load the code images into the designated sensors in WSN. It adapts to both stationary sensors and moving sensors and is also scalable to the size of WSN. 1.3 Soft S ta te P ro to co l D esign Hard state is a signaling approach in which the state is installed forever and it requires explicit signaling for removal. Soft state is a signaling approach in which installed state times out and is removed, unless periodically refreshed by the receipt of a sig­ naling message. Since unrefreshed state will eventually time out, soft-state signaling requires neither explicit state removal nor a procedure to remove orphaned state. Similarly, since state installation and refresh messages will be followed by subsequent periodic refresh messages, reliable signaling is not required [JGKT62]. MDeluge is a soft state protocol. We have developed several soft state protocols for wireless local area networks (WLANs) which includes CAPWAP handover protocol [SZ06] and SIP paging and tracking protocol [SZO06]. We gained experience in protocol design and analysis from this research, and realized that soft state is an important tool in protocol design for wireless networks. 1.3.1 CAPW APH P Recently, a new type of 802.11 access points (AP) called split MAC wireless termi­ nation points (WTP) has emerged. A local MAC WTP is a WTP with full medium 6 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. access control (MAC) functions. A split WTP offloads some MAC functions to an entity called the access controller (AC). Typically an AC in a campus will be in charge of all WTPs in the campus. A Control and Provisioning of Wireless Access Points protocol (CAPWAP protocol) is now being developed by IETF. There is a need to manage station handovers by the AC in the CAPWAP architecture. CAPWAP han­ dover protocol (CAPWAPHP) is a new handover and context transfer protocol for WLAN hosts managed by ACs. CAPWAPHP should fulfill the following requirements: 1. The station should have an association with only one WTP at any time. 2. The station should be able to move from one WTP to another successfully. 3. The protocol should support both split MAC WTPs and local MAC WTPs. 4. The handoff time should be minimized. The design of CAPWAPHP can be divided into 2 parts. The handoff part is used to ensure the handoff correctness. The mobile station can associate with one WTP at any time and it can move from one WTP from another successfully. The context transfer part is used to accelerate the handoff process by transferring the mobile station’s context from the old WTP to the new WTP if local MAC WTPs are used. W ith the context transferring, the re-authentication time can be reduced. For Split MAC wireless termination points, the context cache is stored at AC and kept in soft state. The stations periodically refresh their context caches at AC and when handoff happens they will update their context caches at AC. 1.3.2 S IP P a g in g and T racking p r o to co l The Session Initiation Protocol (SIP) is an application layer protocol that deals with the creation, modification and termination of m ultim edia sessions. The scenario we consider is as follows: A mobile user may connect his/her SIP-enabled phone to IEEE 802.11 wireless LAN network and may receive a call from another mobile user connected to the third/fourth generation (3G/4G) UMTS network. The callee may be in dormant mode and therefore the call may be missed. The architecture of our protocol contains a SIP server, a Location Server (LS), a 7 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Paging Agent (PA) and a tracking agent (TA). MN is identified by LS through SIP registration with its MAC address and its IP address. PA includes a SIP client entity and supports the Register and Paging methods which are extensions of SIP protocol. TA keeps L2 location information of the mobile stations which is called paging cache. SIP Paging and Tracking protocol should fulfill the following requirements: 1. The TA should be able to track the locations of the mobile stations. 2. Once the SIP server receives SIP INVITE message for a dormant MN in its domain, the SIP server should be able to page the MN by sending a paging request message to PA. 3. The paging mechanism should be able to wake up the MN from the domain mode. 4. The paging time should be minimized. In SIP Paging and Tracking protocol, we extended SIP protocol by supporting an extended Register method and a new Paging method. When an MN goes to dormant mode, it registers with PA. When the SIP server gets SIP INVITE messages for a dormant MN, it asks PA to page the MN. TA keeps the paging cache and PA asks TA to page the MN. The paging cache is maintained in soft state. Access routers refresh the paging cache periodically. When the link layer handoff happens, TA is informed and the paging cache is updated. Onlink paging can be implemented using TIM or DTIMs of 802.11. The context of MN is transferred during the paging process to reduce the paging time. 1.4 S tructure o f th e T hesis In Chapter 2, we describe related works on which multicast Deluge is based. Chapter 3 presents MDeluge algorithm. Chapter 4 extends MDeluge to support geographically distributed WSNs with a MDeluge Internet protocol. A new gateway protocol which can bridge the IP network and WSN will be presented. Chapter 5 describes the implementation of MDeluge. Chapter 6 analyzes the performance. Chapter 7 shows the simulation results and chapter 8 concludes the thesis. 8 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 2 N etw ork Program m ing and W ireless M esh Netw orks In this chapter, we will introduce the concept of network programming. We will go through the evolution of network programming applications. The de facto network programming application for Tiny OS [LMP+04] operating system Deluge [HC04] will be introduced in detail. Wireless mesh networks which can be used to extend the geographic coverage of the network are also introduced. The network programming applications are used to program the WSN using the existing code image. With the network programming applications, the sensor nodes do not need to be programmed manually. Instead, the application will contain a mechanism to inject the existing code image into the sensor network. After that, the designated sensors will receive the code image completely. The user can then use the network programming applications to load the new code image and reboot. 2.1 Early A pproaches XNP [xnp03] is the earliest reprogramming application for TinyOS operating system. When TinyOS comes out, XNP is included in its source tree. XNP is a single-hop over the air programming application. In this application, there is one source node, 9 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. and all the nodes need to be reprogrammed are one hop away from the source node. The source node first broadcasts code capsules to all the nodes within its broadcast domain. The wireless links in WSN usually have low bandwidths and high loss rates. The connections of the wireless links are unstable and subject to the changes of the environ­ mental conditions. The network programming applications must have a mechanism to assure the reliable data transmission. Because if the code image is not received completely, it is not usable. PSFQ [WCK02] (Pump Slowly, Fetch Quickly) is such a protocol. It is a hop by hop reliable transport protocol. The data is transferred hop by hop from the source node to the final destination node. PSFQ has three functions: message relaying (pump operation), relay-initiated error recovery (fetch operation) and selective status reporting (report operation). The pump operation makes the source node disseminate data at a relatively slow data rate and uses a data cache at the intermediate sensor nodes to suppress duplicates. The fetch operation enables high rate, NACK-based error recovery which allows nodes to request miss­ ing packets from neighboring nodes aggressively. It also batches all requests for lost packets whenever possible. PSFQ supports a report operation designed specifically to feedback data delivery status information to users in a simple and scalable man­ ner. RMST [SH03] (Reliable Multi-Segment Transport) is a reliable transport layer protocol designed to work with Directed Diffusion [HSI+01] in WSNs. It is used to disseminate large pieces of data from the source node to all subscribed nodes. Two distinct transport services are added to diffusion: effective management of the frag­ mentation and reassembly of units based on application semantics, and guaranteed delivery. It uses a NACK-based repair mechanism. The receivers detect the loss and the requests for missing packets are unicasted to the source. The intermediate nodes caches the request enables fast recovery. SRM [FJL+97] (Scalable Reliable Multi­ cast) is a reliable multicast mechanism. It uses various suppression techniques to minimize network congestion and request implosion at the source node. With SRM, each member in the multicast group periodically sends out a heartbeat which contains 10 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. the sequence number of the latest sent packet. Other members in the multicast group receive these heartbeats and compare the sequence number in the heartbeat with the sequence number of the last received data-packet to detect packet loss. When a packet is lost, a NACK is sent to all members and all members participate in the repair of the traffic which not only lessens the burden on the source node but also makes the repair process faster. Each member caches the latest received data-packets and if the node receives a NACK for a packet it has in its cache, it retransmits that packet to the whole group as a repair. To minimize the number of NACKs and re­ pairs, exponential back-off is used. Instead of sending the packet directly, the node waits for a random time, and if another member sends the same packet it withdraws its own potential transmission. In XNP, a NACK based reliable data transmission mechanism is used. After the whole image has been transmitted, the source node polls each neighbor for missing capsules. The neighboring nodes scan the contents of their EEPROM to find out gaps in the code image. If any gaps are found, they respond the source node with NACKs which contain the information of missing capsules. Upon receiving the NACKs, the source node unicasts the missing capsules to the requesting nodes. However, this single-hop reprogramming application has very limited usage. Whenever the network size is larger than the reach of a single hop, this method of approach is no longer applicable. Multihop Over-the Air Programming (MOAP) [SHE03] is a network programming application supports multihop WSNs. In MOAP, the code image is divided into segments. Each segment can fit into a single packet. The nodes who have the new code image broadcast advertisements to inform other nodes in the network. After receiving the advertisements, other nodes unicast request messages to the source nodes to request the new code image. The source nodes broadcast data messages after receiving the request messages, and NACKs are used if the data messages are lost. Each receiving node maintains a sliding window to receive code segments. However, MOAP doesn’t support fragmentation of the code image, so it requires each sensor 11 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. node to receive the entire image before the node can re-broadcast the code image to other nodes. Because the code data is broadcasted, all the sensor nodes will finally share the same code image. A difference-based approach [RL03] is proposed to reprogram the sensor network with a difference based mechanism. This approach does not send the new code image. Instead, it generates the script which describes the differences between the current code image and the new code image, and sends this script to the required nodes. The code update information can be minimized if the new code image shares much of the content with the old code image. It has four steps to disseminate the new code initialization, code image building, verification and loading. This approach can be used as a complement code dissemination protocol to update the version of the code image. 2.2 D elu ge and V M based approaches Deluge [HC04] is the de facto network programming application for TinyOS WSNs. It uses an epidemic approach. If one sensor in the network gets the new code image, the new code image will finally reach all the nodes in the network. In Deluge, the binary image is divided into pages and pages are divided into packets. This image fragmentation mechanism has several advantages. First, it enables updating the code image in sensor node based on page differences. New pages will be disseminated to replace the old pages instead of disseminating the whole image. Second, with this design, pipelining can be used in code dissemination. After receiving a new page, the sensor node can send it to the next node before requesting the new page. Third, if the link fails during the code dissemination, previously received pages do not need to be retransmitted. After the new link established, the dissemination will resume from the point where the link failed. The source nodes broadcast the code summaries periodically and the requesting nodes unicast request messages to request the code after they receive the code summaries. Then the code data is broadcasted to the 12 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. requesting nodes from the source nodes. A NACK based approach is used for reliable transmission. In Deluge, each sensor node keeps 3 states: maintain, request and transmit. A node in the maintain state is responsible for ensuring that all nodes within commu­ nication range have the newest version of the object profile and all available data for the newest version. To maintain this property, each node occasionally advertises a summary representing the current version of its object profile and the set of pages from the object which are available for transmission. A node in the request state is responsible for actively requesting the remaining packets required to complete the re­ questing page. NACKs are sent with a bitmap specifies data packets in the page that are needed. To achieve density awareness, requests are made with a random backoff to help minimize collisions with requests from other nodes and to allow suppression if any requests or data packets overheard during the backoff period. A node in transmit state is responsible for broadcasting all requested packets for a given page until all requested packets have been broadcasted and then transitions back to maintain state. Mate [LGC05] is a TinyOS application which uses application specific virtual machines (ASVMs) to reprogram deployed WSNs. ASVMs provide a way for a user to define an application specific boundary between virtual code and the VM engine. This allows programs to be very small and makes code dissemination fast and inexpensive. Mate stores the program image in capsules. Capsules can be disseminated similar to the pages in Deluge. Three states are maintained: maintain, request and respond. We can view the Mate’s capsule based code dissemination mechanism as a light-weight Deluge. Mate has several Differences with Deluge. Mate broadcasts the request message and data messages. In Deluge, once a page is requested, all the packets of the page are sent to the requesting node at once, while in Mate only one packet randomly chosen from the requested packets is broadcasted at one time. The code dissemination process usually takes a long time to complete and a large number of messages are sent during the process. To reduce the total number of messages, a suppression mechanism can be used. Trickle [LPCS04] is such a sup13 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. pression algorithm. Trickle itself does not define how code would propagate, because the propagation protocol will depend on the size of the data. Trickle dynamically scales its suppression intervals to detect inconsistencies, but sends few packets when the network is consistent. With Trickle, the redundant broadcasting messages can be suppressed. Deluge uses Trickle to control the broadcasting of version advertisement and Mate maintains three instances to control the broadcasting of version packets, capsule status packets and capsule fragments. SensorWare [BHS03] is a framework for efficient and programmable WSNs. Its design is similar to Mate. However, SensorWare is targeted on more powerful sensor nodes than UCBerkeley nodes. Such nodes (e.g., Rockwell WINS nodes [roc06]) typically have a 1Mbyte of program memory and 128Kbytes of RAM. With the more powerful sensor nodes, SensorWare can support concurrent multi-tasking, so that multiple applications can be concurrently executed in a WSNs. In SensorWare, the script is propagated with a replicate command. The replicate command transfers the script that it was called from, to other nodes. The replicate command starts with a transmission of an ‘intention to replicate’ message, which contains the name of the script and the issuing user. If the same script already exists in the other nodes, replicate, according to options, may choose not to transfer the code or initiate a second script of the same type in the node. 2.3 M u lticast A pproach All the network programming applications described before are aimed to disseminate the code image into the entire network. However, to support macro programming, the new network programming protocol is to disseminate the code image into a subset of the network. This shares some features with multicast protocols in ad hoc networks, e.g. the communication pattern is one to many, and the energy consumption is an important criteria for the applications. Lots of research has been done in the area of multicast protocols in ad hoc net- 14 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. works.In [CGA03], Ad Hoc Multicast Protocols are divided into 4 types: tree-based approaches, mesh-based approaches, stateless multicast and hybrid approaches. In tree-based approaches, a dissemination tree will be constructed and maintained to disseminate the data. In mesh-based approaches, there may have multiple paths between the source and receiver pair. This suits best when the network topology changes frequently. In stateless multicast, the source will explicitly mention the list of destinations in the packet header. The underlying routing protocol will take care of forwarding the packet to respective destinations based on the addresses contained in the header. The hybrid approaches use both tree and mesh in the algorithm. In MDeluge, we will use a tree based algorithm because it is more efficient for data dissemination than mesh based algorithms. The stateless algorithms focus on small group multicast and uses variable length packets. They do not suit the net­ work programming in WSNs because the multicast group may be large in large scale WSNs and some WSN applications use a fixed packet size. Sensor nodes have limited computing and memory resources. That requires us to make the code dissemination protocol not too complicated. So we did not choose a hybrid approach. 2.4 W ireless M esh N etw ork Support Wireless mesh networks (WMN)[AWW05] are proposed to resolve the limitations and improve the performance of Ad Hoc networks. In WMNs, there are mesh routers and mesh clients. Mesh routers will have multiple interfaces which could provide access to Internet, cellular, sensor network, or other networks. Hyacinth (IEEE 802.11 based multi-channel wireless mesh network) [RC05] is an example of wireless mesh networks. In Hyacinth, each mesh node will have multiple 802.11 network interface cards. A fully distributed channel assignment algorithm is used to adapt the traffic loads dynamically, and a multiple spanning tree based loadbalancing routing algorithm is used to adapt the traffic load changes and network failures automatically. 15 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. In [DPZ04], a new metric is presented for routing in multi-radio, multi-hop wireless mesh networks. The Expected Transmission Time(ETT) of a packet over a wireless link can be calculated from the loss rate and the bandwidth of the link. For a path consisting of n hops, ETT of these n hops can be simply added together to get the n cumulative ETT: ^ ETTi . However, the cumulative ETT only shows end-to-end i—1 delay. It can not show the impact of channel diversity. Assuming that if two hops on a path are on the same channel, then they always interfere with one another, in an n-hop path, the system has total of k channel, X j can be defined as: Xj = Y j ETTi 1,'s» / Meal) Router Mesh f o u le r jC^es^i Router M esh k o u ter ' / Mesh Router Mesh Router Mash Router wlt/i Gateway/Bridge • ... Mesh Router, wit/) Gateway/Bridge wiesn Kouier,w«fi,wat / Micro y. A <*etfk server sensor Micro sensor SB " “ r ,.<■ v ^ -10 ^ innulnn server nanen/ “^moving '••sen so r Sensor Network Sensor Network Figure 4.1: Wireless Mesh Network Topology active message format is shown in Figure 4.2. Dest field contains the node id of the destination node. The AM field contains the active message type of the application. For each TinyOS application, a unique number will be used as the active message type. Grp field is the group number of the destination node. Len is the total length of the packet. The length of data field in the packet could be l to 29 bytes. The CRC field is the cyclic redundancy check. If TelosB sensors are used, the format of active messages is slightly different. The TelosB active message format is also shown in figure 4.2. The extra fields in TelosB packets are fcfhi, fcflo, dsn and destpan. They stand for Frame Control Field High Byte, Frame Control Field Low Byte, Data Sequence Number (for ACKs) and Destination PAN Identifier respectively. These extra fields are used for 802.15.4 MAC protocol used by TelosB nodes. Micro servers can act in 2 modes: passive mode and active mode. Each mode will be described below. 31 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Destffl AM(1) Grp(l) Len(l) Data(0-29) Cic(2) General TinyOSPacket Format Len(l) Fdhi(l) Fcflo(l) Dsn(l) Destpan(2) AM(1) Grp(l) Destffl Data(0-28) TelosBTinyOSPacket Format Figure 4.2: Format of general TinyOS Packets and TelosB Packets 4.1 P assive M ode In passive mode, the gateway protocol maps UDP datagrams and active messages only. In passive mode, the client agent will be the only root of the code dissemination tree. The communication stacks of different entities in the protocol is shown in Figure 4.3. UDP will be used as the transport layer protocol in IP network. To make the IP network transparent to the sensor nodes, a virtual sensor node address will be allocated for the client agent. Before the application level message is sent down to the UDP layer at the client agent, an extra header called gateway header will be added to support the gateway protocol at the micro servers. The gateway header includes 4 fields: a source node address, a destination node address, a destination group address and an AM type. The source node address will be set to the virtual sensor node address of the client agent and the AM type is set to the AM type used by MDeluge. The gateway protocol at the micro server maps the UDP datagrams to active messages and vice versa. In active messages, the node address and AM type act similar roles as IP address and port number in UDP datagrams. The gateway protocol maintains a mapping table. Each entry in the mapping table contains an IP address, a port number, a node address and an AM type. When the micro server receives a UDP datagram from the IP network, it extracts its gateway header. Then the micro server sets up a new entry in the mapping table if no such entry already 32 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. MDeluge Transport GatewayProtocol Transport MAC MAC Physical ■I- Physical Client Agent MDeluge Client GenericCom GenericCom AMStandard AMStandard RadioStack,T RadioStack,R Micro Server Sensor Figure 4.3: Communication Stacks for Micro Servers in Passive Mode exists, using the IP address of the client agent, the port number of the MDeluge server application at the client agent, the virtual node address of the client agent and the AM type of MDeluge. Then the gateway protocol passes the application level message to GenericComm component along with the destination node address, destination group address and AM type. GenericComm will build the active message and send it down the active message system stacks. Because the active message does not support fragmentation itself, each application level message will fit into one active message. Fragmentation and reassembling mechanism is needed at the micro servers. When the gateway protocol receives an active m essage from WSN, it looks up the mapping table to find the entry with the corresponding node address and AM type. Then it adds the gateway header to the application level message, and uses the IP address and the port number in the entry to send the message to the client agent. 33 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.2 A ctiv e M od e Micro servers can act in active mode too. In active mode, the micro servers not only act as the gateways, but also aggregate, fragment and and reassemble the messages. Each micro server will be the root of a code dissemination tree. TCP can be used as the transport layer protocol between the client agent and micro servers. Once the client agent gets the code image to be injected into the sensor network, it allocates an MDeluge group address, and sends a code version message to all the micro servers through IP network. The MDeluge server application on micro servers will broadcast a code version message to the sensor network. When the micro servers are in passive mode, the fragmentation and reassembly will be done at the application layer, e.g. MDeluge handles pages and packets of the code data. In active mode, a new layer will be added above the active message layer to support fragmentation and reassembly. In this way, the application layer can send and receive a long message. The sink nodes will request the whole code image instead requesting one page at a time. When micro servers receive the code request messages, they check if they have the requested code image. If not, they request the whole code image from the client agent. Client agent sends the entire code image using TCP. Then the micro servers forward the code image to the sink nodes. Micro servers can send the whole code image in one application message in active mode. The new header to be added to support fragmentation and reassembly is called fragmentation header. Two-layer fragmentation is used. The long application message will be divided into datagrams and datagrams will be divided into fragments. Each datagram is comprised of 48 fragments and each fragment is carried within one active message. The fragmentation header has 4 fields: a 2 bits LF field, a 4 bytes sequence number field, a 2 bytes datagram offset field, and a 6 bits fragment offset field [MK06]. LF specifies the relative position of the datagram within the payload datagram. It is encoded as in Table 4.1. Sequence number will be the same for all the datagrams of the same application message. The datagram offset field specifies the 34 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table 4.1: Encoding of LF Field LF 00 01 10 11 Position Unfragmented First Fragment Last Fragment Interior Fragment offset of the datagram in the message and the fragment offset field specifies the offset of the fragment in the datagram. The reliable transmission can be achieved by sink nodes sending NACKs back to the micro servers if some fragments are not received within certain time. The NACK contains the seuqence number, datagram offset and a 6 bytes bitmap which indicates the missing fragments in the datagram. When micro servers are in passive mode, the processing load is mainly on client agent. So the passive mode can be used when we have micro servers with limited processing power and memory storage. When micro servers act in active mode, the processing load will be distributed from the client agent to multiple micro servers. So the active mode can be used when we have relatively powerful micro servers. 35 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Chapter 5 M D eluge Im plem entation We have implemented basic MDeluge design for TelosB motes [mot06]. In this chap­ ter, we’ll give the detailed description of the implementation of Mdeluge. The exper­ imental results for our implementation are shown at the end of this chapter. 5.1 O perating S ystem s and P latform s In our implementation, we chose TinyOS [LMP+04] as the operating system of the sensor nodes. TinyOS is designed to support the concurrency intensive operations required by networked sensors with minimal hardware requirements. It uses a com­ ponent based architecture. The TinyOS application is composed of a set of reusable system components and no binary kernel is used. The concurrency model provided by TinyOS is based on two threads of execution: tasks and hardware event handlers. Tasks are functions whose execution are deferred. Once scheduled, they run to com­ pletion and do not preempt one another. Hardware event handlers are executed in response to hardware interrupts and also run to completion, but may preempt the execution of tasks or other hardware event handlers. TinyOS supports Split-phase operations. Long latency operations like sensing and communication are all in split phase. The program can request to execute an operation using a command. The command returns immediately. After the operation is done, an event is signaled. 36 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. TinyOS supports different Berkeley modes like Mica2 [mic06a], Mica2Dot [mic06b], and TelosB, etc.. The programs for TinyOS are written in NesC [GLvB+03]. It is a language similar to C but with the support for components. In NesC, a component can provide and use interfaces. The interfaces in NesC are bi-directional. An interface declares a set of functions called commands that the interface provider must implement, and another set of functions called events that the interface user must implement. There are two types of components in NesC: modules and configurations. Modules provide application code and implement one or more interfaces. Configurations are used to wire the components together to assemble the application. NesC does not support function pointers, dynamic memory allocation. After an application is developed in NesC, the NesC compiler compiles it into a single C file. The C file can further be compiled using a C compiler, such as g++, into the binary code. [tin03] We use Stargate [cro06] as the micro server. The Stargate is a high performance processing platform. It has an Intel’s Xscal400MHz PXA255 Processor, a 51-pin Expansion Connector for MICA2 Motes, Ethernet, Serial, JTAG, USB Connectors via 51-pin Daughter Card Interface. It can use li-Ion batteries as the power source. Normally embedded Linux is used as the operating system for Stargate. To support Java application, ACUNIA’s virtual machine open-wonka and class library for Java needs to be installed on Stargate to supply the Java Runtime Environment. TelosB is the sensor platform we used in our implementation. A TelosB mote equips with a 250kbps 2.4GHz IEEE 802.15.4 Chipcon Wireless Transceiver, an 8MHz Texas Instruments MSP430 microcontroller (10k RAM, 48k Flash), an integrated onboard antenna with 50m range indoors / 125m range outdoors, optional integrated humidity, temperature, and light sensors. It also has a ST M25P80 40MHz serial code flash for external data and code storage. The flash holds 1024kB of data and is decomposed into 16 segments, each 64kB in size. [mot06] 37 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5.2 Form ats o f M essages We will define the formats of the messages used in MDeluge first. There are 4 kinds of messages in MDeluge: code version message, code request message, code data message and route update message. We use Active Message type 700,701,702,703 for code version message, code request message, code data message and route update message respectively. These numbers are chosen randomly because there is no administration of AM types now. The code version message format is shown in figure 5.1. The fields have the following meanings: SeqNum (2 bytes): sequence number of the version message. SrcAddr (2 bytes): this field contains the node ID of the node which broadcasted this message. PreAddr (2 bytes): node ID of the previous node from which this message is received. TTL (1 byte): time to live field. It is used to control the network area that will be influenced by the broadcasting. GrpAddr (1 byte): MDeluge group address allocated for this code image. RImgNum (1 byte): running image number indicates which image should be run­ ning on this type of the sensor nodes. Type (1 byte): which type of sensor nodes this code image is for. imgDesc: description of image information. It contains 7 fields: uid (4 bytes) is the unique ID of the image; vNum (2 bytes) is the version number of this image; imgNum (1 byte) is the number of this image; numPgs (2 bytes) is the number of the pages of this image; crc (2 bytes) is cyclic redundancy check; numpgsComplete (2 bytes) is the number of pages the source node contains; and there is a reserved field (1 byte). This supports up to 65536 pages, which would be enough for TinyOS applications. The route update message has the same format as the code version message except 38 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. SeqNum SrcAddr PreAddr TTL GrpAddr RImgNum vNum imgNum numPgs Type ere imgDesc QumPgsC reserved omplete Figure 5.1: Format of Code Version Message SeqNum SrcAddr PreAddr TTL Figure 5.2: Format of Route Update Message it does not contain any version information. The packet format of route update message is shown in Figure 5.2. The code request message format is shown in figure 5.3. The fields have the following meanings: Root (2 bytes): node ID of the root which is the final destination of this message if no intermediate nodes have the requested code. PreAddr (2 bytes): node ID of the previous node from which this message is received. ReqAddr (2 bytes): node ID of the sink node who requests the code. GrpAddr (1 byte): MDeluge group address this sink node is in. pgNum (1 byte): requested page number. B itm ap (6 bytes): a page contains 48 packets. Each bit in th e bitm ap indicates if that packet is needed by the request node. The code data message format is shown in figure 5.4. The fields have the following meanings: GrpAddr (1 byte): MDeluge group address allocated for the code imagef. pgNum (1 byte): page number of the code. 39 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Root ReqAddr PreAddr GrpAddr pgNum Bitmap Figure 5.3: Format of Code Request Message G rpA dd r pgN um p k tN u m D a ta Figure 5.4: Format of Code Data Message pktNum (1 byte): packet number of the code. Data (25 bytes): code data. 5.3 Im p lem en tation o f M D elu ge Server MDeluge server is implemented in Java. It has two states: idle and sending. Each micro server maintains a timer to broadcast the code version messages or route update messages periodically. Here we will use code version messages as an example. The micro server will start in idle state. Once the timer expires, it will broadcast a code version message if it is in idle state. If a code request message is received, the micro server will wait for server wait time W and change to sending state to send the requested page. It does not change to sending state immediately so that if multiple request messages for the same page are received, the code needs to be sent only once. In sending state, if the timer expires or another code request message is received, the code version m essage or the code data messages to be sent will be cached. After sending the page, the micro server will check if any messages are cached. If yes, it will send the cached message. Otherwise the micro server returns to idle state. 40 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5.4 Im p lem en tation o f M D elu ge C lient The MDeluge Client is implemented in NesC. The code size is 40064 bytes in all. After installation ,MDeluge will have 21080 bytes in ROM and 781 bytes in RAM. Its code size is a little bit larger than Deluge whose NesC code is 39413 bytes (20590 bytes in ROM, 599 bytes in RAM). T hat’s because MDeluge needs extra memory to maintain the routing table and it also needs to buffer the messages to be forwarded, A single configuration component called MDelugeC is wired to StdControl. The components relationship of MdelugeC is shown in Figure 5.5. MDelugeM component handles the event of receiving code version messages sig­ naled by GenericComm module using ReceiveMsg interface. When it receives a ver­ sion message, it first checks if it has received this message before by comparing the sequence number. If it has received the message with the same or smaller sequence number, the message will be discarded. Otherwise, the node rebroadcasts the mes­ sage using SendMsg interface provided by GenericComm and SharedMsgBuf interface provided by ShareMsgBufM. It also uses NodeTable interface provided by component NodeTableC to record the parent node and the root. When a node receives a new code version message, it checks if the code version message contains the version information for it. If the message contains its version information, the node will compare the version information in the message with the code images it has to see if it has the latest version. We use DelugeMetadataC com­ ponent which provides DelugeMetadata interface and InternalFlashC which provides InternalFlash interface from Deluge to get and set node’s current version information stored in Flash memory and processor. If some code images are missing or some code images need to be updated, the node notify the MDelugePageTransferC component to request the needed image with the lowest image ID using MDelugePageTransfer in­ terface. After the code image is complete, MDelugePageTransferC will signal an event to MDelugeM component so that MDelugeM can use NetProg interface provided by NetProgC component to load the new image. 41 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. M ain N etP rogC NetFrog Ledi StdContiol DelugeMetadata MDelugeM StBCoiiW M ^^pg^i5 lr^^^ePageTran»ftS>- SendMsg ®e: Random Figure 5.5: Component Relationships of MDeluge Client StdContiol __ StdContiol MDelugePageTnmsfer / \ RequestTable RequestTableC BitVecUtils BitVecUtilsC RacekeMsg DelugeDataRead M M sg DelugeDatawnte PelugaStorageCT) C M D e^geP a g e T t a n s ^ X , (\ \ \ s ' _ SendMsg v, ^ SlwredMsgBuf s" Leds \ RscewiMsg ^ C M D elugeP ageTransfeiM , / 1 ^ ^ / DelugeStats Random Tunei / NodeTablie PendingTable (^DejugeMetadat^^1 RandomLFSR TimeiC NodeTableC S> PendsngTibleC Figure 5.6: Component Relationships of MDelugePageTYansfer in MDeluge Client 42 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The components relationship of MDelugePageTransferC is shown in figure 5.6. We have 3 more components than the DelugePageTransferC of Deluge code: NodeTable, RequestTable and PendingTable. NodeTable and RequestTable record the routing information of the parent and downstream nodes respectively. PendingTable is used to buffer the data message. It handles the receipts of code request messages and code data messages. MDelugePageTransferM maintains three states: idle, sending and requesting. It starts in idle state. When it receives a new code request message event signaled by GenericComm, it checks if it has the requested page of the code by using Del­ ugeMetadata interface. If it has, it transitions to sending state and responses with the requested page in code data messages. If it has not, it forwards the message with the routing information in node table using NodeTable interface. When a node is in idle state and receives a code data message, it checks its request table using Request­ Table interface and forwards the message according to the corresponding entries. If no entry is found, the code data message will be discarded. When a sensor node enters requesting state, it will start a request timer using Timer interface provided by TimerC component. If after request Interval R, the requested page has not been completely received, the request timer will expire and the node will resend a code request message. If a node is in requesting state and receives a code request message, it checks if it has the page requested. If it has it, it will cache code data messages for the page using PendingTable interface. If not, it will check its request table using RequestTable interface. If an entry with the same requesting node id is found, it refreshes and updates the entry. It adds a new entry in the request table if the requesting node id is not found in the table. The code request message will be discarded if the node itself is requesting the same page of the code. Otherwise, the message will be forwarded to the root. If a node is in requesting state and receives a code data message, it checks if it is the data the node is requesting. If not, it routes the message to the sink nodes or discards it if no sink nodes are found in the request table. If it is the data the node is requesting, the node will cache the 43 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. data in the memory. After receiving the whole page, the sensor node will check the request table to see if there are any sink nodes that are requesting that page and also check if there are cached messages to be sent. It will transition to sending state, and send the cached messages if needed or transition to requesting state to request the next page of the code image if cached messages to be sent and the new code image has not been completed. It transitions to idle state if cached messages need to be sent and the new image is full. In sending state, the sensor nodes send the code data messages. If a sensor node in sending state receives a code request message requesting the page it has, it will cache the code data messages to be sent back. If it receives a code data message which needs to be forwarded, it will also cache it. After sending the page, it will check if there are any cached messages. If there are, it will keep sending all the cached messages out. Then it checks if the code image is completely received. If it is not completed yet, it transitions to requesting state, and sends the code request message. If the image is completed, it transitions to idle state. 5.5 E xperim ent We did the experiment to test the code dissemination time of MDeluge in the UNBC wireless sensor network lab. A Stargate is used to be the micro server. A TelosB mote with TOSBase application installed is plugged into the USB port of Stargate so that the Stargate can communicate with TelosB sensor network through TOSBase mote. The MDeluge server is running on the Stargate. MDeluge client is installed on 5 TelosB sensors and these sensors are deployed around the MDeluge. The farthest sensor is two hops away from the Stargate. The server wait time is set to 0.1s and the request interval is set to 1.5 s. We also developed a simulation model of Mdeluge in NS2.29. The NS2 simulation model of MDeluge uses the same parameters as the implementation. We compared the implementation result with the experiment result. The result of code dissemination time for different size of code image is shown 44 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table 5.1: Code Dissemination Time of MDeluge Experiment Experiment Hop Count P=1 P=5 1 1.96 10.15 2 2.02 10.26 P=10 20.04 20.29 P=1 1.96 1.99 Simulation P=5 P=10 9.66 19.25 9.68 19.28 in Table 5.1. The time is in seconds and s means the result of simulation. With the increase of code size, the code dissemination time increases as in Table 5.1. The larger hop count from the sink node to the micro server will slightly increase the code dissemination time. The experiment result and the simulation result quite match. The experiment result is a little longer because the flash memory read and write time is neglected in the simulation. 45 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 6 Perform ance A nalysis In this chapter we will present the performance analysis of MDeluge. The concept of message cost will be introduced first and then a grid structured sensor network will be used for analyzing. 6.1 M essage C ost and Grid Structure The energy consumption is the most important concern for code dissemination. Be­ cause most of the energy used for code dissemination will be used for message sending and receiving, we will use message cost as a scale to evaluate the energy consumption. Message cost is defined as one unit for message transmission and one unit for message reception as in [IGE+02], The deployment pattern of WSN depends on the specific application. For sim­ plicity, we use a grid structure in our analysis. N is the total number of nodes in the grid. So the sensor network will be a \/N by \/~N grid, as in Figure 6.1. The top right node is a micro server with MDeluge server running on it and the other nodes are sensors with MDeluge client running on them. 46 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. M icro \Server Figure 6.1: Grid Topology of sensor network 6.2 A n alytical R esult The flooding of the code version messages in MDeluge will cost N messages. A wireless link connects two nodes and each of them will broadcast the message once, so message will be received twice over a link. The total receptions of the messages are 2n where n is the total link number in the sensor network. The total link number n can be calculated. There are y/N rows in the grid and each row has \/jV —1 horizontal links, so the total horizontal links will be will be \/N (y /N —1). Similarly, the total number of vertical links will be \/N (y /N —1) too. The grid has (y/N —1) * (y/N — 1) cells and each cell has 2 crossing links. The total number of crossing links in the cells is 2(y/N —1) * (y/N — 1). Adding them together, we get the total number of the links which is 2 - 1) + 2(y/N - 1) * (V N - 1) = 2(V N - 1)(2V N - 1) The total message cost for code version message would be Cver = N + 2n = N + 4{V N - 1){2-/N - 1) Let us denote the new code image has p pages and each page has q packets. The 47 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. transmission rate for a sensor is M bps. We will use the general TinyOS packet which has the size of 36 bytes. For a node h hops away from root, the transmission time of a code request message from the node to the root Tr is 36 * 8 * h /M if we neglect the propagation and queuing delay. The transmission time of a page Td would be 36 * 8 * q * h /M if no packets are lost. So ideally, the code dissemination time for each page would be Tp = 36*s*(M q'>—. However, due to the random jitter before packet transmission, the code dissemination time would be longer than the pure total transmission time. If the interval T for a sensor node to resend the code request message is well configured, there will be T > Tp, so that if none of the code data messages are lost, the code request message will not be resent. Otherwise, the code request messages will be sent 3 6 * 8 * (l+ q )* h MT + 1 times for each page. The code request messages are unicasted, so the cost of code request messages for the whole image will be a req ( 36 * 8 * (1 + q) * h + l)*h*p*2 MT The cost of code data message for the whole image C data = 2 * q * h * p The total message cost C will be C = Cver + Creq + Cdata 48 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 7 Sim ulation of M D eluge In this chapter, we show the simulation results of MDeluge in stationary WSN and in WSN with moving sensors as well. The result shows that MDeluge meets design requirement well. It performs better than Deluge to disseminate the code image into a group of sink nodes. 7.1 S tation ary W S N We implemented MDeluge in NS 2.29 to study its performance. NS 2.29 is the current release of NS2 at the time of writing. We also developed simulation models of Deluge in NS2 to compare the results of dissemination time and message cost. The TelosB sensor nodes will be simulated. 802.15.4 is used as the MAC layer protocol. The transmission rate is set to 250kbps to simulate the 250kbps 2.4GHz IEEE 802.15.4 chipcon wireless transceivers on TelosB sensors and the transmission range is set to 125m for outdoor scenarios. In real life, the pattern of WSN deployment will be determined by the specific scenario it will be used. In our simulation, we used a grid scenario as in Figure 6.1. Node 0 is the micro server. The sensor nodes are spaced 80 meters apart. The code image to be disseminated contains 5 pages. The page size is set to 24 packets to reduce the simulation time. The server wait time is 0.1 second and the client’s request interval is set to 1.5 seconds. 49 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table 7.1: Message Cost for Different Sink Node Hop Count 1 2 3 4 C (Simulation) 461 698 951 1222 C(Analysis) 419 669 919 1169 We first simulated with a single sink node. In the code dissemination tree that is built by node 0, there is a link 0-6-12-18-24. We will use 0,6,12,18,24 respectively as the sink node so we can get the different hop counts from the sink node to the micro server. We compare the simulation result of the message cost C with the analysis in Table 7.1 with different hop counts from the sink node to the micro server. The simulation result is larger because the analysis does not take into account message loss and collision. For Deluge, the message cost is always 7263. That is much larger than MDeluge because the code will be disseminated into all the nodes in Deluge and that will cost a lot of extra messages. Table 7.2 shows the dissemination time with different hop counts from the sink node to the micro server. The MDeluge has a shorter dissemination time than Deluge. There are several reasons. The pipelining of Deluge make the sink node propagate the pages it received to the further irrelevant nodes before it can request the other pages while in MDeluge the pipelining only happens at sink nodes. MDeluge also has smaller message cost so that the probability of message collision and retransmission is smaller. The Trickle protocol used by Deluge to suppress the total number of messages also increases the delay. We then simulated the scenario with multiple sink nodes. The code size and the topology is the same as described above. We simulated the cases with a 2*2 grid sink nodes of 6,7,11,12, a 3*3 grid sink nodes of 6,7,8,11,12,13,16,17,18 and a 4*4 grid sink nodes of 6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24. In Table 7.3, we show the result of dissemination time. For Deluge, the code dissemination time mainly depends 50 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table 7.2: Code Dissemination Time for Different Sink Node Hop Count 1 2 3 4 Deluge Time (s) 15.93 20.72 21.32 21.72 MDeluge Time (s) 9.66 9.68 9.72 9.74 Table 7.3: Code Dissemination Time for Different Numbers of Sink Nodes Sink Nodes 2*2 3*3 4*4 Deluge Time (s) 22.57 22.60 24.71 MDeluge Time (s) 17.26 22.19 24.13 on the hop count from the farthest sink node to the micro server. For MDeluge, it also depends on the number and the deployment pattern of sink nodes. When the sink node number and the hop count from the farthest sink node to the micro server increases, the dissemination time of both MDeluge and Deluge increases. MDeluge still has a better performance than Deluge. In Table 7.4, we show the result of message cost C. The message cost of MDeluge depends on the number and the deployment pattern of sink nodes too. With the grid structure of sink nodes, when the number of sink node increases, the message cost of MDeluge increases as in Table 7.4. Deluge still has a larger fixed message cost because it always disseminates the code into all the sensor nodes. Table 7.4: Message Cost for Different Numbers of Sink Nodes Sink Nodes 2*2 3*3 4*4 C (Deluge) 7263 7263 7263 C (MDeluge) 1566 3041 4636 51 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Span 500 m N 23500 m S 23000 m W 57000 m E 57500 m Figure 7.1: 500m*500m city area environment 7.2 W S N w ith M oving Sensors We will use a 500m*500m city area of Figure 7.1 for the simulation of MDeluge with mesh network support. A grid of mesh routers will be deployed in this area. In Hyacinth (IEEE 802.11 based multi-channel wireless mesh network) [RC05], a node model with multiple interfaces and multiple channels is developed in NS-2.1b9a. We ported the node model into NS2.29. We also modified the AODV model in NS2.29 to use the new routing metric MCR [KV06, DPZ04] as the routing model for the mesh router. The topology is generated by Vanet [SJ04]. There are several roads in this city area as shown in Figure 7.1, 50 nodes will be moving on the roads with the fixed speed. The mesh routers are spaced 80 meters apart and each mesh router has 3 NICs. One is the fixed NIC and two are the switchable NICs. The channel switching time is 1ms. The upper left mesh router will be connected to the Internet as the gateway mesh router. Each mesh router connects with a micro server. The micro servers work in active mode. The MDeluge parameters are shown in Table 7.5. We show the code dissemination time and message cost for different code sizes and sink node numbers in Figure 7.2 and 7.3 respectively. The code dissemination time increases slightly when the sink node number increases. Without mesh network 52 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Table 7.5: MDeluge Parameters Parameter N S w B BTTL R s P Name number of sink nodes code image size server wait time beacon interval TTL of route updates request interval speed of sensor nodes parent threshold Value 30 10 pages 0.1 s 5s 2 1.5 s 2 m/s 100m 140 120 100 CO a> E P N = 10 N = 20 N = 30 20 N = 50 Code Size (Pages) Figure 7.2: Code Dissemination Time for Different Numbers of Sink Nodes with Mesh Network Support 53 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. E 0.8 0.6 0.4 0.2 Code Size (Pages) Figure 7.3: Message Cost for Different Numbers of Sink Nodes with Mesh Network Support support, the hop counts from the micro server to the sink nodes may increase with the increasing of sink nodes. But with mesh network support, most sink nodes will be one or two hops from the micro server no matter how many sink nodes in the scene. The code dissemination time increases because the collisions and retransmissions of messages increase with the increasing of sink nodes. With the increasing of code size, the code dissemination time increases as in Figure 7.2. The message cost also increases when the code size and sink node number increase as in Figure 7.3. We then varied the server wait time W. The code dissemination time is shown in Figure 7.4 and the message cost is shown in Figure 7.5. With the increasing of the server wait time, the in-network aggregation reduces the unnecessary retransmissions of data messages, which reduces the code dissemination time too. So both the code dissemination time and message cost decrease first. The longer server wait time will increase the server response time, which increases the code dissemination time. With the increasing of the server wait time, the code dissemination time will reach the lowest value and starts to increase. With the increasing of code dissemination time, the number of request messages and route update messages will increase. So the 54 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 150 S = 10 ■e— s * 1 5 H— s = 20 'V 100 - © E V -e- 50 - 00 0.5 1.5 2 Server Wait Time (s) Figure 7.4: Code Dissemination Time for Different Server Wait Time with Mesh Network Support message cost will start increasing after it reaches the lowest value. The code dissemination time and message cost for different request intervals are shown in Figure 7.6 and Figure 7.7. When the request interval is too small, the message cost is very high because too many request messages are sent and the proba­ bility of collisions and retransmissions of messages is high. This will increase the code dissemination time. When the request interval increases, the message cost and code dissemination time will decrease. The longer request interval will increase the retrans­ mission time for lost data messages, so after the code dissemination time reaches the lowest value, it will start increasing. We simulated static sensor nodes, sensor nodes with speed of 2 m /s as the nodes on pedestrian, 5 m/s, 10 m /s and 20m/s sensor nodes as nodes on vehicles with different speed. The message cost is shown in Figure 7.9. With longer beacon interval, the number of route update messages will decrease which makes the message cost to decrease. The code dissemination time is shown in Figure 7.8. With longer beacon interval, the repairing time of broken links will increase, which will make the code dissemination time to increase. In Figure 7.8, the code dissemination time does not 55 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. x 105 S = 20 % O o 8 0 5 0.5 2.5 Request Interval(s) Figure 7.7: Message Cost for Different Request Intervals with Mesh Network Support change much with the increasing of beacon interval when the sensors are static or the speed is low. For fast moving sensors, the increasing of beacon interval will increase the code dissemination time sharply. Because when the sensors are moving fast, the topology changes dramatically. If the beacon interval is long, the time used to rebuild the gradients from the sink nodes to the source node will be long. 57 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 120 s =0 110 100 s =55 s = 10 s = 20 W Application could be MDeluge or Deluge. All the sensors will initially be assigned to the same type which is represented by an integer of sensor type. A TCL file called grid.tcl will be generated. 68 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5. Run the simulation, ns grid.tcl A .2 Sim ulation o f M oving Sensors 1. Extract ns-2.29_moving.tar.gz file into the NS 2.29 folder. The TCL file for simu­ lation is ab.aodv_example.tcl in a folder named trickle. tar xzvf ns-2.29_moving.tar.gz 2. Compile ns2. Change directory to ns2-29. make 3. The traffic model can be generated by Vanet software. To use Vanet, first extract Vanet.tar.gz. tar zxvf Vanet.tar.gz 4. Compile Vanet. Step 1. make clean Step 2. make depend Step 3. make Step 4. Verify that an executable by the name of ’road-scen-gen’ has been created. 5. Generate the traffic model. ./road-scen-gen Cinput file> The ’input file’ required by road_scen_gen is generated by running two scripts present in ./Scripts/ directory: the ’chop.bash’ script and the ’cutout.bash’ script. The in­ structions for these scripts are present in Vanet2004/Scripts/README. 6. Copy the generated traffic model to your working directory and modify the ab_aodv_example.tcl file to source the file of the traffic model. 7. Run the simulation. 69 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. ns ab_aodv_example.tcl A .3 U se M D elu ge 1. Extract the tinyos-l.x.tar.gz to TinyOS source folder, tar zxvf tinyos-l.x.tar.gz 2. Set up the TOSBase mote. Step 1. Plug one TelosB mote into the USB port of the host. Step 2. Change directory to tinyos-l.x/apps/TOSBase. Step 3. Install the TOSBase application and assign the base node with nodelD 0. make telosb,0 install Step 4. Unplug the mote. 3. Set up MDeluge client motes. Step 1. Plug the TelosB mote into the USB port of the host Step 2. assign a sensor type for the client mote, export MDeluge_TYPE= Step 3. Format the flash memory. Change directory to tinyos-l.x/apps/TestMDeluge/FormatFlash. make telosb, install Step 4. Install MDeluge client application. Change directory to tinyos-l.x/apps/TestMDeluge/DelugeBasic. make telosb, install Step 5. Unplug the TelosB mote. This procedure is repeated for all the MDeluge client motes. 4. The code image can be generated using the Deluge tool. Step 1. Change to the direcotry of the application you want to use. Step 2. Add a line this line into the configuration file: Main.StdControl -> DelugeC; Step 3. make telosb 5. Plug the TOSBase mote into the USB port of the host and start SerialForwarder 70 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. java net.tinyos.sf.SeerialFowarder -comm serial@ :telosb 6. Inject the code Image. java net.tinyos.tools.MDeluge -inject -tosimage= -imgnum= -imgnum= -type= 7. Reboot the sensors. Java java net.tinyos.tools.MDeluge -reboot -imgnum=Cimage number> -type= 71 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. A ppendix B List of A cronym s AC - Access Controller ACK - Acknowledge AM - Active Message AODV - Ad-hoc On-demand Distant Vector AP - Access Point ASVM - Application Specific Virtual Machine ATaG - Abstract Task Graph CAPWAP - Control and Provisioning of Wireless Access Points CAPWAPHP - Control and Provisioning of Wireless Access Points Handover Proto­ col DSR - Dynamic Source Routing DTIMs - Delivery Traffic Indication Message DYMO - Dynamic MANET On-demand E E P R O M - E le c tr ic a lly E r a s a b le P r o g r a m m a b le R e a d - O n ly M e m o ry ETT - Expected Transmission Time I/O - Input/O utput IP - Internet Protocol LS - Location Server MAC - Medium Access Control 72 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. MCR - Multi-Channel Routing MDeluge - Multicast Deluge MN - Mobile Node MOAP - Multihop Over-the Air Programming NACK - Negative Acknowledge NIC - Network Interface Card NS - Network Simulator PA - Paging Agent PAN - Personal Area Network PSFQ - Pump Slowly, Fetch Quickly RAM - Random-Access Memory RMST - Reliable Multi-Segment Transport RREP - Route Reply RREQ - Route Request RTT - Round-Trip Time SIP - Session Initiation Protocol SRM - Scalable Reliable Multicast UDP - User Datagram Protocol WCETT - Weighted Cumulative Expected Transmission Time WLAN - Wireless Local Area Network WMN - Wireless Mesh Network WSN - Wireless Sensor Network WTP - Wireless Termination Points TA - Tracking Agent TCP - Transmission Control Protocol TIM - Traffic Indication Map TTL - Time To Live UMTS - Universal Mobile Telephone System VM - Virtual Machine 73 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.