Docteur de l Université Paris 6. Saoucene Mahfoudh. Jury: - PDF

THESE DE DOCTORAT DE L UNIVERSITÉ PARIS 6 PIERRE ET MARIE CURIE to obtain the degree of Docteur de l Université Paris 6 Discipline: Computer Science Host laboratory: INRIA Rocquencourt by Reviewers: Saoucene

Please download to get full document.

View again

of 149
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Government & Nonprofit

Publish on:

Views: 9 | Pages: 149

Extension: PDF | Download: 0

THESE DE DOCTORAT DE L UNIVERSITÉ PARIS 6 PIERRE ET MARIE CURIE to obtain the degree of Docteur de l Université Paris 6 Discipline: Computer Science Host laboratory: INRIA Rocquencourt by Reviewers: Saoucene Mahfoudh Title: Energy efficiency in wireless ad hoc and sensor networks: routing, node activity scheduling and cross-layering Thesis Director: M. Mario Gerla M. David Simplot-Ryl Pascale Minet Jury: Examiners: M. Tuan Dang M. Philippe Jacquet Ms. Pacale Minet M. Michel Misson M. Guy Pujolle Ms. Leila Saidane To my parents: Alaya Mahfoudh and Samira Hassouna To my husband and son: Walid and Hamza Ridene i Acknowledgements It is with great pleasure and felicity that I would like to express thanks to all people who have made this thesis possible. First of all, I want to express my deep gratitude to Ms. Pascale Minet, my advisor, for her excellent support, her advice and guidance during this research. Her constant availability, academic rigor and experience helped me to develop excellent research habits and gave me the will and the power to reach success. I can not thank her enough for her direction. I would like to thank Mr. Philippe Jacquet for providing me the opportunity to be a member of his team. My cordial thanks go to Mr. Mario Gerla and Mr. David Simplot-Ryl for accepting to review my thesis. I would also like to thank Mr. Tuan Dang, Mr. Philippe Jacquet, Mr. Michel Misson, Mr. Guy Pujolle and Ms. Leila Saidane who honored me by accepting to be part of my thesis committee. I would like to express my gratitude to all the member of Hipercom team for the exceptionally friendly working environment. Thanks to Christine Anocq for her availability and help in administratif tasks. Thanks to Amina, Cedric, Skandar, Ichrak, Anis, Paul, Yasser, Yassine and Salman. Working with you was a great pleasure. A special thank goes to my husband, Walid Ridene for his support, understanding and encouragement throughout all my thesis and all the happiness and the love that he brings to my life. Last but not least, I want to thank my parents, Alaya Mahfoudh and Samira Hassouna. Their faith in me has encouraged me to go after my dreams. Thanks to my sister Salma, my brothers Slim, Mohamed, Houssem and all my family, especially Khaled and Olfa, for their constant motivation. My love and reverence for them. ii Contents LIST OF FIGURES ix LIST OF TABLES x 1 Introduction Motivation Specificities of wireless ad hoc and sensor networks Differences between wireless ad hoc and sensor networks Problem Statement Contributions Thesis organization Energy efficiency: State of the art Introduction Definition of network lifetime Energy consumption model Energy consumption in wireless networks Energy states Reasons of energy consumption in the network Classification of energy efficient techniques Energy efficient routing Node activity scheduling Topology control by tuning node transmission power Reduce the amount of information transferred Cross layering optimization Analysis of node energy consumption distribution Discussion Conclusion iii 3 Energy efficient routing Introduction Related work Multipath routing protocols Adaptive hop-by-hop routing protocols EOLSR: Energy efficient extension of OLSR OLSR functioning overview Why OLSR is not energy efficient? Principles of EOLSR Energy consumption model Energy efficient selection of MPRs Routing algorithm for EOLSR Optimized broadcasts EOLSR design Performance evaluation of EOLSR Comparison of EOLSR with MinEnergy and MaxP acket Comparative performance evaluation of EOLSR with multipath routing strategies Energy consumption distribution EOLSR for data gathering applications Maintaining routes only to strategic nodes Applicability of this optimization Conclusion Node activity scheduling Introduction Graph coloring: state of the art Vertex coloring Edge coloring Graph coloring applied to wireless sensor networks SERENA: Scheduling Router Node Activity Two hop coloring algorithm Slot assignment algorithm Message exchanged and information maintained in SERENA Performance evaluation of SERENA Comparison with TDMA and USAP SERENA in a real wireless network environment Support of immediate acknowledgement: Extension to three-hop coloring algorithm Coloring algorithm with unidirectional links iv 4.5 Color conflict detection and resolution Causes of a color conflict Principles of detection and resolution of color conflict Synchronization Conclusion Node activity scheduling for data gathering applications Motivations SERENA adaptation to data gathering applications Principle Messages exchanged Information maintained by each node Algorithm Computation of the number of colors Comparison with another tree coloring algorithm Performance evaluation Benefit brought by coloring Adaptivity of the coloring algorithm The optimized coloring algorithm for tree topologies General principles Comparison with TDMA-ASAP Generalization Network dimensioning with network calculus Network calculus Comparison of our algorithm with ZigBee Conclusion Cross layering and integration of energy efficient techniques Introduction State of the art Cross layering with EOLSR Routing and application cross layering Routing and MAC cross layering Routing and energy management cross layering Cross layering with SERENA SERENA and application layer cross layering SERENA and MAC layer cross layering Synthesis Application to the OCARI project Project description The OCARI network and its architecture v 6.6.3 NwCARI: Energy efficient network layer Conclusion Conclusion and perspectives Conclusion Perspectives vi List of Figures 2.1 Distribution of node energy consumption without sleeping state Number of multipoint relays per node, function of network density Number of multipoint relays per node, function of node number Number of TCs received per node Number of TCs forwarded in the network Network lifetime with and without the optimized broadcast Impact of the EMPR selection strategy on the network lifetime Comparison of the EOLSR network lifetime with MinEnergy and MaxP acket Comparison of the EOLSR data delivered with MinEnergy and MaxP acket Multipath routing Comparison of network lifetime with EOLSR, DN and DL versus OLSR Comparison of delivery rate with EOLSR, DN and DL versus OLSR Distribution of node energy consumption without sleeping state Building route to reach the strategic node Local repair routes to reach the strategic node Number of TCs received per node per TC period in strategic and generic modes Number of TCs sent per MPR node per TC period in strategic and generic modes Vertex coloring Edge coloring Number of colors used Number of rounds Number of colors used Number of rounds Distributed vs centralized slot assignment algorithm A wireless network and its coloring Node activity time Impact of SERENA on network lifetime Impact of SERENA on delivered data Slot assignment and traffic rate vii 4.13 Slot reuse Distribution of energy consumption with SERENA Network lifetime with SERENA and USAP Amount of user data delivered with SERENA and USAP Slot assignment Node throughput obtained with SERENA and USAP Collision with two-hop coloring and immediate acknowledgement Number of colors used Number of rounds needed Type 1 color conflict between A and B causing a collision in B Type 2 color conflict between A and C causing a collision in C Type 3 color conflict between A and C causing a collision in B Type 4 color conflict between A and D causing a collision in B Number of conflicts per type Number of conflicts per SERENA variant TDMA/CA behavior when (a) a desired frame is captured, (b) an undesired frame is captured or (c) a collision occurs Colors assigned to a tree of 15 nodes Slots assignment Tree colored with our algorithm Tree colored with the other algorithm Comparative evaluation of the number of colors used by the Desc(N) and N 3 (N) algorithms Number of colors as a function of the number of nodes and the density Number of colors as a function of the tree depth and the density Average number of messages sent per node The active period in the polling cycle Duration of the active period as a function of the number of nodes Different collision cases Number of colors as a function of the number of nodes Number of messages as a function of the number of nodes Delay and backlog bounds ZigBee superframe structure A colored tree Bandwidth reserved with and without our algorithm Buffer dimensioning at each router with and without our algorithm Maximum delay per hop and maximum end-to-end delay Interaction between adjacent and non adjacent layers Cross-layering architecture with cross-layer entity viii 6.3 Topology of an OCARI network OCARI architecture Global cycle OCARI application architecture Network lifetime ix List of Tables 2.1 Power value in each radio state Classification of energy aware routing protocols [15] Parameters used for simulation Power value in each radio state Parameters used for simulation Parameters used for simulation Parameters used for simulation Number of slots assigned per node Parameters used for simulation Maximum throughput in Kbps obtained by a node x Chapter 1 Introduction 1.1 Motivation Wireless networks play a crucial role in the communication systems nowadays. Wireless networks are being increasingly used in the communication among devices of the most varied types and sizes. User mobility, affordable-ity, flexibility and ease of use are few of many reasons for making them very appealing to new applications and more users everyday. In this work, we consider only wireless networks capable of operating without the support of any fixed infrastructure. We also consider the general case of multi-hop networks. More precisely, we will consider wireless ad hoc networks as well as wireless sensor networks. The diversity of the applications supported by wireless ad hoc and sensor networks explain the success of this type of network. These applications concern as various domains as environmental monitoring, wildlife protection, emergency rescue, home monitoring, target tracking, exploration mission in hostile environments, etc. However, the most critical requirement for adopting such networks is energy efficiency. Indeed, some nodes are battery operated and battery replacement can be difficult, expensive or even impossible. The goal of communication protocol designers is then to maximize the lifetime of such networks Specificities of wireless ad hoc and sensor networks Wireless ad hoc and sensor networks have in common some characteristics that have to be taken into account by energy efficient techniques: Lack of pre-configuration: A wireless ad hoc and sensor network is a collection of wireless nodes that can dynamically self-organize into an arbitrary and temporary topology to form a network without using any pre-existing infrastructure. Wireless communication: which has the following properties: 1 Radio interferences: Indeed, when a node N 1 is transmitting to a neighbor node N 2, no other node in the transmission range of N 1 can receive another frame. Similarly, no other node in the transmission range of N 2 can send another frame. Radio link versatility: as the propagation conditions change very frequently, the quality of a radio link varies strongly in the time. Limited bandwidth: the wireless bandwidth has a capacity much smaller than a wired one due to the shared nature of the wireless channel and interferences. Scalability: Communication protocols should be able to support large (i.e. a high number of nodes) or dense (i.e. a high number of neighbors per node) wireless networks Differences between wireless ad hoc and sensor networks While wireless sensor networks share many commonalities with existing ad hoc network concepts, there are also a number of differences and specific challenges: Applications. The main difference between common ad hoc networks and wireless sensor networks is their different area of application. In fact, a sensor network is characterized by its strong interaction with its environment. For this reason, it can be used in a large number of applications [1] like: Indoor/outdoor environment monitoring, Monitoring of buildings/bridges/airplanes for structural integrity, Ubiquitous computing for healthcare applications, Sensing within factory environments, Sensing for transportation applications, Warehouse and retail inventory management, Interactive museums/exhibits, etc. Constraints. Constraints in wireless sensor networks are stronger than in ad hoc networks because of the miniaturization of sensor devices: Limited memory/storage. Limited processing capacity. Radio transceiver: the radio range is generally shorter (20m in versus 250m in b). Low rate: 250 kbps in versus 11Mbps in b. Limited energy: The energy constraint in wireless sensor networks is stronger than in ad hoc networks. This is because, sensor networks are usually deployed in hostile environment or the number of nodes in the network can be very important. Consequently, changing the nodes batteries can be very difficult, expensive or even impossible. 2 Mobility support: It is an evident requirement for VANETs (Vehicular Ad hoc Networks), for instance. It is usually not required in many wireless sensor networks: in these networks, either all nodes are fixed or a very limited number of them is allowed to move. 1.2 Problem Statement In wireless ad hoc and sensor networks, nodes working only with battery power will die after battery exhaustion. This means that the network has a limited lifetime. One of the main challenges facing the network designers in wireless ad hoc and sensor networks is to maximize the network lifetime. Our work is centered on energy efficient techniques that will prolong network lifetime. Several classes of energy efficient techniques exist. Among them topology control assumes that the MAC layer is able to tune the transmission power of the node. In this work, we do not make such an assumption: the sender always transmits with the maximum transmission power. In the following, we focus on the three other energy efficient classes: energy efficient routing, node activity scheduling and optimization of the volume of data transferred. The specificities of the wireless ad hoc and sensor networks make difficult the design of communication protocols and in particular energy efficient ones. They also lead to favor simple techniques: protocols should induce a low overhead, have minimal memory and computation requirements, etc. 1.3 Contributions The main contribution of this work are: Design, specification and performance evaluation of an energy efficient routing protocol based on OLSR. The proposed protocol, called EOLSR, computes the path built from intermediate nodes with sufficient residual energy that minimizes the energy dissipated by an end-to-end transmission. The second originality of this protocol resides in the cross layering with both the application and the MAC layer. The cross layering with application allows us to define two modes depending on the application requirements: Generic mode applies to applications where the communications characteristics are not known in advance. Strategic mode applies to applications where the potential destinations exist in a limited number and are known in advance. This is the case for instance in data gathering applications. Design, specification and performance evaluation of node activity scheduling. The proposed solution, named SERENA, is based on node coloring to assign time slot to nodes. 3 The innovation resides in taking into account wireless environment constraints like unidirectional links, immediate acknowledgement of unicast transmissions, etc. The second innovation consists in adapting to application requirements by selecting the most appropriate mode: Generic mode is used where there is no specific knowledge on the application and topology. Specific mode is used in applications organized in a tree, like data gathering applications. Benefits brought by the cross layering. In this work, we have advertised a cross layering approach to optimize communication protocols taking into account the real environment in which the network operates. We have shown that high benefits can be obtained at a small cost. For instance, we have specified the interactions between: the routing protocol and both the MAC and application layers to optimize the stability of routes as well as reduce the overhead. node activity scheduling and both the MAC and application layers to detect color conflicts and to better adapt to application requirements. Specification and performance evaluation of optimized broadcast. We have shown that the solution proposed, based on multipoint relay, improves network lifetime. Integration in the network layer of the OCARI project. We have contributed to the specification of the energy efficient network layer of the OCARI project. We have specified network messages format, network primitives and processing done by the network layer. This network layer integrates EOLSR, SERENA, and optimized broadcasts. It takes advantages of cross layering with the MAC and application layers. 1.4 Thesis organization This dissertation is structured as follows: Chapter 1, this chapter, defines the context and states the problem that will be solved in this work. It points out the main contributions of this thesis and presents the organization of this dissertation. Chapter 2 deals with energy efficiency. It first defines the main concepts such as network lifetime and node energy consumption model. It then provides a classification of energy efficient techniques and gives for each of them a brief state of the art. Simulation results show the distribution of node energy consumption in wireless sensor networks. Chapter 3 focuses on energy efficient routing. First, we recall some work related to multipath routing and minimum energy routing. We show that OLSR does not maximize the network lifetime and present EOLSR, our energy efficient extension of OLSR. We define the four main modules of EOLSR: energy consumption model, energy efficient selection of 4 multipoint relays, routing algorithm and optimized broadcasts. Performance evaluation results allow us to validate the design choices made for each module. A cross layering optimization with the application layer leads us to distinguish between a generic mode adapted to applications where the communications are not known in advance and a strategic mode where all the destinations are known in advance. The strategic mode is well adapted to data gathering applications, for instance. Chapter 4 is centered on node activity scheduling. We are interested more particularly in graph coloring. We first compare the respective merits of vertex and edge colorings and present the benefits of each coloring in wireless sensor networks. We precisely define the problem of node coloring in these networks highlighting the different constraints. SERENA s two-hop coloring algorithms is described with all exchanged messages and the information maintained by each node. The coloring algorithm is then followed by a slot assignment algorithm. Performance evaluation of SERENA is done, comparing the results of SERENA with other coloring algorithm and other variations of TDMA. SERENA is then extended to allow immediate acknowledgement of unicast transmissions and to cope with unidirectional links that exist in a real environment. Color conflicts cannot be avoided in an environment prone to topology changes due to unidirectional links, node mobility and late node arrivals. Such conflicts, detected by a cross layering approach with the MAC layer, are solved by SERENA. Chapter 5 shows how to optimize node activity scheduling for data gathering applications where the delay needed to detect data from all sensor nodes must be minimized. Simulation results allow us to compare SERENA with classical TDMA and TDMA-ASAP a dynamic variant of TDMA. Network calculus is used t
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks