Wireless sensor networks are the collection of wireless nodes that are deployed to monitor certain phenomena of interest. Once the node takes measurements it transmits to a base station over a wireless channel. The base station collects data from all the nodes and do further analysis. To save energy, it is often useful to build clusters, and the head of each cluster communicates with the base station.

Initially, we do the simulation analysis of the Zigbee networks where few nodes are more powerful than the other nodes. The results show that in the mobile heterogeneous sensor networks, due to phenomenon orphaning and high cost of route discovery and maintenance, the performance of the network degrades with respect to the homogeneous network.

The core of this thesis is to empirically analyze the sensor network. Due to its resource constraints, low power wireless sensor networks face several technical challenges.

Many protocols work well on simulators but do not act as we expect in the actual deployments. For example, sensors physically placed at the top of the heap experience Free Space propagation model, while the sensors which are at the bottom of the heap have sharp fading channel characteristics.

In this thesis, we show that impact of asymmetric links in the wireless sensor network topology and that link quality between sensors varies consistently. We propose two ways to improve the performance of Link Quality Indicator (LQI) based algorithms in the real asymmetric link sensor networks. In the first way, network has no choice but to have some sensors which can transmit over the larger distance and become cluster heads. The number of cluster heads can be given by Matérn Hard-Core process. In the second solution, ii we propose HybridLQI which improves the performance of LQI based algorithm without adding any overhead on the network.

Later, we apply theoretical clustering approaches in sensor network to real world.

We deploy Matérn Hard Core Process and Max-Min cluster Formation heuristic on real Tmote nodes in sparse as well as highly dense networks. Empirical results show clustering process based on Matérn Hard Core Process outperforms Max-Min Cluster formation in terms of the memory requirement, ease of implementation and number of messages needed for clustering.

Finally, using Absorbing Markov chain and measurements we study the performance of load balancing techniques in real sensor networks.

iii Résumé Empirical Analysis of Wireless Sensor Networks par Ashish Gupta

Les réseaux de capteurs sans fil sont une collection de noeuds non connectés qui sont installés pour la détection de certains phénomènes intéressants. Après avoir pris des mesures un capteur sans fil retransmet ces mesures la station de base. La station de base collecte les données de tous les capteurs et les analyse. Pour économiser l'énergie il est souvent utilise de grouper les capteurs en clusters, chaque cluster ayant une tête de cluster qui communique avec la station de base.

Au début, on commence par analyser la simulation des réseaux Zigbee où il y a quelques noeuds qui transmettent avec différentes puissances. Les résultats montrent que dans les réseaux de capteurs mobiles et hétérogènes et cause du phénomène d'isolation des noeuds et du coût très élevé du routage et la maintenance, les performances sont moins bonnes que celles des réseaux homogènes.

Le but principal de cette thèse est de faire une analyse empirique des réseaux de capteurs. A cause de leurs ressources limitées les réseaux de capteurs doivent faire face plusieurs défis techniques. Beaucoup de protocoles fonctionnent très bien dans les simulateurs mais pas aussi bien en implémentation réelle. Par exemple, les capteurs déposés sur un objet élevé subissent moins d'atténuation que les autres capteurs placés sur le sol.

Dans cette thèse, on montre qu'il y a un impact des liens asymétriques sur la topologie des réseaux de capteurs sans fil et que la qualité des liens (LQI) varie en permanence. On propose deux méthodes pour améliorer les performances des algorithmes basés sur la qualité des liens des réseaux de capteurs avec des liens asymétriques. Dans la première méthode, le réseau n'a pas d'autre choix que d'avoir des noeuds qui transmettent des grandes distances et deviennent des clusters Head. Le nombre de clusters Head peut être donné par Matérn Hard-core process. Dans la seconde méthode, on propose HybridLQI qui améliore les algorithmes basés sur LQI sans ajouter des entêtes au réseau.

Ensuite, on applique les approches de clustérisassions théoriques sur le réseau de capteurs réel. On applique Matérn Hard Core process et Max-Min heuristique de formation iv des clusters sur des noeuds "Tmote " dans des réseaux denses et des réseaux de faible densité. Les résultats empiriques ont montré la supériorité de Matérn sur Max-Min dans les besoins d'espace mémoire, la simplicité de l'implémentation et le nombre de messages de signalisation.

Enfin, en utilisant les chaînes de Markov absorbantes et des mesures, on étudie les performances des techniques de la distribution de charge dans des réseaux de capteurs réels.

v

In loving memory of my grand parents vi

The grand aim of all science is to cover the greatest number of empirical facts by logical deduction from the smallest number of hypotheses or axioms -Albert Enstien vii Acknowledgments Great discoveries and improvements invariably involve the cooperation of many minds. I may be given credit for having blazed the trail, but when I look at the subsequent developments I feel the credit is due to others rather than to myself.

Alexander Graham Bell

First and foremost I would like to thank my advisor Prof. Monique Becker. It has been an honor to be her Ph.D. student. Prof. Monique Becker's dedication, advise, perseverance and guidance has made this thesis possible. She has been an excellent motivator.

Prof. Michel Marot my "encadrant" has been very supportive. Michel taught me the intricacies of what it means to be a researcher. His patience with me has helped me to improve my French language skills by several notches. The level of our friendliness can be gauged from the fact that sometimes our discussion took turn to BCE period. These discussions helped me to think out of the box. His dedication and attention to detail has resulted in profound improvements.

I am grateful to Prof. André Luc Beylot (IRIT, Toulouse) for accepting to be a reporter for this thesis. Various interactions with him and Dr. Riadh Dhaou (IRIT, Toulouse) during our project meetings have proved invaluable. I would like to express my gratitude to Dr. Frederica Darema (Scientific Director, Air force office of Scientific Research,USA) and Prof. Guy Pujolle (Université Paris VI) for being members of the jury. I would also like to express my gratitude to Prof. Paul J.

Kuehn (University of Stuttgart, Germany) for accepting to be a reporter for this thesis. I would also like to thank Dr. Didier Perino. On several occasions he arranged sensors for me. Let me take this opportunity to thank Fréderic as well for his timely help while installing TinyOS and other troubleshooting. I would also like to thank Prof. Harve Debar (Head of the Departmetment-RST) for his constant encouragement espcially at the final phase of this thesis. I would also like to thank Prof. Maryline Laurent-Maknavicius for insightful interactions. viii Chérif Diallo has been a true friend. On numerous occasions he has helped me.

Professionally, he aided me in conducting several experiments with sensors which made this thesis possible. I would also like to thank Prof. Pierre Becker. He and Prof. Monique Becker invited me to their house on numerous occasions to take my mind off the inevitable frustrations that I encountered during my thesis.

Rahim Kacimi (IRIT, Toulouse) needs a special mention for his patience and dedication in dealing with me. Not only we worked together on the empirical study on Link quality but he is a great host as well. When I went to Toulouse in 2008, he had done all the necessary arrangements beforehand. Not only he managed to get me a decent place but also made himself available 24x7 for the whole week.

I would also like to thank Dr. Alexandre Delye De Clauzade De Mazieux. He mentored me during the initial period of this thesis. His efforts made my first publication possible. I would also like to thank Dr. Vincent Gauthier with whom discussions during the coffee breaks have been quiet insightful.

I would also like to thank Mohit Sharma (summer intern at TMSP from IIT-Kanpur) for his help to program and fine tune the Hybrid MultihopLQI algorithm. For the work on Max-Min and Matérn Hardcore Point process, I am particularly thankful to Harmeet Singh (summer intern at TMSP from IIT-Kanpur) for his code and help. I would also like to thank Dr. Manoj Panda for his insights on CSMA behaviour and Matérn process. I would also like to thank Sanjay Kanade for his emotional support during this whole time. I can never forget the numerous trips we took together to Carrefour. I would also like to thank Dr. Sandhodche Balakrishnan and Dr. Mahendiran Prathaban for their help to complete the paper work with UPMC especially at the time of registration.

I would also like to thank Nicholas Charbel. Our discussions over the lunch time have been very useful.

I would also like to thank Er. Deepak Makhija. We are friends since our Engineering days. He has been a tremendous help to me whenever I got stuck in JAVA. I would also like to thank Chakib Bekara and Wassim Drira with whom I worked on the CAPTEURS Project.

I would like to thank Françoise Abad for providing seamless support to complete ix all administrative work. She is the one who took care of all necessary administrative work from buying a simple USB hub to all conference missions and other reimbursements. I take this opportunity to also thank Céline Bourdais to provide invaluable support to process CNRS-SAMOVAR grants.

Finally, I owe whatever I am to my parents Er. Balbir Singh Gupta In both cases nodes transmit at -20 dbm . . . . . . . 6.2 Average number of hopcounts of the nodes from the BS when BS transmits at 0 dbm and -20 dbm. In both the cases, 6 other nodes transmit at -20 dbm 6.3 Average number of hops from the Nodes to the BS, when nodes are deployed in 3x6 grid topology. In all the cases, 17 nodes transmit at -20 dbm. . . . . 6. 4

Introduction

With the rapid improvement in wireless network technologies and chip designing ( [START_REF] Cc | Single Chip Very Low Power RF Transceiver[END_REF], [1], [2], [3] and [4]) more and more opportunities are opening up to deploy large scale sensor networks. Spread across a huge geographical area, a wireless sensor network consists of hundreds or thousands of sensors called nodes that assemble and configure themselves.

The nodes then sense environmental changes and report them to other nodes over defined network architectures. Usage scenarios for these devices range from real-time tracking, to monitoring of environmental conditions, to ubiquitous computing environments.

In most of the settings, the network operates for long periods of time and the nodes are wireless, so the available energy resources limit their overall operation. To minimize energy consumption, most of the device's components, including the radio, are likely being turned off most of the time ( [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF][START_REF] Ye | An energy-efficient mac protocol for wireless sensor networks[END_REF][START_REF]IEEE. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF][START_REF]IEEE. Part 15.1: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Wireless Personal Area Networks (WPANs)[END_REF][START_REF]Zigbee Specification V1[END_REF][START_REF] Venkatesh Rajendran | Energy-efficient collision-free medium access control for wireless sensor networks[END_REF][START_REF] Van Dam | An adaptive energy-efficient mac protocol for wireless sensor networks[END_REF]). One of the most important aspects of a wireless sensor network is the communication between the nodes. Their deployment generally means that there will be a high degree of interaction between nodes, both positive and negative ( [START_REF] De | An efficient data transport protocol for event-driven field-estimation on sensor networks[END_REF]). The character of the communication used in a wireless sensor network has a huge impact on the usability of a sensor network( [START_REF] Stann | Rmst: reliable data transport in sensor networks[END_REF]). For example, the lifetime of a sensor network in which most nodes are battery-powered or non-rechargeable is essentially influenced by the used communication patterns ( [START_REF] Singh | Power-aware routing in mobile ad hoc networks[END_REF]). Each of these factors further complicates the networking protocols. Some of the applications for sensor networks are:

• Home Automation.

• Industrial Automation. 1 2

• Disaster Assistance.

• Remote Metering.

• Automotive Networks.

• Logistics.

• Medicine and Health Care Some of the design issues which should be taken into account while implementing the sensor networks are:

• Enable low-cost, low-power embedded networking.

-"Low Cost" basically means low memory footprint.

-"Low Power" means low radio power as well as long battery life.

• Support a wide variety of technical requirement and design tradeoffs.

-Battery life vs. throughput/latency.

-Latency vs. spatial coverage.

-Code size vs. "Ease of use" and "Feature Richness". According to [START_REF] Perkins | Ad Hoc network[END_REF], problem of routing is essentially for the distributed version of shortest path problem. Each node maintains a list of preferred next hop nodes and each data packet contains its sender and its destination address. When an intermediate node receives a packet it parses and finds its destination and accordingly it forwards it to its next hop neighbour. The process continues till the packet is finally received at its destination (as shown below).

-

---------------------------------------------------------------------------------------- event received() { if(packet_destination==my_id) {Process the packet;} else { event (send); } } event send () { transmit(get_next_hop_neighbour()); } -----------------------------------------------------------------------------------------
The next-hop routing methods can be categorized into: Link-state and distancevector.

Link-State

In the link-state approach, each node maintains cost for each link. To have a consistent state of the network, each node periodically broadcasts the link state in form of beacon messages. So, when a node receives beacons or other messages it constructs and maintains its neighbour table.

PROJECT-CAPTEURS

Distance-Vector A distance-vector routing protocol requires a router to inform its neighbors of topology changes periodically and, in some cases, when a change is detected in the topology of a network. Compared to link-state protocols, which require a router to inform all the nodes in a network of topology changes, distance-vector routing protocols have less computational complexity and message overhead.

Project-CAPTEURS

CAPTEURS's goal is to propose a system for the whole supply chain, from the warehouses to the retailers. Goods are stored in a pallet and each pallet is equipped with a temperature sensor. A truck can't transport more than 33 pallets (1m x 1m x 1m) in a single trip but a warehouse is more likely to store hundred of thousands of pallets. For scalability reasons, it is essential to have clustering techniques combined with the energy

PROBLEM DEFINITION AND APPROACHES IN SENSOR NETWORK 5

efficient routing mechanism.

In the last decade, lots of efforts have been focused on semiconductor and networking technologies. Therefore, several existing solutions are used to build architectures. However, a lot of technical challenges remain. Some doors remain to be opened in the field of communication networks. For instance, quality of service must be ensured while taking into account large network limitations and low energy levels of sensors at the same time.

The CAPTEURS project has been divided into two parallel tasks. In the first task, prospec- In the second task, the effort has focused on designing a concrete solution for only the transportation phase of the supply chain. the general routing and limitations of simulation studies. More importantly, it discusses several experimental studies in the field of sensor networks.

In this thesis, we will be using TinyOS [START_REF] Hill | System architecture directions for networked sensors[END_REF] as the operating system for our sensors.

"TinyOS [START_REF] Hill | System architecture directions for networked sensors[END_REF] is an open-source operating system designed for wireless embedded sensor few nodes are capable of routing the data. In this chapter hierarchical cluster routing is implemented using the LEACH protocol and the performance of heterogeneous network is compared with a homogeneous network. The results show that in the mobile heterogeneous sensor network, due to the phenomenon of orphaning and high cost of route discovery and maintenance, the performance of the network degrades with respect to the homogeneous network. The performance of the system worsens as the number of hops between the node and the base station increases. These results helped us to select the real sensor nodes (i.e., Fully Function Device) which we have used in this thesis.

Chapter 4 discusses the real time deployment issues in the sensor networks using the concept of Link Quality Indicator (LQI) as the criteria. While most of the earlier peer studies are done on the test-bed, our studies are more comprehensive as we deploy sensors in straight line, grid topology, in isolated places as well as in the public area. Different nodes transmit at different power levels making the deployment more realistic. Further, we deploy sensors in the outdoor as well as indoors. This study takes three factors in account:-

• Sensors can have low quality of radio antenna.

• Deployment in an area where steady environment can't be possible.

• Change in the orientation of deployment of sensors. Finally, can we apply the load balancing techniques in a generic manner? The chapter investigates some of these issues. We apply link quality based algorithms and compare their performances with the round robin algorithm. Finally, chapter 9 concludes the thesis.

Nel mezzo del cammin di nostra vita mi ritrovai per una selva oscura, ché la diritta via era smarrita.

In the middle of the road of my life, I awoke in the dark wood, where the true way was wholly lost.

Dante's La Commedia Divina

Chapter 2

Background "If we examine our thoughts, we shall find them always occupied with the past and the future -Blaise Pascal "

The advent of small, efficient, integrated sensors can allow us to implement cost effective solutions. On the one hand these solutions can range from our daily lives to the complex problems of the industrial monitoring and automation. So, now question arises "how far can we go with the present technologies?"

It has been more than a decade when research community first started looking for these answers and in this direction huge theoretical work has been done. However, due to hardware and cost factors, there have been limited efforts in the experimental verification of the ad hoc or sensors algorithm.

This chapter briefly discusses why experimental studies are important and does the survey of important work in this direction. Also, it discusses various routing and MAC schemes.

Wireless Sensor Networks

Developments in the wireless technologies are opening up new application avenues in the automation of traditionally labour intensive work. With the infinite number of small and cheap devices available today, the question remains, how should they communicate in an effective manner? One of the major constraints of these small devices is their limited battery capacity. In fact, the degree of success of any kind of automation lies on the level of human interference; the lower the human interference is, the better the system is, while providing seamless services. Therefore, not only it is important that these devices should communicate in an efficient manner but also independent of any fixed infrastructure.

Nevertheless 5. Birth process: When a node enters the network, if it is alone in the network it initiates the network else joins an existing network.

6. Death Process: When a nodes exits the network or runs out of battery.

Furthermore, the sensor network may undergo dynamic and frequent topology changes. All these factors are unique to the sensor networks.

How to study sensor networks

So, now the question arises "how to study the sensor networks"?

Graph Theory: Answer can be the graph theory where each edge be treated as the radio channel link. However, these edges fail to consider the dynamic nature of links. Sensor networks are envisioned to have small size. They should also have minimal price. Because of these attributes several compromises are done. One of the biggest fallout of these is the quality of the radio antenna. Plus due to the dynamic physical media, the use of graph theory to model the wireless links cannot be an obvious choice.

Simulation: Another way is to simulate. Simulators such as MATLAB [START_REF]Wireless medium access control (mac) and physical layer (phy) specifications for low rate wireless personal area networks (lr-wpans)[END_REF], NS-2, Emstar [START_REF] Girod | Emstar: a software environment for developing and deploying wireless sensor networks[END_REF] don't support sensor network as such. TOSSIM [START_REF] Levis | Tossim: accurate and scalable simulation of entire tinyos applications[END_REF] does not support MAC layer in the simulation. Further, their support for asymmetric link is also limited. So, without the MAC layers results usually do not match the performance of the network in real time.

Many protocols work well on simulators but do not act as we expect in the actual deployments. Therefore, this decade has witnessed research community focusing more and more on the real time application and deployment of various testbeds. The testbeds initially set up to verify the algorithms have opened new fronts in the area of wireless sensor networks.

These testbeds have shown several deployment limitations which were very difficult to detect in the simulators. One wireless sensor network deployment failed due to inconsistency between routing and the MAC layer [START_REF] Langendoen | Murphy loves potatoes: experiences from a pilot sensor network deployment in precision agriculture[END_REF]. [START_REF] David Kotz | Experimental evaluation of wireless simulation assumptions[END_REF] indicates the wide difference between the simulations and the real world issues. Next section discusses some of the major experimental work done in the last decade or so. [START_REF] Hill | Mica: A wirless platform for deeply embedded networks[END_REF] nodes and confirmed the existence of the radio irregularity.

Experimental Studies

They evaluated that the radio irregularity has greater impact on the routing layer than the MAC layer.

Link Asymmetries due to Nodes -802.11

Ganesan et al. [START_REF] Ganesan | Complex behavior at scale: An experimental study of low-power wireless sensor networks[END_REF] using rene motes showed that even simple algorithms such as flooding had significant complexity at large scales. They observed that many node pairs had asymmetric packet reception rates, which they postulate were due to receive sensitivity differences among the nodes. Cerpa et al. [START_REF] Cerpa | Scale: A tool for simple connectivity assessment in lossy environments[END_REF] swapped node pair and supported this asymmetric node pairs finding that the asymmetries were a product of the nodes and not the environment.

Gray Area -802.11

Traditionally like any other networking protocols wireless sensor network protocols have often been evaluated via the simulators. However, due to the constraints such as low power battery and the low quality of the radio antenna of the sensor hardware, some of the assumptions in the simulators are not valid in the real time.

In [START_REF] Zhao | Understanding packet delivery performance in dense wireless sensor networks[END_REF] For the rest of the thesis, the use of word "mote/node" mean a wireless sensor.

Link Quality Indicator

The link quality indication (LQI) metric characterizes the strength and/or quality of a received packet. LQI measures the incoming modulation of each successfully received packet. The CC2420 radio as per IEEE 802.15.4, samples the first eight chips of a packet (8 chips/bit), measures the error in the modulation, and calculates a LQI value. In other words, LQI can be seen as a physical measure of the error in the incoming modulation of successfully received packet (packet that passes the CRC check).

Basically, the CC2420 chip correlation indicator provides fine-grained information on the part of the SINR curve where the slope is significant. This is why the values show much larger temporal variation: a tiny shift in SINR causes a change in LQI. : If the received modulation is FSK or GFSK, the receiver will measure the frequency of each "bit" and compare it with the expected frequency based on the channel frequency and the deviation and the measured frequency offset. If other modulations are used, the error of the modulated parameter (frequency for FSK/GFSK, phase for MSK, amplitude for ASK etc) will be measured against the expected ideal value.

Deployment Experiences

In the real time deployment of the sensors, now, it has become a well established fact that radio links are unreliable [START_REF] De Couto | A high throughput path metric for multi-hop wireless routing[END_REF], [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF], [START_REF] Zuniga | Analyzing the transitional region in low power wireless links[END_REF], [START_REF] Becker | Experimental study: Link quality and deployment issues in wireless sensor networks[END_REF]. In [START_REF] Gungor | Resource-aware and link quality based routing metric for wireless sensor and actor networks[END_REF] One of the classical ways to calculate the route cost is based on the minimumnumber-of-hops routing based technique. However, one of the major problems is the unreliability of the radio links. If the link quality of the channel is not so good, nodes have to indulge in retransmission again and again, having detrimental effect on the life time of the network.

Polastre et al. [START_REF] Polastre | Telos: enabling ultra-low power wireless research[END_REF] in their preliminary evaluation for Telos motes suggested that the average LQI is a better indicator of packet reception rate (PRR).

Holland et al. [START_REF] Holland | Experimental investigation of radio performance in wireless sensor networks[END_REF] conducted experiments using 20 motes in outdoor and indoor and have observed that LQI very closely related to packet yield. Further height of sensors played a significant role in performance. This fact is also noted in [START_REF] Becker | Experimental study: Link quality and deployment issues in wireless sensor networks[END_REF]. Other studies that has been done on the 802.11 are [START_REF] Aguayo | Linklevel measurements from an 802.11b mesh network[END_REF], [START_REF] Raman | On the feasibility of the link abstraction in wireless mesh networks[END_REF] and [START_REF] Reis | Measurement-based models of delivery and interference in static wireless networks[END_REF]. • Grey areas in the network with poor packet delivery performance.

• Links with highest reception rate had signal strength value higher than a given threshold value, but not the vice-versa. • The energy detect method of carrier sense may be forgoing some good transmission opportunities.

• Under extremely high loads, the improvement in link quality might not be worth the time it takes to carrier sense. • Grey areas in the network with poor packet delivery performance.

• Links with highest reception rate had signal strength value higher than a given threshold value, but not the vice-versa.

• Tried to compare the behavior of Micaz and Telos platform, but remained noncommittal on which platform is better over whom. Also, by the time, may be some sensors run out of battery or their transmission power have decreased.

Routing

Initially ad-hoc routing algorithms were designed for mobile networks but some of the algorithms such as [START_REF] Bicket | Architecture and evaluation of an unplanned 802.11b mesh network[END_REF][START_REF] De Couto | A high throughput path metric for multi-hop wireless routing[END_REF] are also applied to fixed network. The Distributed Source Routing protocol (DSR) [START_REF] David | Dynamic source routing in ad hoc wireless networks[END_REF] and the Destination Sequenced Distance Vector protocol (DSDV) [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers[END_REF] have been one of the earliest proposed routing algorithms. The DSR is an on-demand routing protocol. In DSR, a node wishing to communicate with another node broadcasts a route discovery packet. Intermediate nodes that receive route discovery packets add their own address to the packets and re-broadcast the request. Hence, the request propagates over the network. Route maintenance in DSR happens either through the use of link-layer acknowledgements provided by the MAC layer or through the use of passive acknowledgements. DSDV on the other hand proactively builds routes from any node to any node, which can lead to increased control overhead, The beacon Based routing algorithms such as [5] are inspired from both the DSR and DSDV. The Base Station initiates the route request and the tree/mesh is created for whole network.

Routing Metrics

The routing metric is a critical part of a routing protocol. It is the factor applied by the routing protocol to determine the best path. The higher is the ability of the routing metric to correctly capture the underlying topology dynamics, the better is the performance of the routing algorithm.

Traditionally, the Minimum Hop Count (or shortest path) metric was used in several Internet/ wired routing protocols. In this metric, the path that minimizes the number of hops is preferred. It was originally used in DSR and DSDV for routing. However, it was found to be inadequate for wireless adhoc networks. In [START_REF] Douglas | Performance of multihop wireless networks: shortest path is not enough[END_REF], Cuto et al. experimentally present that many of the multiple minimum hop-count paths often have poor throughput.

Minimum-hop-count routing often chooses routes that have significantly less capacity than the best paths that exist in the network The failure to capture the effects of lossy links and asymmetric links are the biggest limitations [START_REF] Aguayo | Linklevel measurements from an 802.11b mesh network[END_REF][START_REF] De Couto | A high throughput path metric for multi-hop wireless routing[END_REF].

Cerpa et al. [START_REF] Cerpa | Statistical model of lossy links in wireless sensor networks[END_REF], Zhao et al. [START_REF] Zhao | Understanding packet delivery performance in dense wireless sensor networks[END_REF] and Woo et al. [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF] highlighted this problem for the wireless sensor networks. If link quality/losses is not taken into account, the metric can select poor quality paths, as they exhibited a smaller hop count than much higher quality paths. A poor quality route can have high losses. Asymmetric links, i.e., links whose channel quality in one direction differs substantially from the quality in the other direction, are also ignored by the minimum hop count metric. These links can be quite frequent both in wireless networks in general and in WSNs in particular, especially mote-based WSNs.

Next chapters will highlight the problems associated with the asymmetrical links.

The Estimated Transmission Count(ETX) [START_REF] De Couto | A high throughput path metric for multi-hop wireless routing[END_REF] metric finds paths that maximize the data throughput. These paths require the minimum amount of transmissions to successfully send a packet from the source to the destination. The requirement of successful delivery means that each packet being acknowledged. Therefore, in an ideal case, the number of packet transmissions required is 2; one for the actual packet and one for the acknowledgement. If the links are not perfect, then the minimum number of transmissions per packet are greater, as packets (and ACKs) may be retransmitted. By using an indicator for the number of transmissions per link and by including reverse-link information through the requirement for a successful ACK reception, ETX incorporates both the lossy link and the asymmetric link issues into the routing metric itself. The ETX metrics can be given as:

ET X = 1/d f * d r
The routing algorithm selects the path with the least sum of ETX values over its constituent links. Each node broadcasts a probe packet every second to measure d f (forward delivery ratio) and d r (reverse delivery ratio).

MAC PROTOCOLS 20

ETX assumes losses over time are independent. ETX calculates the average number of transmissions needed for a packet as the inverse of reception ratios calculated over an interval (usually from control beacons). Cerpa et al. [START_REF] Cerpa | Temporal properties of low power wireless links: modeling and implications on multi-hop routing[END_REF] showed that PRR rates can change significantly over time. So, the long-term PRR calculation can lead to very inaccurate results. Cerpa et al. [START_REF] Cerpa | Temporal properties of low power wireless links: modeling and implications on multi-hop routing[END_REF] method of sending control packets every few milliseconds have very high energy overhead. of its schedule), if there is no packet to be received, however, channel throughput is lesser than the SMAC. Traffic Adative Medium Access (TRAMA) protocol, assumes that time is slotted and uses a distributed election scheme based on information about the traffic at each node to determine which node can transmit at a particular time slot. This scheme relies on heavily on neighbours and considers that during the random access period all nodes must be in receiving or transmitting state. This increases the duty cycle of the nodes. Z-MAC [START_REF] Rhee | Z-mac: a hybrid mac for wireless sensor networks[END_REF] is a combination of TDMA and CSMA . The authors showed that Z-MAC achieves high channel utilization and low latency than pure TDMA and CSMA. IEEE 802.15.4 defines a MAC protocol for low-rate Wireless Sensor Networks. When operating in TDMA mode it provides guaranteed channel access via a co-ordinator (using beacons). In ad hoc mode, channel uses CSMA/CA for non-guaranteed access.

MAC protocols

Hardware based approaches are also examined for the MAC synchronization. In [START_REF] Alanson | Design of a passively-powered, programmable sensing platform for uhf rfid systems[END_REF] authors have presented a design for programmable RFID sensor. In [START_REF] Daniel | Wirelessly-charged uhf tags for sensor data collection[END_REF]authors discussed Passive Data Logger (PDL), which charges itself (capacitors) using the RFID Reader and therefore, does not need any battery support to continue its operation. However, this architecture is not autonomous as well as feasible without any Base Station (in this case RFID Reader). In [START_REF] Ruzzelli | On the rfid wake-up impulse for multi-hop sensor networks[END_REF] a RFID wake up mechanism for sensor network is proposed and in [START_REF] Jurdak | Multi-hop rfid wakeup radio: Design, evaluation and energy tradeoffs[END_REF]authors have evaluated the performance of multi-hop RFID sensor networks. In [START_REF] Gu | Radio-triggered wake-up capability for sensor networks[END_REF] authors have examined various RFID circuits for wake-up mechanism.

For our experimental purpose, we will use simple CSMA/CA MAC supported by

Tmote sky sensor and operated via TinyOS-1.x. For ease of programming, we will not • Data rates of 250 kbps, 20 kbps and 40kpbs.

• Star, mesh, tree topology.

• Support for low latency devices.

• CSMA-CA channel access.

• 16 channels in the 2.4GHz ISM band, 10 channels in the 915MHz ISM band and one channel in the European 868MHz band.

• Low power consumption.

IEEE 802.15.4 uses orthogonal quadrature phase shift keying (OQPSK) and direct sequence spread spectrum (DSSS). Subsequently, several Zigbee compliant solutions are currently available. The Zigbee standardizes the platform for the research community. They informed us that our messages, reset their's motes. Later, it was discovered that our initialization beacons were their reset commands. This means that MAC protocols cannot assume that they are the sole users of the channel. Therefore, analytical results in ideal system may not be applicable in the real-world systems.

Research community has put a lot of effort to study the effect of overlapping technologies, e.g., [START_REF] Howitt | Ieee 802.15.4 low rate wireless personal area network coexistence issues[END_REF], [START_REF] Petrova | Interference measurements on performance degradation between colocated ieee 802.11g/n and ieee 802.15.4 networks[END_REF], [START_REF] Young Shin | Lecture notes in computer science: Packet error rate analysis of ieee 802.15.4 under ieee 802.11b interference[END_REF] and [START_REF] Shuaib | Performance evaluation of ieee 802.15.4: Experimental and simulation results[END_REF]. [START_REF] Young Shin | Lecture notes in computer science: Packet error rate analysis of ieee 802.15.4 under ieee 802.11b interference[END_REF] While performing experiments for this thesis, we also do not observe any affect of the WiFi. We do observe interferences from the other Zigbee networks. Once our colleagues reported to us that their network was re-initialized when we started our network.

PROTOCOLS IN TINYOS

DSSS Transmission

As per the Jennic [START_REF] Jennic | [END_REF]'s technical report, IEEE 802.15.4 is designed to promote coexistence with other technologies. Therefore, the Direct Sequence Spread Spectrum (DSSS) transmit scheme is used for the communication. The basic idea is to use more bandwidth than is strictly required, thus spreading the signal over a wider frequency band. This is achieved by mapping the incoming bit-pattern into a higher data-rate bit sequence using a chipping code (effectively adding redundancy). Since the signal is spread over a larger bandwidth, narrow-band interferers block a smaller overall percentage of the signal, allowing the receiver to recover the signal.

Protocols in TinyOS

Collection Tree Protocol and MultihopLQI are the two collection protocols now available in TinyOS2.x . DRIP and DIP are the two dissemination protocols and finally the Deluge for over the air programming.

MultihopLQI [5]

• Mostly tested and used on platforms with CC2420.

• Small footprint.

• Assumes links are symmetric.

Collection Tree Protocol [42]

• System Independent.

• Not thoroughly tested.

• Code foot print can be an issue.

Drip [6]

• Fast and efficient for small number of items.

• Trickle timers for advertisements.

• Suppression.

MULTIHOPLQI

DIP [7]

• Efficiently Disseminates large number of items (can not fit in one packet).

• Use hashes and version vectors to detect and identify updates to the values.

Deluge, [8]

• Over-the-air programming.

• Disseminates code.

• Programs the nodes.

• If code size is large Deluge can not work. Here is the pseudo code for the data message used by our application:-

MultihopLQI

------------------------------------------------------------------------- uint32_t
. -------------------------------------------------------------------------
The Beacon Messages in MultihopLQI are different than the beacon messages exchanged at the MAC layer. In case of MAC layer, beacon messages are used for channel access mechanism. In case of MultihopLQI algorithm, beacon messages are sent by the routing layer. Each node periodically sends its beacon messages (Table 2.5). Each beacon message consists of its Parent id, cost of reaching the Base station and the hopcount of the node from the BS. The information stored in each beacon is the starting point of the path (the node itself), the eventual destination (parent). Therefore, for the BS, the LQI based cost is zero and also the hopcount is zero.

The root node or destination begin network by sending the first beacon, and continue to do this periodically. If a node does not have a path to the base station, it do not send any beacons. The use of parent id is to avoid the loops in the path as well as to forward the node message. When a node receive a message, it calculates LQI of the received packet.

This received LQI is then used to estimate the cost of reaching the node. The higher the - When node receives a beacon, it checks whether beacon is from its original parent or from the other nodes. If the beacon is from the parent, it will simply update the parent cost. If the beacon is from other node, it will check the cost of routing the via new node.

------------------------------------------------------------------------ //
[i].hopcount = _bmsg->hopcount + 1; //Increase hopcount -------------------------------------------------------------------------
If the cost is less by 10% and no loop is created in the network, the new parent is selected and the neighbour table is updated. Pseudo neigbhour entry is given as:-

------------------------------------------------------------------------- typedef struct
-------------------------------------------------------------------------
Finally, the node sends its own beacon. Based on these beacons, once a parent is selected, the data is unicast to that node. The overall operation of MultihopLQI is summarized below:

• Initially, once the neighbour table is formed, the pointer to next hop neighbour is set to the node having minimum estimated cost ( Figure 2.9(a)).

• If new beacon arrives from the node e.g., A, lastheard entry will be updated to ZERO for the node A and other nodes it will be incremented ( Figure 2.9(b)).

• If the link layer acknowledgement fails, ack-fail field is set to 1 and next best available node is selected ( Figure 2.9(c)).

• If new beacon arrives from the node e.g., A, lastheard entry will be updated to ZERO for the node A and other nodes it will be incremented and ack-fail bit is reset to ZERO( Figure 2.9(d)).

• If the lastheard entry crosses a threshold value, the BEACON TIME OUT is triggered and node will be evicted from the neighbour table ( Figure 2.9(e)).. Interfaces Initially, application layer (Delta Application) is launched and it interacts with network layer via MultihopM (Figure2.10, M in MultihopM signifies that it is a module).

The multi-hop [9] implementation consists of two core modules, MultihopDataM and MultiHopLQIM. Figure 2.11 provides an overview of the configuration.

Interface Description:

The component configuration exports 6 interfaces. A '[ ]' after the interface name indicates the interface is parameterized.

• StdControl -The standard control interface.

• RouteControl -A special interface for controlling monitoring router operation. See the 'RouteControl.nc' interface description file for more information.

• Receive[] -In this implementation, the base station is the only implicit destination for packets. This interface exists only as a stub and is not implemented.

• Send[] -The port to use for locally originated packets.

• Intercept[] -This port is used when a packet is received that WILL be forwarded. It provides a means for an application to examine forwarded traffic and, depending on the value returned, suppress the forwarding operation.

• Snoop[] -The Snoop port uses the 'Intercept' interface definition, but with different semantics. It is signaled when a packet is received that WILL NOT be forwarded.

This interface is useful for passive monitoring of traffic for replication purposes.

Conclusion

Experimental studies are key to the degree of success of sensor networks. This chapter provided insight into the general routing and limitations of simulation studies.

Later, we discussed several experimental studies in the field of sensor networks. Then, we survey different routing metrics and finally, very briefly, we discussed some of the protocols available in TinyOS. So, the first task is to understand the implications of these types of devices in the network. This chapter studies the performance of various topologies in a mobile Zigbee sensor network comprising the FFD and RFD devices. We create several topologies having different number of FFD and RFD nodes. We also vary the radio range of the nodes. FFD nodes are assumed to have higher energy than the RFD nodes. To evaluate the performances of the different topologies, hierarchical cluster based routing is implemented.

We are among the first to study to performance of heterogeneous Zigbee based sensor network and we show that higher the number of RFD nodes in the network, the lower is the performance of the network. The two most common routing techniques employed in multi-hop environment are the Clustering and the Mesh. Figure 3.1 shows the various ZigBee network topology models.

The role of Zigbee Coordinator is similar to the classical Base Station. The ZigBee Routers are the FFD nodes and ZigBee End Devices are the RFD nodes.

Cluster Routing

Clustering is a model where a sensor network is subdivided into smaller units called clusters. A subset of nodes in the network is elected as the cluster heads (CHs) while the other nodes will join the clusters as members.

A clustered sensor network can be further subdivided into two types: homogeneous and heterogeneous network. In homogeneous networks all the sensor nodes are identical in terms of energy and hardware complexity. Static clustering (cluster heads (CH) once elected, serve for the entire lifetime of the network) in a homogeneous network can be implemented with fair degree of ease but has its own challenges. The cluster head nodes will be over-loaded with the long range transmissions to the remote base station, and the extra processing necessary for data aggregation and protocol co-ordination. As a result the cluster head nodes expire before other nodes and we can have a single point of failure.

Therefore, it is very important and interesting to examine the networks where some nodes are more powerful than other nodes. This kind of sensor networks are knows as heterogeneous sensor networks i.e. clustered sensor network with two types of nodes, type-1 and type-0, with type-1 having more energy than type-0. Under some conditions, a CH, a type-1 node spends energy much faster than the type-0 nodes within its cluster until the cluster enters a homogeneous state with all nodes having equal energy. This chapter analyzes the work in the similar domain and examines the applicability of those results for the CAPTEURS project.

In the ZigBee newtorks as only few nodes can participate in the routing, classical Mobile Ad hoc Network (MANET) algorithms [START_REF] Perkins | Ad hoc on demand distance vector routing[END_REF][START_REF] Park | Temporally-ordered routing algorithm (tora)version[END_REF][START_REF] Jacquet | Optimized link state routing protocol (olsr)[END_REF][START_REF] Belding-Royer Chakeres | Dynamic manet on-demand routing protocol (dymo)[END_REF][START_REF] David | Dynamic source routing in ad hoc wireless networks[END_REF]] cannot be applied.

Zigbee Tree Routing Zigbee tree algorithm is an example of cluster tree algorithm.

Depending upon the network parameters set at the application layer of Zigbee e.g. nwk-MaxDepth, nwkMaxChildren and nwkMaxRouter, a tree is constructed and only a FFD node can become the router or CH. In case of Zigbee tree routing, each CH has its own 16 bits address space and it divides the address space between its children. Each child is allocated the further 16 bit network address from that address space and therefore, instead of 64 bit MAC addresses this, network address can be used for routing purposes. This helps in auto routing as each CH is aware of its own address space and its parent address space.

Members will forward data packets to the CHs which, acting as relays, forward the packets to the sink or Base Station (BS). However, tree routing is not much feasible in mobile sensor networks, as CH itself might be changing its position, so its own address space and hence the address space of its children is not static at all.

Mesh Routing

Mesh networks are self-healing. Mesh network allows for continuous connections and reconfiguration over the broken paths by "hopping" from node to node until the final destination is reached. The Ad hoc On-Demand Distance Vector (AODV) [START_REF] Perkins | Ad hoc on demand distance vector routing[END_REF] routing protocol is a reactive protocol designed for use in ad hoc mobile networks. The Zigbee Mesh routing is similar to AODV. In [START_REF] Liang | Impact of node heterogeneity in zigbee mesh network routing[END_REF], authors have discussed the behavior of mesh routing in Zigbee networks. They used the set of FFD and RFD devices and studied the performance of the network by varying the number of RFD devices. They used the scenario where around 20% of the devices were mobile. They observed that increase in the node heterogeneity in the network i.e. increase in the number of RFD nodes, leads to the significant drop in routing performance of the whole system when compared with the simple AODV routing mechanism.

However, authors did not take into the account the energy implication for the RFD systems, because as the number of RFD nodes increases in the network; the total energy of the network should decrease. This chapter takes more critical view of the effect of topology on the overall performance of the system using energy. We show that how topology lays an intrinsic role in the network performance.

LEACH

Another, way of selecting the CH is LEACH algorithm. LEACH [START_REF] Chandrakasan | Energy-efficient communication protocol for wireless micro sensor networks[END_REF] is the selforganizing, dynamic algorithm to decide CHs in the network. LEACH has two phases; the Set up phase and the steady phase. In the set-up phase nodes organize themselves into the local clusters and the appointed CH communicates directly to the BS. This phenomenon of local clustering is repeated again after fixed interval of time and the new cluster formation takes place. Therefore, we used LEACH algorithm over the Zigbee Tree algorithm to select the CH and implement the routing scheme. In the LEACH, at the beginning of each interval a sensor node can become the CH on the function of some predefined probability. Since, CH requires quite a large amount of energy to communicate with Base Station, these CH rotation policy helps to distribute energy evenly in the whole network. Once a node declares itself the CH, the nearby nodes send the join request and once the node has joined the CH, it sends data to CH in the given time slot.

Related Work

In [START_REF] Vivek | Homogeneous vs heterogeneous clustered sensor networks: A comparative study[END_REF] the authors made the comparison between the homogeneous networks and heterogeneous networks in terms of overall network deployment cost. They studied multihop variant of LEACH (M-LEACH) for the intra-cluster routing and compared with the 3.2. ENVIRONMENT simple LEACH. However, M-LEACH is applicable to only the static networks not to the mobile ones and it considers that nodes inside the cluster will also participate in the intracluster routing. Similarly, most work in [START_REF] Soro | Prolonging the lifetime of wireless sensor networks via unequal clustering[END_REF] and [START_REF] Vivek | A minimum cost heterogeneous sensor network with a lifetime constraint[END_REF] relates to the static networks. Also, the main focus is to test the feasibility of the RFDs in the network.

Environment

This section details simulator.

NS2 and LEACH

The LEACH protocol is mainly used to choose the cluster heads. The implementation is referenced from [START_REF]Network simulator 2 leach implementation[END_REF]. However, the LEACH protocol has been implemented only for the homogeneous networks. Therefore, it is useful for the networks comprised of only FFD nodes as RFD are not capable of routing. The m-LEACH or multi hop LEACH is also ineffective as it needs the nodes capable of routing inside the cluster. In the simulation we assumed that either RFD is single hop away from the FFD or it is orphan as searching for the cluster head. Therefore, a few changes were made to implement the heterogeneous networks. The Probability of selection of CH is given as:

# Pi(t) = k / (N -k mod(r,N/k)) #
where k is the expected number of clusters per round # N is the total number of sensor nodes in the network # and r is the number of rounds that have already passed. # # If node has been cluster-head in this group of rounds, it will not # act as a cluster-head for this round.

Mobility Model

We use Random Waypoint model (RWP) for the simulations. It is introduced by the Monarch group [START_REF] Johnson | A performance comparison of multi-hop wireless ad hoc network routing protocols[END_REF]. RWP assumes that node mobility takes place in a flat rectangular area with no obstacles. Nodes movement is characterised by two parameters: a speed interval [Vmin; Vmax] and the pause time P. The movement patterns for the nodes follows the cyclic behaviour. Each node randomly selects a direction in which to travel, where a direction is measured in degrees. The node then randomly selects a speed and destination along the direction. Once it reaches the destination, it remains stationary for some predefined pause time or NS default time. At the end of the pause time, a new direction and speed is selected, and movement is resumed. Result is a uniform node distribution as well as causing continuous changes in the topology of the network. 1. Explicit definition of FFD and RFD nodes, with higher energy level for FFD nodes.

Network Model

2. For the ease of routing it is assumed that each and every node is location aware node.

3. Therefore, depending on the distance of the node from the Base Station and its radio range, a node can calculate its minimum depth.

4. NETWORK DEPTH of BS is 0 5. Accordingly, if the radio range of a node is 30m and its distance from the base station is 80m it assumes its NETWORK DEPTH is 3.

6. Each of the RFDs and FFDs periodically send join request if they have not yet joined any cluster head.

7. Periodically, each of the FFD node advertises itself as the Cluster Head and waits for the join request from the other FFDs or RFDs.

8. If the FFD node does not have NETWORK DEPTH equal to 0 then it will also send the join request to other FFDs. 9. Decision to choose parent for a FFD is based on received signal strength from the advertising FFD as well as the NETWORK DEPTH of the advertising FFD.

10. Node will always join the cluster head whose NETWORK DEPTH is less than or equal to the depth of the node, i.e. node will never join the cluster whose cluster head has depth more than the node itself.

Simulation

We use 2.4 GHz frequency range as it is universally used in the Zigbee networks.

In most of the sensor networks, if the sensor is out of range of its CH or more precisely that it is orphan and has no CH, node switch into the energy saving mode and thus sleeps for some time and then scans the network if any device is available to become the CH. However, it is not true in every case. E.g., in the automation of the logistics and the supply chain management of the frozen items inside the data-ware house, where strong emphasis is put on temperature control, any significant or minor change in the temperature is needed to LEACH algorithm is based on the rotation policy of the CH. This enables the proper energy utilization in the sensor network, as the same nodes are not burdened again and again to become CH. Even though, LEACH is designed for the static networks, the use of rotation policy makes it an ideal foil to select the CH in the mobile sensor network; since we need to select CH again and again. The simulation stops when the numbers of nodes inside the network are less than 5 or the time limit exceeds itself 3700s.

Energy distribution

We use four different scenarios to simulate the environment. As the motivation for having the heterogeneous network is to have energy efficient system, in all the simulation scenarios the total initial energy of the network is equal. We assume that in case of heterogeneous networks a node can either be a FFD or the RFD and 75% of the nodes are RFD and rest are FFD ones. FFD nodes are 333% more powerful than the RFD device. In homogeneous networks nodes, each node has 4.864J of energy. In heterogeneous networks FFDs have 10J and RFDs have 3J. However, average energy per node in the network remains the same in all the scenarios. Rationale for having heterogeneous network is to let some node act as the router or Cluster Head and other nodes just being the end devices. Therefore, the FFD nodes were made more powerful as they need to route the data consistently.

Description

The four simulation scenarios (Table 4.2) represent the different network topologies. Scenarios {1, 2} are comprised of homogeneous nodes where every node is capable of routing.

• In Simple LEACH -Scenario 1, a node is at most 2 hop distance away from the BS and CH is directly connected to the BS. {3, 4} is the type of topologies they exhibit. While in the scenario {3} the choice of radio range helped in not only to compare the performance of the heterogeneous network but also to compare the performance with the homogeneous network (particularly, scenario {1}).

The scenarios {3, 4} provide the opportunity to contrast between the different networks.

Furthermore, radio range of scenario {3} is higher then the radio range of scenario {2} but lower than the radio range of scenario {1}. This provides an interesting opportunity to compare the networks, which not only differ in terms of the device types but also in terms of the radio range.

Results

This section studies the performance of the network scenarios based on the simulation parameters as listed in Table 4.3 and Table 3.3. It examines the performance of networks on the basis of three given criteria.

• Number of messages received at the BS.

• Number of nodes alive.

• Longevity of the network.

RESULTS

43

Messages Received If the whole set of FFDs are out of the radio range of for a given RFD node, the RFD node becomes orphan and cannot communicate with the BS. Thus, nodes in the heterogeneous networks are more likely to suffer repeatedly from the orphaning phenomenon. However, it is not the case with homogeneous networks. Therefore, number of messages received at the BS is much higher for the homogeneous networks. Moreover, if CH is more than one hop away from the BS, it requires another CH as an intermediate node to connect itself to the BS. In the case of the heterogeneous networks, a CH can itself be an orphan node.

Figure 3.3 shows the total number of message received at the BS at any given time. It shows that as the hierarchy of the network increases, the number of messages delivered at BS decreases. Performance is at its best in case of homogeneous single hop network and worst in case of the multihop heterogeneous networks; the higher the number of hops is, the poorer the performance is. Due to the mobility, not only a node changes its position but also the CH itself might have changed its positions as well. There are chances that the selected CH may also have moved out of the radio range of its own cluster. Same phenomenon may occur during the communication between the two CHs. Therefore, as the degree of hierarchy increases the performance of the network degrades. Performance degrades even more in heterogeneous networks, as very few nodes are available to become CH.

So, to improve the message reception, at least all nodes should have routing capabilities.

Life Time Efficient energy utilization is principle behind heterogeneous networks. Therefore, all the simulated scenarios had equal initial energy levels. This helped to understand the performance of the system on the basis of energy. Figure 3.4 gives an idea about the longevity of the network. It compares the number of nodes remained inside the network at any given time. We observed that Figure 3.5, the RFD nodes die more quickly than that of nodes in homogeneous networks. This happened due to the fact that the RFD nodes had less initial energy than that of homogeneous nodes and RFD nodes lost lot of energy while searching a CH. Finally, only FFDs remained in the network as they had the maximum energy. This rapid network degradation, in case of heterogeneous networks, also contributed to the cause of lower number of messages received at BS.

Conclusion

This chapter studies a sensor network comprised of two types of devices: FFDs, the devices which can route the packet as well as can act as the CH, and the RFDs, which can connect to the FFDs but incapable of routing or becoming the CH themselves. The heterogeneous networks in this chapter are similar to the networks proposed by the Zigbee.

Four different scenarios are simulated, two each for the homogeneous and heterogeneous networks. The four network scenarios varied in terms of topologies and device types. We have used energy as the constraint and examined the role played by topology while designing heterogeneous networks. It is observed that the performance of the network is deeply intertwined with the network topology. In the mobile sensor networks, increase in the network hierarchy increases the energy consumption in the network as well as degrades the performance of network in terms of number of received messages. Furthermore, due to the inability of RFDs to participate in routing, performance of the system degrades even further in case of the heterogeneous hierarchical networks. and some nodes on the table and inside a cupboard.

While most of the earlier peer studies are done on the test-bed, our studies are more comprehensive as we deploy sensors in the straight line, grid topology, in the isolated places as well as in the public area. Further, we deploy sensors in the outdoor as well as indoor area. Finally, experimental studies prove the results of the last chapter via real measurements.

Introduction

Most of the sensor applications are designed to use simple, cheap and tiny devices with limited battery power. Furthermore, when real sensors are deployed, they do not have access to GPS (which is high energy consuming as well as expensive). Therefore, sensors have no choice but to use some control messages. They have to flood the network with control messages like Beacons and then identify their exact location in the network. This procedure can be active or reactive. Based on the replies, they also construct their neighbor table or routing table to build the network topology.

The sensors do not know the exact physical locations of the other sensor nodes. This is the common assumption during simulation studies. The decision which sensor is near or far is dependent upon the received signal quality or in case of our experiments Link Quality Indicator (LQI). For each received packet, this value is obtained through Chipcon CC2420 [1] radio module provided in the Moteiv's Tmote Sky sensor [START_REF]Tmote Sky datasheet[END_REF]. As per the matrix of Chipcon, the higher the LQI value is, the better the link quality between the two nodes is. Therefore, in these sensors, if the LQI between two sensors is above a given threshold, they can communicate directly while accounting the overall network topology.

The most interesting aspect in any sensor network is the transmission power of the sensor, a major component of energy consumption in any sensor. Higher transmission power leads to better signal quality over a large area, nonetheless resulting in higher energy consumption and vice-versa.

Objective

The objective of our work is to understand and observe the issues which are relevant during the real deployment of sensor network :

A. Sensors can have low quality of radio antenna.

B. Deployment in an area where steady environment can't be possible.

C. Change in the orientation of deployment of sensors.

In this chapter, our main focus is to know the problems in the asymmetric link

Problem and Background

Last few years have witnessed the tremendous leap in sensor network domain. Indeed, researchers try to exploit all the parameters that this domain provides to improve the performance criteria of the proposed solutions, protocols, and algorithms. In [START_REF] Gungor | Resource-aware and link quality based routing metric for wireless sensor and actor networks[END_REF], authors present a resource-aware and link quality based routing metric for wireless sensor and actor networks in order to adapt to variable wireless channel conditions in such heterogeneous networks. In the field of localization, Blumenthal et al. use the LQI to estimate a distance from a node to some reference points [START_REF] Blumenthal | Weighted centroid localization in zigbee-based sensor networks[END_REF]. More currently, the experimental/deployment analysis become one of the forefront subject in WSN field. Recent experimental studies [START_REF] Wahba | An empirical evaluation of embedded link quality[END_REF],

[61], [START_REF] Son | Experimental analysis of concurrent packet transmissions in wireless sensor networks[END_REF], [START_REF] Srinivasan | Understanding the causes of packet delivery success and failure in dense wireless sensor networks[END_REF] and [START_REF] Zhao | Understanding packet delivery performance in dense wireless sensor networks[END_REF] have shown that in real sensor network deployments, wireless link quality varies over space and time. In [START_REF] Lal | Measurement and characterization of link quality metrics in energy constrained wireless sensor networks[END_REF], authors investigated performance issues related to node placement, packet rate and distance. In In all the work, authors have taken into account the homogeneous nature of the network, where all the nodes have equal transmission power. Higher energy emission leads to better signal over a large area, resulting in higher energy consumption. This work compares the various homogeneous and heterogeneous scenarios (described in next section) and their effect on Link Quality and hence on the connectivity of the network.

Thus, a sufficient reason for our interest in the link quality is to answer the following questions. Is this parameter time-varying? What are the factors of this variation? How does LQI depend on transmission power and distances between the nodes? And finally, what are its impacts on routing and network topology?

Experimental Set-up

In order to experience and understand how few fundamental aspects of deployment can influence the sensor network as a whole; let us analyze some real time deployment In fact, all these scenarios helped us to compare several as well as relevant configurations for a given sensor network. We started with simple straight line topology, observed the network with time, node displacement, positioning, connectivity, etc. Then applied those observations by adding node redundancy (grid-topology) to the network.

Tool

Tmote Sky is a small platform including a microcontroller operating at 8MHz, 48K of ROM, 10K of RAM, a 2.4GHz ZigBee wireless transceiver, and a USB interface for device programming and logging. Each device operates on 2 AA batteries. Tmote Sky node Figure 4.2 provides an interface to parameterize its transmission power. The parameter varies from 1 (-25 dBm, minimum Transmission Power Level (TPL)) to 31 (0 dBm, the maximum TPL). Therefore, just by varying the TPL parameter transmission power can be increased or decreased. Additionally, in all the scenarios only printed antenna on the sensor has been used (no additional external antenna). Furthermore, all the sensors are placed on the floor.

All scenarios, as described in Table 4.2 later are based on following assumptions: • Deployment in an area with steady environment is not possible.

Sensors are deployed in two sets.

• Outdoors. • Indoor.

Outdoor Deployment

In the first set, sensors are deployed in direct visibility in open area with clear weather, all together in 5 scenarios. Each sensor transmits at 0dbm.

Remarks on

Table4.1 :-Typically, at 0 dbm, a Tmote Sky sensor has a range of around 100 meters. Therefore, as all sensors transmit at 31 TPL (0dbm) transmission power, all sensors connect directly with the BS.

So, 0dbm at outdoors do not present significant network insight. As our main focus is to study the behaviour of multihop network. Therefore, it is imperative to reduce the transmission power of the nodes. So, now we focus more on the indoor environment with reduce transmission power.

Indoor Deployment

In the second set, sensors are deployed (Table4.1) in direct line of sight in indoor area (all together in 40 scenarios). The tests are conducted in two phases.

In the first phase, Scenarios 1 to 29 (Tab. 4.2), nodes are placed in 2m (approx.)

wide indoor corridor (in straight line, direct visibility) along the wall. Further, the area is open to public and has experienced frequent movements of people during the measurements.

In order to understand the effect of transmission power, the node density, etc; the number of nodes as well as transmission power of the nodes is varied. 12, 7 and 5 (including BS) are deployed separated by 3, 6, and 9 meters respectively. For each set of above • When BS transmits at 31 TPL, there is no noticeable affect on the received LQI even The scenario confirms that in the sparse network, the deployment configuration does not affect the LQI behaviour. The scenario confirms that in the sparse network, the deployment configuration does not affect the LQI behaviour. The scenario confirm that in the sparse network, the deployment configuration does not affect the LQI behaviour. Here, BS TPL is 5 in all the scenarios.

Finally, since the BS TPL is just 5, only few nodes can receive beacons from the BS.

The scenario confirms that in the sparse network, the deployment configuration does not affect the LQI behaviour.

Analysis and Observation

In the last section, we saw the behaviour of LQI with respect to the distance and transmission power. In this section, we will take LQI measurements of some of the relevant scenarios and do the comparative analysis between the various network topologies.

LQI with distance and time

The channel quality of a given sensor network is dynamic i.e., not only it is being affected by the limited battery of sensors but also by the periodic/random change in the In most of the sensor networks, the role of a BS is to collect data and send it to a remote server or end-user. The BS can be selected statically or dynamically. The LQI usually determines the connectivity between the various nodes. Here, we will discuss Scenario 24. In this scenario, we have 12 nodes including BS. Each node is separated by 3 meters and all the nodes are in straight line (direct visibility). BS) in the network. For Clarity reasons, we present the relevant results only for few nodes.

Initially, we have observed that, the node which is 33 meters away from the BS, is not

Impact of the high transmission power of the Base Station

Another important aspect of any sensor network is the transmission power of its nodes. Transmission power limits the range of any given sensor. Sensor network relies upon neighbor discovery and route discovery mechanism to communicate with BS. Therefore, it is interesting to see, how different level of BS energy may affect sensor network. Scenarios 26 and 27 are different only in terms of TPL level of BS. In both the scenarios, we have 7 sensor nodes, separated by 6 meters in the straight line. Figure 4.36 presents the LQI readings of each sensor with BS, in a two different networks (for ease of clarity, again only few nodes are depicted). As, we compare LQI values, we can observe, that just by increasing the TPL of the BS, the LQI between the nodes and the BS improves tremendously. Also, the lower the TPL of BS the lower is the LQI (apart from sensor which is nearest to BS). Further, we can clearly observe the difference of LQI readings of sensor which is being placed at a distance of 18 meters from the BS. Due to difference in LQI values of these sensors, sensor with BS (31 points, scenario 26) remains connected continuously with BS, the other sensor in Scenario 27 is rather connected via its neighbours.

Higher power level for a given node leads to a natural single hop cluster, since each node sees the BS as being close (even if it is far) and consumes lot of energy because of its high transmission power level. And then, each node tries to communicate directly with the BS instead of communicating to BS via a set of hops. This raises some more issues for example in terms of traffic where a traffic can be captured by a single high power node.

In fact, in the next subsection, we will magnify this effect in the grid topology and the ramification of this phenomenon.

Grid topology

Table 4.3 presents another set of tests (Scenarios 30-40). These tests are executed in an indoor room but in an area cut-off from the public. We have used two different grids of size 4x4 and 3x6. In both cases, sensors are separated by 3 meters. In these scenarios, two TPL sets are defined as SetMax{31} and SetLow{10,5,3}.

Link quality with distance and time

Here, the link quality variations are not completely due to the change in the physical properties of the channel because of the closed environment (a classroom) without any presence of people. Generally (Figure 4.37), all the collected values for every combination of distance and transmission power vary between 103 to 108. Furthermore, if we refer to other kind of experiments [START_REF] Wahba | An empirical evaluation of embedded link quality[END_REF], [START_REF] Lal | Measurement and characterization of link quality metrics in energy constrained wireless sensor networks[END_REF], [START_REF] Holland | Experimental investigation of radio performance in wireless sensor networks[END_REF] these values remain interesting because the packet received rate for such LQI values is high. For a given transmission power level, the LQI values are slightly different (i.e they decrease when distance from the Base Station increases); and for a given distance, these values decrease slightly when we reduce the transmission power.

When the distance from BS is higher than 3 or 6 meters, we notice some dramatic decreases in the LQI variations. We also observe that the variations of LQI are more frequent with the nodes placed along the wall, than when they are placed diagonally.

Influence of BS transmission power on topology

To conduct our experiments, we have used MultiHop LQI routing algorithm [5] in TinyOS, because the code for the Tmote Sky platform was available.

According to this algorithm, we noticed that the transmission power of the Base Station is a crucial parameter. Moreover, the BS has an important role in the network topology and the route changing. Indeed, in order to allow the nodes to choose their routes to reach the Base Station, the Base Station required to send beacon packets regularly. Station transmits with a higher power than the power of the nodes. In this case, all the nodes note that the link quality with the BS is sufficiently high to choose direct connections (Figure 4.38(a)). The second case, when the Base Station transmits with the same power than the nodes, we observed some multi-hop routes especially for the furthest nodes. The third case when the Base Station transmits with a lower power than the power of the nodes, several multi-hop connections appear with an important traffic overload on the nodes closer to the BS. (Figure 4.38(b)). Indeed, the routing algorithm issues that getting through these nodes constitutes the most optimal way (number of hops) and the most effective (link quality). We proved that by adding another node with a high transmission power beside the Base Station and all the traffics are transmitted via this node (Figure 4.38(c)).

As shown in

Influence of nodes transmission power on LQI and Multi-hopping

While the routing algorithm is mainly based on the link quality, thus, varying the nodes TPL implies certainly changes in the network topology. Here, we consider the scenarios 30 to 40 to analyze these changes according to the nodes-and BS-TPL.

Figure4.39 plots the average number of hops as a function of the BS-and node-TPL, observed in a grid of 3x6 nodes. We can note that the number of hops increases with the reduction in BS-TPL. This result endorses the observations of the preceding paragraph on BS-TPL impact. The number of hops remains reasonable (3) even with the lowest BS-TPL because the area is relatively small (6x15m).

On the other hand, Figure4.40 illustrates the difference between two sets of sce- narios Set{35,36,37} and set{38,39,40}. In these two sets we used two distinct Node-TPL (respectively 10 and 5). In this figure we can clearly note that the number of multi-hop paths is always higher when the node-TPL is lower.

Emulating RFD and FFD in real time

Chapter 3 discusses the potential problems in the implementation of FFDs and RFDs. To test this hypothesis, 26 nodes including BS are deployed in a cluster based topology as per the specifiction given in Table . 4.4.

The idea is to emulate the RFD and FFD topologies as suggested by the Zigbee as well as to observe the heterogeneity at various levels inside the network over a large, uneven, irregular area with relatively random deployment. Initially, we observed negligible connectivity inside the clusters. CH were able to connect with BS but the nodes inside the CH were unable to connect with CH. However, when the node were raised over the level of CH, they connect with CH. As the nodes were at power level of 5 TPL and were just inches above the ground, there radio link was obstructed with grasses as well as some other flora on the ground. However, as the sensors are raised, they don't get into these problems.

Later, to improve the performance of this network, TPL of RFDs is increased. It is like replacing RFDs with FFDs. As the TPL increases, the connectivity between the nodes improves. Though in these tests sensors are static, but they do confirm that RFDs are not ideal.

Conclusion

Focusing on using a commercial hardware platform in sensor systems, we have carried out in this work on an experimental study on the link quality in wireless sensor networks. In the first set of experiments, we studied the LQI evolution over time and observed the dynamics of transmission channel. Very briefly, we discussed the significance of positioning of the Base Station in any given sensor network. We saw, how network is sensitive to small node displacements. With these experiences, we presented LQI timevarying and some random disturbances due to external phenomena and physical changes.

It is very important to study these issues, as sensors may not be subjected to steady state deployment. Finally, we studied the impact of transmission power of BS and observed how sensors in networks with high TPL of BS can miss-construct network topology and the effects on the connectivity between nodes and BS. We saw, how a high power node creates a natural single hop cluster. We used these observations and experiences to conduct further experiments.

In the second set of experiments, we have also investigated the impact of nodes transmission power on the LQI which affects consequently the network topology. Indeed, with high BS-TPL and Node-TPL, often we observed only one cluster (BS as a clusterhead). When we varied the TPL between nodes (heterogeneous nodes), several clusters appeared (cluster-head with high TPL). So, it may be a possible solution to organize the network on clusters. However, such heterogeneity may affect the lifespan of these nodes and the network connectivity.

To know, is to know that you know nothing. That is the meaning of true knowledge.

Socrates

Chapter 5

Topology Challenges in the Implementation of Wireless Sensor

Network for Cold Chain

Chapter 4 discussed how the LQI can shape the network. This chapter discusses how it can affect the performance of the network. We take packet loss as the performance criteria. In the last chapter, we also proved that the Base Station TPL may have a misleading effect for the farthest nodes. Indeed, these nodes calculate that the link quality with the BS is sufficiently high to connect directly. But longer distance may increase the risk of packet loss. Also, the link quality of another direction (node to BS) is not necessarily be the same because of distance or weak Node-TPL.

In this chapter1 , we will study, understand: how the transmission power mismatch among the sensors can effect topology and its detrimental result on the message reception of a sensor network. We present that LQI being a major factor on routing, can have a detrimental effect on the performance of the network, especially on the Message Receive Percentage.

Introduction

A typical cold chain Wireless Sensor Network (WSN) will consist of large number of pallets and each being equipped with a temperature sensor. Generally, all sensors take temperature readings and team-up together to send this data to sink. If the temperature is over the threshold, alarms will be generated and the pallet can be localized and taken care of. In the absence of GPS, sensors need some physical parameters to calculate their relative distance in the network. So, sensors send beacons and based on beacons from other sensors, the neighbor table is computed by each sensor node and the network is constructed.

Recently, channel quality is being measured in terms of Link Quality Index (LQI)

and Received Signal Strength Indicator (RSSI) and these are becoming the standard metrics for routing algorithms. However, these parameters are very fickle and time variant and are greatly dependent on the following parameters:

• Wireless Channel:

-Susceptible to any change or orientation of physical medium.

-Interference from competing technologies

• Radio:

-Nodes typically are not equipped with high performance antennas.

-Some nodes are placed in direct sight of vision and some are not.

-The loss ratio of the link can be high.

• Random Deployment:

-Physical distance between the communicating nodes can vary significantly.

-Obstacle rich environment causes sharper fading.

• Temporal Effects:

-Random change in the quality of channel, causing variable packet loss in the channel.

-Death or birth of a node.

BACKGROUND

83

-Deployment in harsh, inaccessible places may exhibit significant behavior in multi-path communication.

The above contexts are the typical constraints while deploying WSN to monitor cold chain.

Background

In the real time deployment of the sensors, now, it has become a well established fact that radio links are unreliable [START_REF] De Couto | A high throughput path metric for multi-hop wireless routing[END_REF], [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF], [START_REF] Zuniga | Analyzing the transitional region in low power wireless links[END_REF], [START_REF] Becker | Experimental study: Link quality and deployment issues in wireless sensor networks[END_REF]. Holland et al. [START_REF] Holland | Experimental investigation of radio performance in wireless sensor networks[END_REF] conducted experiments using 20 motes in outdoor and indoor and have observed that LQI very closely related to packet yield. Further height of sensors played a significant role in performance. This fact is also noted in [START_REF] Becker | Experimental study: Link quality and deployment issues in wireless sensor networks[END_REF].

In the last chapter, we deployed motes with different transmission power levels in indoor environment. We observed that a sensor network is sensitive to small node displacements and LQI varied with time because of some random disturbances due to external phenomenon and physical changes. They also observed that, powerful nodes become cluster heads.

In most of the articles, authors have considered only the homogeneous nature of the network. However, it is not possible in the real deployment. Sensors differ, may be because of the orientation, hardware problem, etc. With respect to LQI, they differ, as LQI varies with distance, so by changing the transmission power of node, we are effectively changing the distances among the sensor. Also, by the time, may be some sensors run out of battery or their transmission power have decreased.

In this chapter , we will study, understand and investigate: how in heterogeneous networks, transmission power mismatch among the sensors can affect topology and its detrimental result on packet reception of sensor network. Then, we have exploited the characteristics of LQI and asymmetric links to emulate rugged terrain and other obstaclerich environment and show that adding some powerful nodes can be one of the way forward to improve the performance of sensor networks.

Deployment context and the Cold Chain

In all the deployments, a Tmote Sky sensor attached to Laptop acts as the BS and it is the only difference between the BS and the other sensors. In the previous chapter, we saw the evolution of LQI. The motivation of this chapter is to check how this LQI mismatch effects the packet losses in the network. So, we deploy nodes in different environment areas and topologies. In the second set, sensors are placed inside the gymnasium and they were deployed in 10x4 grid (40 sensors including BS). Distance among sensor was 4 meter. We varied the TPL for both BS and other nodes.

In the third set, sensors are deployed inside a class room in a grid topology (6x3).

They were placed on student's desk 80 cm (approx.) above the ground. We again vary TPL of nodes. All these tests were conducted at room temperature, 15-20 degrees Celsius.

In the final set, we deployed sensors in grid of 10x5 (50 sensors including BS).

Influence of Bluetooth, Wi-Fi

For most part of deployment, nodes were under the influence of either Bluetooth or Wi-Fi. While running experiments, we transferred some files using Bluetooth, but it had a very marginal effect, restricting itself to a very minor change in topology. It may be due to the limited reach of Bluetooth itself. In case of Wi-Fi, whole network was under the influence of Wi-Fi. We do not observe any influence of the Wi-Fi. In fact, our deployment once created the interference for another Zigbee network.

Effect of Subzero Temperature -Unresolved Issue

During our experiments, we faced several problems. Malfunctioning of sensors was the major problem encountered by us. Initially, we deployed sensors with 5 TPL under sub-zero conditions on the floor. However, very few sensors worked that too in some cases with high loss ratio up to 99%. Even then, in all the cases sensors stopped responding, after 2-3 minutes of deployment. Then, step by step, we increase transmission power level to 20.

At 20 TPL, sensors start working, but even at that high transmission power, we find very difficult to take any significant readings, etc. We tried this for over 3 days. Every time, when ever sensor was compiled it started working but again it stopped functioning after some time. Finally, we stopped deploying sensors under sub-zero temperature. We assumed that since sensors were placed on the floor, it might have some influence of the battery (AA)

or on the hardware platform, or because of some issues related to electrostatic charge while handling the motes, etc. Finally, we carried out measurements, when temperature was around 10 degree Celsius.

Observation

In the last chapter we saw, how LQI varies over the distance and the effect of HP nodes on the network. We observed that nodes tries to connect with the nodes having better LQI. So, in this section we discuss the packet losses when BS nodes transmits at different power levels. For the ease of understanding, we are presenting only the 3 relevant scenarios. In all cases, BS transmits at 31 TPL. Initially, nodes transmit at TPL= 25 and then we gradually reduce it 5 (third case). We can observe as we reduce the TPL of the nodes, the MRP of the nodes also decreases.

Homogeneous Vs Heterogeneous Nodes-straight line

When nodes transmit at TPL=25, MRP for each node is close to 99%. In the second and third case, when nodes transmit at TPL= 20 and TPL=5, till 24 meters the packet reception is in the band of 70-90%. After that, for TPL= 5, the packet reception drops to less than 20% for the node which is 36 meters away from the BS. When TPL= 20, the packet reception is close to 70% for the same distance.

It seems that as we reduce the TPL of the nodes the losses increase. So, we deploy nodes and BS with homogeneous transmission power level. We deploy node and BS with TPL =5 and the compare MRP with the case when BS has TPL= 31 and nodes have TPL=5.

Figure 5.5 shows Message Received Percentage for each node with respect to its distance from the BS. It illustrates that when both BS and nodes are set at TPL = 5 TPL, MRP is over 90%. However, when BS is set at 31 TPL, message reception drops sharply.

This happens, as sensors calculate that the BS with very high TPL, is nearer to it than the In conclusion, by varying the transmission power of BS, topology changes are induced. Moreover, high TPL of BS leads to loss of packets sent by the nodes (farthest) because they try connect with the BS directly. Instead, they should have used multihop scheme. This can be a problem in the real deployment of sensor networks.

Effect of surroundings

Another example of how topology affects the performance of a WSN is shown in Fig. 5.6. It shows the average message loss percentage of 50 nodes separated by 4 meters when placed in a grid (10x5) in two different conditions. In ideal conditions, each node should have a range up to 100 m. In the first case, when nodes were placed indoors the losses were negligible. However, when the nodes were placed in an obstacles rich environment message losses increase to 45%.

Role of height

We have observed that when the nodes are placed on the ground they have more losses than the case when the nodes are deployed by approximately 80 cm above the ground (on a table, Scenario {37-51}). Fig. 5.7 shows the MRP of 18 different sensors with their is close to 100%, when nodes are placed on the table, while in the other case it just hovers around 50%. However, it is true only when there is a huge difference between the TPL of the BS and other the nodes, while in other scenarios (in same condition) the MRP is close to 90-100%.

Using LQI to select the Cluster Head

So far, we have seen that the mismatch in the LQI values from the beacons of the node and the BS can have detrimental effect on the performance of the sensor network.

So, we decided to exploit the same feature (LQI) to select a node as a CH. If the sufficient number of HP nodes can be introduced in the network, using LQI as the selection criterion, they can become CH.

We add some nodes with higher transmission power Scenarios 31-34, we found them to have the stabilizing effect on the network. Some of the nodes become clusterheads and then route packets to the BS. Figure 5.8 shows this effect. As we add more and more high power nodes, the losses in the network decreases. Now, sensors connect with the BS via CH. In conclusion, HP nodes can be the criteria to construct network topology but further work in this direction is needed.

Conclusion

Transmission power of any sensor plays very important role from designing to implementation of any sensor network. The real deployment of nodes has been a tricky situation for researchers. Also, in reality, its not possible to have homogenous networks, as sensors will always remain different because of their placement orientation and other physical variables present in the network. In this chapter, we have studied various topologies in sensor networks. We deployed sensors in grid, straight line, on the floor, over the table, in public place as well as secluded place. We have also varied the distances as well as the transmission power of sensors. We have investigated the multihop topology in the heterogeneous sensor networks. We have observed how the mismatch in transmission power of BS and nodes could result in high packet losses. This is true, especially, in cases where, BS is very powerful and nodes are quite feeble. Due to the strong influence of BS, nodes evaluate that BS is nearer to them with respect to other sensors present in the network.

And, we have seen, despite having high LQI, how the amount of packet lost can be higher in these networks. Finally, this chapter raises question: Does LQI, really give you the reliable information, especially in case of heterogeneous sensor networks? These results are interesting, as in classical approach, BS is considered as a very powerful device.

The experiments confirm that interferences (e.g. in the grid scenario) as well as multi-path fading, etc strongly increase the packet losses. Furthermore, scenarios with huge differences in transmission power (e.g. high power BS, low power clients) result in higher message losses. We have also seen that an algorithm behaves differently when its surrounding changes. We also propose to have some high power nodes to answer asymmetric link problem and to stabilize the network.

Later, we use LQI as the criteria of choosing cluster heads. Then, we show that by distributing enough high power nodes (working as Cluster heads) it can stabalize the network and indeed can be beneficial to the network.

having the least estimated cost of reaching the BS is selected as parent.

The problem arise when the downlink LQI is better than uplink LQI. For example, if the transmission power of the nodes A and B are different, two different values of LQI are estimated for each direction of link (From A to B and B to A). To prove this problem, we deployed sensors in two topologies:-1. Straight Line and 2. Grid.

Deployment in Straight line

We deployed 7 sensors in a straight line separated by 6 meters each. All sensors had direct line of sight. They were deployed in a 2 meter (approx) wide corridor isolated from the public. Each node sends 12 packets/minute of packet size 70 bytes for 110 minutes.

Two different experiments were carried out.

• Case 1: All the sensors including BS were deployed with the Transmission Power Level (TPL) of-20 dbm.

• Case 2: Nodes TPL= -20 dbm and BS TPL= 0 dbm.

Sensor connected to the Laptop became the BS and it was the only difference between the nodes and the BS. The sensors description and the choice of the wireless channel are described in the Section 6.4.1.

LQI distribution over distance

Effect on the Hopcount

When BS transmission power is higher than other nodes, the LQI received by the nodes from the beacon of the BS is better than the other neighbouring nodes. Following the behavior of the MultihopLQI, nodes calculates that the BS is nearer to them than the other nodes. Then, they will try to send their data directly to the BS, even if the transmission power is not sufficiently high to be received by the BS. When BS transmits at 0 dbm, there is not much change in the hopcount. In fact, for the node which is 36 meters away from the BS, the hopcount drops from 4 to 2 as the BS TPL increased from -20 dbm to 0 dbm. Therefore, just by varying the transmission power of BS, topology changes can be induced. Moreover, this leads to a situation where the data from the nodes are lost because they try to reach directly with the BS which is too far. Instead, they should have used multihop scheme. This can be a problem in the real deployment of sensor networks. To verify this phenomena in the grid topology, 18 nodes (3x6) including BS were deployed in the class room. Nodes were deployed on the table. Distance between the nodes was three meters. Parameters for experiments are as follows:-

Effect on the Hopcount-Grid Topology

• Transmission power of BS varied from 0 dbm to -25 dbm (in steps).

• Nodes transmission power was set to -20 dbm.

Figure 6.3. shows average number of hops per node in the sensor network as a function of BS transmission power level. We can observe that by varying the BS TPL, topology changes can be induced in the network. The number of hops are reasonable for this relatively small deployment area (6m×15m), but same phenomenon is observed.

To summarize, MultihopLQI lead nodes to directly connect with the BS. In other words, it influences the node to choose bad routes because it considers quality of the links are symmetric. In the next section, we present the algorithm to optimize the MultihopLQI. • Initialization: In the this phase, we use the MultihopLQI algorithm to construct topology of the network. : Whenever a node receives a packet from other nodes, it sends an acknowledgment. In this way, we calculate the PLP between the two given nodes. Table 6.1 shows routing table of node A. By fully utilizing the information via LQI and as well as probability of packet reception, we can find the better link.

• Route Selection: PLP between the nodes can be good, intermediate or poor. Therefore, we also treat the PLP in three different ways and the lower the PLP is, the lesser is its importance.

-If the PLP of the node is less than some threshold value (5% in our case), we do not take into account the LQI based estimation. The node with lowest PLP is selected to route the packet.

-If PLP is above the threshold value (5%) but less than twice the threshold value (10%), we select the node having least LQI cost among the nodes having PLP within 5-10%. In this manner, relevance of PLP is reduced marginally.

-If the PLP is even greater than twice the threshold value, it is assumed channel quality is already bad. Hence, we directly use the LQI.

In HybridLQI, when the acknowledgment fails but PLP is within the agreed range, we continue to send packet to the same parent. However, if the PLP increases over a certain threshold, new parent is selected. On the other hand, in MultihopLQI, whenever the acknowledgement fails, we go back to the routing table and select the new parent with least estimated cost automatically. Nodes receive periodic beacons which can have very good down-link LQI but may have poor up-link packet reception.

Using PLP, we can rectify this problem in the MultihopLQI.

• Routing Table Maintenance: When a new beacon arrives, the link cost is updated.

However, the nodes with lower PLP are given preferences and they are not evicted from the routing table even if their LQI based estimations are high. First priority while sorting the table goes to PLP. However, when a node is again added to the table, its PLP value is reset. In this way, the non-relevant history of the node has no bearing on the routing metrics. So, when the sensor is added again to the routing table, it starts new.

In short, each node keeps the following information:

• Number of packets sent.

• Packet Reception: Once the Acknowledgment is received, the reception counter is increased.

• Packet Drop: If the node fails to transmit the packet even after 5 retries the counter is increased.

SETUP 100

Table 6.1 shows an example of HybridLQI where the node A computes its routing table. If only LQI based cost estimation is used, the node D will be selected as parent by the node A but it will experience higher losses. By using HybridLQI, the node A will select node B to route its packets. If the PLP is within the threshold value and the acknowledgement fails from the parent, the node will not change its parent. In MultihopLQI, the node changes its parent if the acknowledgment fails.

6.4 SetUp

Platform

Tmote Sky [START_REF]Tmote Sky datasheet[END_REF] sensors consists of a microcontroller operating at 8MHz, 48K ROM, 10K RAM, a 2.4GHz ZigBee wireless transceiver (Chipcon CC2420). It has a printed antenna for wireless communication. No additioanl antenna was used for the communication. topology. TPL of all the nodes was 0 dbm. Figure 6.5 shows the deployment topology of the network. In the first case, nodes were placed indoor on a very smooth and glossy floor (direct line of sight). In the second case nodes were deployed in obstacle-rich environment.

TestBed Area

Evaluation

This section discusses the experimental results obtained when the MultihopLQI and HybridLQI were deployed in dense and sparse conditions. MultihopLQI and HybridLQI were run as per the parameters shown in Table 6.2 and in five different scenarios (Table 6.3). Each test was repeated 10 times approximately.

Deployment in a Dense Network

When the nodes were deployed at TPL = 0 dbm, most of the nodes were into the direct communication with each other. Similarly, when BS was deployed at TPL = 0 dbm, HybridLQI and MultihopLQI. We can see that when both the algorithms were deployed at 0 dbm, they had the minimum losses. Decrease in the TPL of the node increases the relative distance between the nodes. This increased the hopcount of the nodes needed to connect with the BS. So, as we decreased the TPL of the nodes, the loss increased.

In Scenario 1, when the nodes and BS transmited at 0 dBm, HybridLQI had 16% fewer losses with respect to MultihopLQI. For Scenario 2 and Scenario 3, HybridLQI had 20% and 17% less losses respectively. Also for the Scenario 4 and 5, HybridLQI performs better than the MultihopLQI. In fact, HybridLQI performs more or less equally in the symmetric as well as asymmetric scenarios. Therefore, by using the HybridLQI algorithm, we can effectively improve the performance of asymmetric links for LQI based algorithms.

In case of a dense network, there were several routes to the BS. And as the distances between the BS and the other nodes were relatively short, the performance of the HybridLQI was rather limited. Another reason for the limited performance of the HybridLQI was due to the strict adherence to 5-10% loss limits. But when we deployed the nodes in the real world, the number of retransmissions were very high.

Deployment in a Sparse Network

In the case of sparse networks, there are not many routes to reach the BS. If the BS is more powerful than other nodes, it distorts the network's equilibrium. Therefore, based on the LQI a sensor receives from the BS, it misconstrues the topology and then tries to communicate directly with the BS.

7 nodes are deployed including the BS in the straight line separated by 6 meters.

HybridLQI and MultihopLQI are deployed as per parameters described in Table 6.4 and Table 6.5. Asymmetric links between the nodes and the BS by setting BS at 0 dBm and the other nodes at -20 dbm. Figure 6.7 shows the message receive percentage of the 6 individual nodes from the BS for the two algorithms. The node which is 6 meters away from the BS can communicate directly with the BS. Since the distance is very short, Message Receive Percentage (MRP) is close to 98%. For HybridLQI, Message Receive Percentage is close to 97%. This negligible difference can be explained more on the basis of some changes in the temporal characteristics of the physical medium. Also, for the node which is 12 meters away from the BS, MRP in both cases is over 90%. Similarly, nodes which are 18 and 24 meters away from the BS, the MRP decreases in both the cases, due to the very low transmission power of the nodes (-20 dbm).

We can clearly observe from the Figure 6.7, in the HybridLQI algorithm, the performance of the node which is at 36 meters away clearly increased by 350%. We must remember, when we calculate the MRP, we do not take into account the number of retries.

But retries number is limited to 5 and after that the message will be simply dropped.

The nodes which are at 30 and 36 meters from the BS receive beacons from their neighbours and the BS. Since the BS transmits at high power, the nodes in MultihopLQI misconstrue their topologies and try to send packets directly to the BS. However, once the acknowledgement fails, the node forwards its message to another node. Nevertheless, due to the unreliable wireless links, whenever the acknowledgment fails from this node, the node again checks its routing table. In the meantime, new beacons arrive from the BS and the routing tables are sorted to the earlier state where the BS is at the top. Since MultihopLQI assumes links to be symmetric, the procedure is repeated and the performance of the network drops. However, if we take into account the PLP, this problem can be solved without losing more packets.

Observations and Discussion

This section discusses some issues about packet drop in the sensor network using MultihopLQI and HybridLQI.

Deceptive Acknowledgement

In MultihopLQI whenever a node sends a message, it waits for an acknowledgment.

And if it does not receive that reply, it retransmits that packet to another node. However, sometimes one node receives the packet and it sends back the acknowledgement. However, that packet is lost by some intermediate node. Let's say node A forwards one packet to node B, and when node B receives the packet, it sends an acknowledgment to node A. Later, node B forwards that packet to the BS or to some other node. Sometime it was observed that the packet is lost because of a deceptive acknowledgment. As B was unable to forward that packet to the BS or other nodes even after 5 retries, the packet was simply dropped.

Therefore, the packet sent by the node A is simply lost.

6.6.2 High values of LQI do not translate into a good connection given time. However, as we add more and more nodes, the channel quality can deteriorate, as it can no longer be measured as a function of only two sensors. This channel quality is affected by the behavior of other nodes. Therefore, there is an issue regarding LQI sampling and estimation and the way it is done by the MultihopLQI. This procedure can be improved.

Our views are confirmed by the Figure 6.8. It plots the average LQI between the nodes 22, 25, 27 and the BS with node 24 when 5x10 nodes were deployed in a grid topology with 0 dBm transmission power level. Node 24 is an interesting choice as it is more or less in the center of the network. However, despite having such a good LQI even directly with the BS, the message losses at node 24 are close to 20%.

Transient Performance Loss

While doing some experiments, we observed that the performance of MultihopLQI drops suddenly and increases the losses in the network. It is especially true when there are more retransmissions. In fact, it is a vicious cycle. The higher the number of retransmissions the greater the losses, which again increases the burden on the network. It continues until the nodes drop some packets. To deal with this kind of problem, the authors [START_REF] Gnawali | Collection tree protocol[END_REF] suggest using adaptive beaconing. In a future work, we will explore this idea for HybridLQI algorithm as well.

Also, using other congestion control mechanisms will definitely cut down the rate of retransmission. As we cut down this factor, the performance of the routing should improve considerably.

I think that in the discussion of natural problems we ought to begin not with the Scriptures, but with experiments, and demonstrations.

Galileo Galilei

Chapter 7

Implementing Clustering in Real

Wireless Sensor Network

One of the ways to organize sensor network is to divide whole network into small virtual groups (clusters) based on some rule. These control clusters perform control functions in their sensors which are equipped with data processing and communication capabilities. Few cluster formation contexts are as follows:-

• Distance or proximity.

• Logical organizing.

• Topology control.

• Load Balancing.

• Network Scalability • Nodes are partitioned into groups according to some rules.

• Once the portioning is completed, each partition has one cluster head which controls the whole cluster.

Motivation

An ideal wireless sensor consumes very little power, is software programmable, is capable of fast data acquisition and processing and costs little to purchase and install. In • Data aggregation and updates take place in CHs.

• Improve network lifetime.

• Reduce network traffic and the contention for the channel.

• Limits data transmission.

• Facilitate the reusability of the resources.

• CHs and gateway nodes can form a virtual backbone for intercluster routing.

• Cluster structure gives the impression of a smaller and more stable network.

Building clusters

Several works have done simulation and theoretical analysis of the clustering process in the network. Vision of the senor network is to have nodes piecing together the information and feeding it to Base Station. The network which is without an autonomous BS has only theoretical significance, as network finally needs some central authority to collect data from those nodes. We doubt to have a network where nodes are collecting/ sensing some information but are not reporting them to any of the authority but to themselves.

Even if the network is fully autonomous, nodes need external source to switch them ON.

So, in this work, our goal is to create clusters which will be sending their information to the BS. However, even if there is no BS, our proposed clustering process can work, based on some assumption e.g., node with smallest node id will win the contention. (However, we

have not yet implemented it, but it can be easily be done without disturbing the other nitty gritty of this work.)

Matérn hard-core Process

The Matérn hard-core process (MHP) is a poisson point process where no points are allowed within the vicinity of a given distance from a point. According to Baccelli et al. [START_REF] Baccelli | An aloha protocol for multihop mobile wireless networks[END_REF] the Matérn hard core process is a natural model for the access scheme of HiPERLAN (High Performance Radio LAN)) type 1 and The MAC of HiPERLAN type 1 actually uses an advanced version of CSMA. [START_REF] Hoydis | Effects of topology on local throughputcapacity of ad hoc networks[END_REF] suggests that MHP distribution may not perform in comparison to modified Thomas point process (TPP) and the Matérn cluster process.

However, they confirm that the MHP gives regular point. In this work, we will be making clusters based on the MHP as our goal is to have CHs spread evenly across the network to make network more connected. Also, Thomas Point Process will not give regular points.

Description

In the stochastic geometry "Thinning operation uses some definite rule to delete points of basic process.". We can apply the same concept to calculate the minimum number of nodes required to diffuse the information over the whole network. The thinning process can be characterized into two types: independent and dependent thinning processes. In case of independent thinning points are independent of the each other (location, in case of sensor nodes) and the vice-versa in other case.

If the characteristics of the basic process are known then it is straightforward to calculate the characteristics of point process produced by independent thinning. Thus, if Φ is the result of p(x)-thinning of Φ b , then its intensity measure ∧ is given by

∧(B) = B p(x) ∧ b dx (7.1)
Where B is borel set.

Matérn Hard core Process (MHP) [START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF], is essentially a dependent thinning applied marks smaller than m(x). Formally, the thinning process Φ is given by:

"Φ = {x ∈ Φ b : m(x) < m(y)∀y ∈ Φ b ∩ b(x, h)\{x}}" (7.2)
The basic principle to use MHP as the clustering mechanism is that inside a cluster there can only be single cluster. If the node falls in a zone where a CH is already present, it can t become a CH.

Let us assume a simple case, where CHs have to be separated by minimum distance h and sensors lying inside that area or sphere whose radius is given as R = h 2 cannot become CH. If d is the degree of Borel b and by applying the Matérn hard-core process and Palm retaining probability of a typical point in a point process, the following result is derived [START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF](pages-145-165). point process with intensity 1000. Initially, a node is randomly selected. Then, Matérn hardcore process is applied and points are selected as cluster head. The number of cluster heads is a property of radio range of the node. The larger is the transmission range of the sensor node, the smaller is the number of cluster heads (as shown in Figure 7.3).

Grid Topology: Further, Eq. (7.2) is valid for poisson distribution, but it can be applied in the grid topology as well. While in case of Poisson only bounds can be obtained, In case of grid, we can calculate the exact number of CHs. In this chapter, we will use Eq. 7.2 to apply the thinning on the real sensor deployment.

Max-Min cluster Formation Heuristic

In the well known heuristic proposed in [START_REF] Amis | Max-min d-cluster formation in wireless ad hoc networks[END_REF], the d-dominating set of CHs is first selected by using nodes identifiers and then clusters are formed. [START_REF] Delye | Correction, generalisation and validation of the "max-min d-cluster formation heuristic[END_REF] and [START_REF] Delye De Clauzade De Mazieux | Proof of the generalised maxmin[END_REF] further corrected, validated and generalized the Max-Min heuristic and show that rule 2 of the cluster formation creates loops in the network.

Max-Min uses 2d+1 rounds. Where d is the number of hops a node can be away from its CH. The first round, exchange of initial information such as weight is done. In the following d-rounds, Max Min has floodmax phase, which is followed by the floodmin phase in the final d rounds.

The WSN can be modeled as a graph G = (V, E), where two nodes are connected by an edge if they can communicate with each other. Let x ∈ V be a node in the WSN.

N (x) is the set of neighbours the node x and W (x) is the weight of the node, which in our case in the degree of connectivity given as D(x).

Initial Phase k = 0 ∀y ∈ V, W 0 = D(x), S(x) = x (7.4) FloodMax Phase k ∈ [|1, d|],
Assuming that ∀x ∈ V , W k-1 (x) and S k-1 (x) are known in previous step. Let y k (x) be a unique node in N (x) defined by:

∀y ∈ N (x)\y k (x), W k-1 (y k (x)) > W k-1 (y) (7.5)
W k and S k are calculated as follows:

∀x ∈ V, W k-1 (y k (x)), S k = y k (x) (7.6) FloodMin Phase k ∈ [|d + 1, 2d|],
Assuming that ∀x ∈ V , W k-1 (x) and S k-1 (x) are known in previous step. Let y k (x) be a unique node in N (x) defined by:

∀y ∈ N (x)\y k (x), W k-1 (y k (x)) < W k-1 (y) (7.7)
W k and S k are calculated as follows:

∀x ∈ V, W k-1 (y k (x)), S k = y k (x) (7.8)
The set of CHs are defined as follows:

S = x ∈ V, W 2d (x) = v(x) (7
.9)

Implementation

This section describes the implementation of Matérn Hardcore Process and Max-Min cluster formation heuristic.

Matérn Algorithm

The basic algorithm, is described in Figure 7.5.

Step 1: Base station declares itself as cluster head. Adjacent nodes getting beacons from CH join it and form cluster. The structure of beacon message is follows:

typedef struct BeaconMsg { uint16_t parent; uint16_t cost; uint16_t hopcount; // from me to "base station" So, a node sending a beacon, which is not so far connected to the network will be able to mention this its to its neighbour. So, the beacon message will make sure that only nodes which are connected to the cluster head, can become CH. In our work, the field cluster hopcount is 1, however for future use, it can implemented with more than one hop and node can be k hop away from the BS.

Step 2: Nodes not connected directly with CH declare themselves as CH. A conflict arises if more than one node in same area of influence declares itself as CH.

Step 3: This conflict is resolved using node-id. The node which have higher id will cease to be a CH.

Step 4: Node which loses right to be a CH sends special messages that I am no longer a CH.

The nodes on receiving these special messages from their CH again participate in process of clustering. The new nodes wait to join cluster before declaring itself to be CH.

In this implementation, we wait for single packet.

Once the clustering is over, HybridLQI algorithm is used to perform inter-cluster routing.

Functioning

The process of clustering is initialized by base station. Initially every node (except base station) is unconnected. All clustering will be done by beacon messages which are also being used in routing. Base Station (default CH) start sending beacon messages. The reception of beacon is handled via three cases:-Case 1: If a node receives beacon message from CH with required LQI value (106), three more conditions are possible:

• If node is not connected, it will join that CH and set it status as connected and start sending beacon messages.

• If node is connected but itself is not CH, it will keep this CH in its cluster table.

• If it is clusterhead itself, it will check if it needs to remain cluster head or not. This is because we do not want two clusters in same sphere of influence.

Case 2: If node receives beacon message from connected node (either a cluster head or any other node which is connected) basically we want that only connected node trigger the formation of clusters and if the node itself is not connected, it will check if it needs to declare itself as clusterhead or not.

Case 3: The cluster head will use these beacons for routing. Other nodes which are not clusterhead, will simply route to their clusterhead. Now clusterhead will send this packet to base station.

Max-Min algorithm

The basic algorithm, is described in Figure 7.6.

The Max-Min algorithm (for d=1) as described below is implemented in 5 phases.

1. Phase 1: It is an initial phase, where each node will broadcast it beacon message with TTL=1 ( time to live). This is done for neighbour discovery. Like in the case of MHP, to be considered as a neighbour, LQI between two links should be of at least 106. Nodes determines their own weight and stores their information in the neighbour • Node must send its phase messages repeatedly so that it neighbours could be able to receive them. Also, the nodes which are in Phase 4 can only process these packets.

• A pause is necessary after this phase as nodes enter in Phase 4 at different time, therefore to have a correct view of the network, a node must wait for some time.

5. Phase 5: Finally, the nodes can decide if it can become a CH or not. CH then sends a burst of beacon message so that other non-clusters can join it.

Once, the clustering ends, we perform inter-cluster routing via HybridLQI.

Analysis

Effect of node density on Max-Min

Initial phases of Max-Min has huge memory requirement and in fact it increases linearly as the number of nodes increases. We explain it via an example. We conducted two sets of test:

• In the first set, we deployed 12 nodes including BS.

• In the second set, we deployed 30 nodes including BS.

ANALYSIS 120

Both of these test were conducted over an area of 20 m 2 where a node is supposed to be a neighbour if the LQI between the nodes is greater than or equal to 106. So, basically, we increased the node density of the of network. Max-Min is required to store information for all of its neighbours, so the difficult we faced was the amount of memory, we should allocate for neighbour table while deploying the Max-Min. We set the size of neigbour tbale to 12.

Case 1: 12 nodes including BS It may happen over the time that a node inside a cluster may not receive some beacons of its CH and may trigger BEACON TIME OUT which will lead to the eviction of the CH from the parent table of the node. BEACON TIME OUT was 80 beacons. If in the last 80 beacons a node did not receive any beacon from its CH, it assumed that the CH died.

Each node sent 2 beacons per minute. In this case, we performed the simple routing via were available to join many CH.

Figure 7.10 also illustrates average number of phase messages required to complete the Max-Min phase were close to 280 per node. Therefore, to calculate weight and to complete the Max-Min phases, the higher the node density is, the higher is the number of phase packet requirement.

It may happen over the time that a node inside a cluster may not receive some beacons of its CH and may trigger BEACON TIME OUT which will lead to the eviction of the CH from the parent table of the node. In this case, we performed the simple routing via HybridLQI. Once, the CH was evicted, the hopcount between the nodes varied with time, as we used HybridLQI as the routing algorithm between the two clusters.

Lets further evaluate the performance of the Max-Min without any route maintenance, i.e., if Cluster Head is evicted from the routing table, the Max-Min should stop and new cluster formation should take place. For ease of analysis, in Figure 7.10, we are not updating the Clusterheads and the parents according to HybridLQI.

Max-Min Vs Matérn Hardcore Process

So far, we have seen that Max-Min has issues with node density which leads to increase in the memory requirement as well as prolonging the time to create the whole network. Now, we will discuss the MHP.

To begin with, lets discuss some of the difference between the Max-Min and MHP • First of all MHP does not need all the state of the network. In fact its work as binary, if one node is under the area of influence of one CH, it cannot declare itself as a CH.

Therefore, memory requirement is not at all dependent on the node density.

• In Max-Min due to the requirement of state of the network, Max-Min has to prolong the duration and number of phase packets as the node density of the network increases.

It has more to do with the fact that the nodes boot and enter phases at different time and they must receive the phase packets to compute the proper state of the network.

In case of the Mateérn Hardcore Process, nodes needs to send very few packets to propagate that they have changed their state from the CH to non-CH or from non-CH to CH. Sensors don't need to know how many nodes are in its vicinity. So, a short burst of special message packets is enough in MHP to propagate changes. As underlying CSMA/CA will make sure that the channel is available and rest of the nodes will be in the listening state.

• It makes route maintenance easy as well. As whenever there is BEACON TIME OUT, a node will declare itself as the CH and it will maintain the routing. Hence, MHP inherently does the cluster maintenance.

We have already seen that Max-Min due to its memory requirement may not perform at optimum level at larger network. In this subsection, we compare the performance of Max-Min with MHP in a 12 node network. So, it can be easily infered that Matérn Hardcore Process easily outperforms the Max-Min with respect to the ease of applicability and clustering. Mathematical model proves that even in the random network, MHP provides regular distribution of cluster heads which is the primary requirement of any clustering process.

Conclusion and Discussion

In this chapter, we have implemented Matérn Hardcore Process and Max-Min cluster heuristic on Tmote Sky sensors. These are among the two most important cluster formation techniques which can have wide applications in the sensor networks. In our work, we have used the default CSMA/CA implementation available in the TinyOS stack.

• Matérn Hard-Core process is less complicated as compared to Max-Min heuristic.

Code foot print of MHP is lower than that of Max-Min heuristic. One of the problems which Max-Min implementation faces is to have all the nodes in same phase at same time. Because of CSMA, each nodes send its phase messages at different time. To have nodes communicate in same phase, each phase is elongated and multiple phase messages are sent. MHP does not have synchronization problem. Hence, it can be said that MHP is natural process which can be used with CSMA. Also, TDMA is not scalable, hence we have not tried to implement MaxMin heuristic with TDMA.

However, it will be interesting to do that in future.

• In MaxMin Heuristic, each node has to exchange information with its neighbors. This requires exchange of packets. But in Matérn Hard-Core Process no such exchange of information is required. Each node either join a cluster on receiving beacons from clusterheads or become clusterhead if they are not in area of influence of other clusterhead. In case of conflict, the nodes decide locally among themselves and nodes which become un-connected due to conflict then join other cluster. Hence, we can say that clusterization is faster and overhead is low in MHP.

• In MaxMin Heuristic, each node stores information about its neighbors in its neighbor table. This information is required during clustering. But because sensors have limited memory, it might be the case that complete information cannot be stored. This may result in false calculations and number of singleton clusters may increase significantly. But in MHP, no memory is required for clustering. Hence, we conclude that memory requirement is low for MHP process relative to Max-Min heuristic. Also,

INTRODUCTION 133

[84] and [START_REF] Scott | Routing and channel assignment for low power transmission in pcs[END_REF], address the problem of minimizing the total consumed energy to reach the destination. In [START_REF] Rahul | Energy aware routing for low energy ad hoc sensor networks[END_REF], authors proposed energy aware routing where localized flooding are used for the route maintenance. However, the solution was too specific to a very stable wireless channel, which cannot be the case in the real world. In [START_REF] Bouabdallah | Load-balanced routing scheme for energy-efficient wireless sensor networks[END_REF], authors show that distributing the traffic generated by each sensor node through multiple paths instead of using a single path allows energy savings. In real deployment, routes quality keeps on changing and so are the paths. This chapter will show the drawback of these kind of approach when the links are not reliable. In case of geographic routing, nodes usually employ a greedy forwarding mechanism where each node forwards a packet to the neighbour that is closest to the destination. [START_REF] Fyffe | Traffic-adapted load balancing in sensor networks employing geographic routing[END_REF], proposes geographic routing based load balancing schemes.

The main objective in this work is also to check the load balancing schemes for the cold chain process. Inside a cold storage warehouse, each pallet (containing frozen items) can be equipped with a temperature sensor. Random shipment of pallets makes the use of geographical based routing almost impossible. In addition, having carrier sense as the MAC layer protocol has its own complexities ( [START_REF] Jamieson | Understanding the Real-World Performance of Carrier Sense[END_REF]). [START_REF] Toumpis | Load balancing in wireless sensor networks using kirchhoff's voltage law[END_REF] assumes that network is sufficiently connected.

To Figure 8.1 shows the distribution of LQI over distance as a function of transmission power. While at higher power level LQI has good confidence interval, at lower transmission level its readings are rather unreliable. Therefore, LQI instantaneous value can be used to emulate a network having varying radio links.

While at higher power level LQI has good confidence interval but at lower transmission level its reading are rather unreliable. Therefore, LQI instantaneous value can be used to emulate network having varying radio links.

Arbutus [START_REF] Puccinelli | Arbutus: Network-layer load balancing for wireless sensor networks[END_REF], implements load balancing on the real sensors. It employs blacklisting to iron out the asymmetric links but with very careful calibration which may be applicable to whole range of networks. Diallo et al. in [START_REF] Diallo | Hlink quality and local load balancing routing mechanisms in wireless sensor networks[END_REF] have shown if the network links stabilizes under some conditions, LQI based routing scheme can be a way forward to improve the network performance.

Retransmission

In real sensor networks, links are unreliable. Therefore, retransmission is necessary. Definition In an absorbing Markov chain, a state which is not absorbing is called transient.

, R 1 , R 2 , R 3 , R 4 , R 5 and
absorbing states S , L can be presented as:

P = R 0 R 1 R 2 R 3 R 4 R 5 S L                   R 0 R 1 R 2 R 3 R 4 R 5 S L 0 1 -l 2 1 0 0 0 0 l 2 1 0 0 0 1 -l 2 2 0 0 0 l 2 2 0 0 0 0 1 -l 2 3 0 0 l 2 3 0 0 0 0 0 1 -l 2 4 0 l 2 4 0 0 0 0 0 0 1 -l 2 5 l 2 5 0 0 0 0 0 0 0 l 2 6 1 -l 2 6 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1                  
For the states R 0 , R 1 , R 2 , R 3 and R 4 it is possible to reach state S and from the state R 5 it is possible to reach both S or L.

A Markov chain with r absorbing states and t transition states in its canonical form can be given as:

P = T R. ABS.     T R. ABS. Q tXt R tXr 0 rXt I rXr    
where, I is an r-by-r identity matrix, 0 is an r-by-t zero matrix, R is a nonzero t-by-r matrix, and Q is an t-by-t matrix.

P n = T R. ABS.     T R. ABS. Q n ⊛ 0 I    
In Markovian process, entry p

(n) ij of the matrix P n is the probability of being in the state s j in n steps if the starting state was s i . Further, as from each transient state an absorbing state can be reached, therefore, as n approachs infinity; Q n must approaches zero. Now question arises, how to find the long term probabilities for entering each of the absorbing states.

For an absorbing Markov chain the matrix I -Q has an inverse N and N = I+Q+Q 2 +..... The ij entry n ij of the matrix N is the expected number of times the chain is in state s ij , given that it starts in state s j . The initial state is counted if i = j.

Now,

Q =              0 1 -l 2 1 0 0 0 0 0 0 1 -l 2 2 0 0 0 0 0 0 1 -l 2 3 0 0 0 0 0 0 1 -l 2 4 0 0 0 0 0 0 1 -l 2
For the case, i.e., links with high probability of the success and symmetric links/routes, where l 1 = l 2 =l 3 =l 4 =l 5 =0.9 the matrix T can be given as:-

T = R 0 R 1 R 2 R 3 R 4 R 5                 R 0 R 1 R 2 R 3 R 4 R 5 1 -.19 0 0 0 0 0 1 -.19 0 0 0 0 0 1 -.19 0 0 0 0 0 1 -.19 0 0 0 0 0 1 -. 19
0 0 0 0 0 1                 T -1 = R 0 R 1 R 2 R 3 R 4 R 5                 R 0 R 1 R 2 R 3 R 4 R 5 1
0 0 0 0 0 1                
So, for a link with 90% success probability, 0.1900, 0.0361, 0.0069, 0.0013, 0.0002 are the expected number of times that the node will be in states

R 1 , R 2 , R 3 , R 4 , R 5
respectively.

Theorem 8.2.1 Let b ij be the probability that an absorbing chain will be absorbed in the absorbing state s j if it starts in the transient state s i . Let B be the matrix with the entries b ij . then B is an t-by-r matrix and B=NR, where N is the fundamental matrix and R is in the canonical form.

So,

B = R 0 R 1 R 2 R 3 R 4 R 5                 S L 0

LoadBalancing

In this section, we discuss the load balancing model. Figure 8.5 shows sender having three different routes to reach the BS. In case of load balancing, if λ is the total rate, it will be divided equally between the three different routes via R 1 , R 2 and R 3 . Similarly, if the acknowledgement fails on any of these routes, the node will re-route its packet via another route. And after 5 retransmission attempts the packet will be dropped. Else, the packet has been successfully delivered.

Figure 8.5 shows a load balancing model where a node sends its packet to three different nodes in the round robin fashion. P 0 , P 1 and P 2 are the probabilities that the packet transmission will fail over that link (with Ack).

In case of load balancing, the main objective is to increase the lifetime of the network by partitioning the load between the immediate neighbours. However, when the links/routes are asymmetric or unreliable, load balancing should be applied very carefully.

Let us discuss how links unreliability may affect the network. So, lets consider a scenario where different routes are used by a node i to reach node j with each route having different packet delivery ratio.

From 8.2.1, we construct a transition matrix which is used to calculate the num- 142 In the previous section, we have seen via Absorbing Markov chain the impact of the links having different packet success probabilities.

T -1 = R 0 R 1 R 2 R 3 R 4 R 5             

Experimental Results

To verify the above hypothesis, we deploy MultihopLQI [5], HybridLQI [START_REF] Gupta | Hybridlqi: Hybrid multihoplqi for improving asymmetric links in wireless sensor networks[END_REF] and Round-Robin(based on MultihopLQI). Table 8.1 lists the parameters of the experiments.

Algorithms are implemented in the following manner:-1. For all the algorithms, whenever any beacon arrives, its LQI based cost is checked and parent table is updated, if necessary.

2. In case of Round-robin, to choose current parent, 1st least cost node is selected and message is sent to it. For next message, 2nd least cost parent is selected and finally, message is sent to 3rd least cost parent. And then again next message to 1st least cost parent. In step-2, implementation does not wait for the acknowledgment packet but keeps on sending data to top 3 in neighbour table.

3. In case of Round-Robin,If the timer for the Ack is gone, i.e., its acknowledgement is not received then message is retried again. However, to whom it was sent first is not taken into account (we do not need to, as parents are continuously changing). For delivery purposes, there is no discrimination between the messages being sent for the first time or being retransmitted. The parent is selected as per the pointer to the parent list.

In case of MultihopLQI, the parent is not changed till the acknowledgement fails.

In case of HybridLQI, the parent is not changed without taking into account the Packet Loss Percentage and other factors. 4. After 5 retransmission attempts packet will be dropped. If the packet is transmitted successfully within these 5 attempts, it is not considered in packet loss computation.

Average number of hops

As the transmission power of nodes decreases their hop count to reach BS increases as shown in Figure8.7. Round-Robin has higher hop-count than the other algorithms as it does not use the optimum route to the BS. It is obliged to send packets over different routes.

Packet Reception

So, as the number of hops increases, in case of Round-Robin algorithm, the probability of using links with lower packet rate increases. Figure 8.8 illustrates that as the At 0 dBm, nodes transmit at highest power and they can communicate directly with the BS. Therefore, for Round-Robin, MultihopLQI and HybridLQI the packet reception is close to 95%. Since, Round-Robin and MultihopLQI in no-retransmission implementation do not retransmit, they have lower packet reception vis-a-vis the other algorithms.

At -5 dBm, there is not much change in the packet reception as the deployment area is small (430 m 2 ). Therefore, most of the nodes can communicate directly with the BS. Hence, very low losses for these algorithms.

At -11 dBm, links become less reliable and Round-Robin (load balancing) has higher packet losses than the MultihopLQI or HybridLQI.

At -20 dBm, the average packet reception of the Round-Robin (load balancing) drops to 80% while for the MultihopLQI and HybridLQI packet reception is close to 90%.

Even when no retransmission is used at -20 dBm, average packet reception of the Round-Robin is 35% while for MultihopLQI it is over 50%.

Conclusion

To increase the network lifetime, load balancing has been a hot topic of research in sensor networks. However, very few test bed implementations have been done. In fact Artubus is the only implementation for the load balancing. Even in this case, the network has to be carefully calibrated. In this chapter, initially we use Absorbing Markov chain to model retransmissions in sensor network. Then, we apply similar approach to model the load balancing in the sensor networks. We show that routes having different packet success probabilities can affect the performance of the sensor network and successful packet delivery can drop from 98% to 16%.

Later, we deploy 30 motes in grid configuration(5x6) and implement three different algorithms (MultihopLQI, Hybrid MultihopLQI and Round Robin-Load Balancing) with retransmission mode. We also implement MultihopLQI and Round Robin-Load Balancing without retransmission. Then, we show that at higher transmission power level, since the link packet delivery is higher; all the three algorithms have equal packet reception.

In these conditions, load balancing techniques can be applied. However, as we reduce the transmission power of the nodes, the hopcount of the nodes to connect with the BS increases. So, when the Round Robin algorithm is applied at lower power levels, its performance in terms of packet delivery degrades. At -20 dBm transmission power level, the packet loss of the Round Robin -Load balancing with retransmissions (20%) is twice that of other non-load balancing algorithms (10%). When no retransmission at -20 dBm packet delivery of MultihopLQI is 55% while that of Round Robin-Load balancing is 45%.

The measurements results allow us to quantify that when links/routes are not symmetrical over the networks, which is the case in the real world, the load balancing techniques should be applied very carefully. Now, we can answer that load balancing schemes cannot be applied generically.

What we observe is not nature itself, but nature exposed to our method of questioning.

Werner Heisenberg

Chapter 9

Conclusion

The design of the sensor network is a very complicated process. Results obtained via simulation studies are difficult to implement in real deployment. Packet delivery performance for a single-hop and a multihop network varies too much. These results suggest that a gap exists between research algorithms and their performance in real deployments.

Due to its resource constraints, low power wireless sensor networks face several technical challenges. However, they still have to maintain the quality of service requirement such as minimum losses, packet delivery rate, throughput, etc. Besides the physical hardware there are several other issues which affect the sensor network performances such as protocol mismatch, buffer overflow in the sensors and asynchronous nature of the underlying protocol stack.

Many protocols work well on simulators but do not act as we expect in the actual deployments. Sensors placed at the top experience Free Space propagation model, while the sensors which are at the bottom have sharp fading channel characteristics. Propagation effects such as shadowing, path loss and multipath fading add further complications in the field of protocol design.

One of the approaches to improve the performance of the sensor network is to add some powerful nodes in the network. In this way, the ZigBee proposes two types of network devices; FFD-Fully functional Device and RFD-Reduce functional devices. The motivation for having these types of devices is to have RFD cluster around the FFD and let FFD which are more powerful to do the necessary calculations and routing. However in Chapter 3, we 149 show that these kinds of networks are only feasible for the static networks. We have shown that in the mobile heterogeneous (networks with FFD and RFD) sensor networks, due to phenomenon orphaning and high cost of route discovery and maintenance, the performance of the network degrades with respect to the homogeneous network. The performance of the system worsens as the number of hops between the node and the base station increased.

Link estimation is essential for efficient routing. LQI is one such link estimation on which MultihopLQI (Multihop Link Quality Indicator) algorithm is based. Chapter 4 does the primary empirical analysis of the link quality indicator where we deploy sensors in various configurations. With these experiences, we show LQI time-varying and some random disturbances due to external phenomena and physical changes. It is very important to study these issues, as sensors may not be in steady state deployment. We empirically prove that a high power node creates a natural single hop cluster. We used these observations and experiences to conduct further experiments. Using these results and we illustrate in Chapter 5 that if we have enough number of high power nodes (i.e., nodes with higher transmission power than its peers) these high power nodes can act as the back bone and improve the packet delivery over the network.

In Chapter 5, we also show that how asymmetrical links may have the detrimental effect on the packet reception. One of the ways to improve the packet reception is to add some high power nodes in the network. However, we have already seen in Chapter 3, if there is mobility in the system, high power nodes may not be that much useful. So, we need further solutions. In algorithm, the inbuilt assumption is that the uplink (the link from the child to its parent) and the downlink (link from the parent to its child) are symmetric. Since, MultihopLQI is the beacon based system by assuming that the links are symmetric, a node needs to broadcast a single beacon thus avoiding the two way handshake. In this way beacon messages are reduced. So, we propose HybridLQI algorithm in Chapter 6 which estimates downlink via from the received beacon. On the other hand, acknowledgments are implemented (and necessary because of the dynamic nature of the routes, which makes it impossible to use negative acknowledgements). We propose the use of this acknowledgment (Link Layer feedback mechanism) based link estimation to measure the uplink channel quality. In this way without adding any control overhead the veracity of the LQI can be verified. Also, as the size of the beacon and the data packet is different, we cannot fully rely on the LQI of the packet. We empirically(up to 50 nodes) show that by applying HybridLQI approach, we have been able to reduce the packet loss percentage by up to 15 -20% in the dense network and by up to 350% for the node which is three hop away from the BS.

In chapter 7, we implement two clustering schemes to form clusters on real sensors.

We deployed Max-Min cluster heuristic and Matérn Hardcore process on both sparse and dense network. We have shown that the cluster formation via Matérn Hardcore process comprehensively outperforms Max-Min cluster heuristic in both types of networks. Max-Min cluster heuristic's memory requirement is linearly related to the size of the neighbours.

We also illustrate that the denser the network is, the higher is the memory requirement. We also show that the Max-Min cluster heuristic requires the total state of the d hop neighbours which increases the initialization time for the network as nodes boot at random time and clock synchronization is not possible. On both counts, Matérn Hardcore process easily beats Max-Min. Matérn Hardcore process doesn't have any memory requirement related to the size of the network. Also, its initialization does not depend on the knowledge of the local topology. A node just needs to know whether it is under the zone of clusterhead or not. We also show that the cluster maintenance is done inherently in the Matérn Hardcore process.

In case of the Max-Min, we have to rerun the algorithm.

In Chapter 8, we implement load balancing to partition the flow of data. Artubus is the only implementation for the load balancing. Even in this case, the network has to be carefully calibrated. Also, authors are silent on the heuristic of the load factor. We use Absorbing Markov chain to model retransmissions in sensor network. Then, we apply similar approach to model the load balancing in the sensor networks. Then, we deployed motes with MultihopLQI, HybridLQI and Round Robin algorithm. We empirically quantify that when links are not symmetrical over the networks, which is the case in the real world, the load balancing techniques can have the adverse effect on the performance of the sensor network. Now, we can answer that load balancing schemes cannot be applied generically. Actually, the algorithms such as HybridLQI by keeping the state of the immediate neighbours (only 3-5 are required), a node can change its neighbor which can have better links rather than blindly following the load balancing strategy. Also, load balancing is inherently performed by such types of algorithm as the next hop neighbor is changing based on the link layer acknowledgement failure. 9.1. FUTURE DIRECTIONS 151 9.1 Future Directions "Que Sera Sera(Whatever Will Be,Will Be) -Alfred Hitchcock's-The Man Who Knew Too Much(1956) " Link estimation, neighbour table management and cost metrics are key to the success of sensor networks. In the simulation studies, either researchers assume that the nodes are location aware or they take averages of the link quality between several nodes (which is also an unreasonable assumption as link quality is the property of a node pair), so the use of beacons becomes imminent in real implementation of WSN to know the state of the network.

By applying the routing metrics, bottlenecks of the network can be detected.

Then, researchers can use our load balancing model to perform intelligent load balancing by partitioning the network and apply different load balancing techniques.

In literature, researchers use the term degree of connectivity but they never explain what their parameters are. We have used threshold LQI to calculate degree of connectivity.

And then, we use it to create clusters. Packet reception rate between the nodes can also be one of the criteria. Use of these metrics can be further explored.

We are in process of documenting our TinyOS-1.x implementation on clustering.

We have tried to make our code as generic as possible. Very soon, we will make Max-Min cluster formation Heuristic's and Matérn Hardcore Process's code available online. For the moment, the code can be made available on request. This code can be easily modified to do all sorts of clustering operations.

4. 1

 1 Straight-line (a) and Grid (b) deployment. . . . . . . . . . . . . . . . . . . . 4.2 Front and Back of the Tmote Sky module . . . . . . . . . . . . . . . . . . . 4.3 Topology-Scenario1, BS TPL=31, node TPL=25 . . . . . . . . . . . . . . . 4.4 LQI of the Beacons Received from the BS at different sensors, BS TPL=31, node TPL=25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Topology-Scenario-2, BS TPL=31, node TPL=25 . . . . . . . . . . . . . . . 4.6 LQI of the Beacons Received from the BS, BS TPL=31, node TPL=25 . . 4.7 Topology-Scenario-3, BS TPL=25, node TPL=25 . . . . . . . . . . . . . . . 4.8 LQI of the Beacons Received from the BS, BS TPL=25, node TPL=25 . . 4.9 Topology-Scenario-4, BS TPL=25, node TPL=25 . . . . . . . . . . . . . . . LIST OF FIGURES xv 4.10 Scenario-4, LQI of the Beacons Received from the BS, BS TPL=25, node TPL=25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Topology-Scenario-5, BS TPL= 31, node TPL =25 . . . . . . . . . . . . . . 4.12 Scenario-5,LQI of the Beacons Received from the BS, BS TPL= 31, node TPL =25. Here, we place last node behind a wall and hence node could not receive beacon from the BS. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.13 Topology-Scenario-6, BS TPL= 31, node TPL =25 . . . . . . . . . . . . . . 4.14 Scenario-6-LQI of the Beacons Received from the BS, BS TPL= 31, node TPL =25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.15 Random movement of People caused topology change, Topology-Scenario-7, BS TPL= 20, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . 4.16 LQI of the Beacons Received from the BS Scenario 7, BS TPL= 20, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.17 Topology-Scenario-8, BS TPL= 31, node TPL =20 . . . . . . . . . . . . . . 4.18 LQI of the Beacons Received from the BS, Scenario 8, BS TPL= 20, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.19 LQI of the Beacons Received from the BS-Scenario 9, BS TPL= 20, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.20 LQI of the Beacons Received from the BS-Scenario 10, BS TPL= 20, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.21 LQI of the Beacons Received from the BS-Scenario 11, BS TPL= 31, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.22 LQI of the Beacons Received from the BS-Scenario 12, BS TPL= 31, node TPL =20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.23 LQI of the Beacons Received from the BS, Scenario 13, BS TPL= 15, node TPL =15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.24 LQI of the Beacons Received from the BS, Scenario 14, BS TPL= 15, node TPL =15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.25 LQI of the Beacons Received from the BS, Scenario 15, BS TPL= 15, node TPL =15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.26 LQI of the Beacons Received from the BS, Scenario 16, BS TPL= 31, node TPL =15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.27 LQI of the Beacons Received from the BS, Scenario 17, BS TPL= 31, node TPL =15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.28 LQI of the Beacons Received from the BS, Scenario 18, BS TPL= 31, node TPL =15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.29 Topology, Scenario 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.30 LQI of the Beacons Received from the BS, (a) Scenario 19 (b) Scenario 21 (c) Scenario 23. BS TPL= 10, node TPL =10 . . . . . . . . . . . . . . . . 4.31 LQI of the Beacons Received from the BS, (a) Scenario 20 (b) Scenario 22. BS TPL= 31, node TPL =10 . . . . . . . . . . . . . . . . . . . . . . . . . . 4.32 LQI of the Beacons Received from the BS, (a) Scenario 24 (b) Scenario 26 (c) Scenario 28. BS TPL= 31, node TPL =5 . . . . . . . . . . . . . . . . . LIST OF FIGURES xvi 4.33 LQI of the Beacons Received from the BS, (a) Scenario 25 (b) Scenario 27 (c) Scenario 29. BS TPL= 5, node TPL =5 . . . . . . . . . . . . . . . . . . 4.34 Real time evolution of LQI. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.35 Impact of position of Base Station. . . . . . . . . . . . . . . . . . . . . . . . 4.36 Impact of high power of Base Station. . . . . . . . . . . . . . . . . . . . . . 4.37 LQI variation with time, scenario 33. . . . . . . . . . . . . . . . . . . . . . . 4.38 BS transmission power effects. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.39 Average number of hops. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.40 Number of multi-hop routes. . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 A typical Warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Sensor plugged inside a Pallete . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Grid Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Message Receive Percentage for different nodes placed in a 2 meter wide corridor open to public in three different scenarios. BS TPL= 31 in all the cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Message Receive Percentage for different nodes placed in a 2 meter wide corridor open to public. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Message Losses in different deployment surroundings . . . . . . . . . . . . 5.7 Comparison of Message Loss Percentage when nodes are placed on the Floor Vs placed on the Table, BS TPL =3 and Node TPL=10 . . . . . . . . . . . 5.8 Variation of Message Lost Percentages,Addition of HP nodes stabilizes network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 LQI of the BS received by the 6 different nodes, when Base Station TPL = 0 dbm and -20 dbm.

3. 1

 1 Simulation Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 General Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Heterogeneous network parameters . . . . . . . . . . . . . . . . . . . . . . . 4.1 Scenario Description-First Set . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Scenario Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Grid Scenario Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Emulating RFD and FFD in real time . . . . . . . . . . . . . . . . . . . . . 5.1 Scenario Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Routing Table of Node A . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Experimental Parameters for Dense Network . . . . . . . . . . . . . . . . . 6.3 Dense Network Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Experimental Parameters for Sparse Network . . . . . . . . . . . . . . . . . 6.5 Sparse Network Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Deployment Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 Experimental Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 TPL to dbm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Layered Messages

Figure 1 .

 1 Figure 1.1 shows a typical sensor network, where Data or Beacon messages are encapsulated into Multihop Message. These multihop messages are then fit into the TinyOS messages and sent over the radio to the next hop. Usually, beacon message Time to live (TTL) is 1 and the Data message TTL is equal to the hopcount of the sending node.

Figure 2 .

 2 1(a) and Figure 2.1(b) show the signal strength and respective packet reception over four directions. The results show that the overdependence on the simulation has its own limitations.

  (a) Signal Strength over time in Four Direction. (b) Non-Isotropic Packet Reception

Figure 2 . 1 :

 21 Figure 2.1: Radio Irregularity Reality [101].

Figure 2 . 2 :Figure 2 .

 222 Figure 2.2: Schematic view of the data packet [1]

Figure 2 . 3 :

 23 Figure 2.3: Modulator [1]

Figure 2 .

 2 Figure 2.3 shows at which point the data LQI values are calculated.

Figure 2 . 4 :

 24 Figure 2.4: Typical Sensor

2. 6 . 1

 61 Coexistence between Zigbee, Wi-Fi and Bluetooth 802.15.4 has 16 non-overlapping channels separated by 5 Mhz. Wi-Fi, Bluetooth and Zigbee all operates on 2.4 GHz. Figure 2.5 shows the overlapping Wi-Fi and Zigbee

Figure 2 . 5 :

 25 Figure 2.5: LR-WPAN vs Non-Overlapping WLAN Channel Allocations

Figure 2 . 6 :Figure 2 .

 262 Figure 2.6: Sensornet

Figure 2 .

 2 7 shows the flowchart of the MultihopLQI algorithm.

Figure 2 . 7 :

 27 Figure 2.7: MultihopLQI

  Correlate LQI, The higher the value of the LQI is lower is the cost of //reaching the node uint16_t correlation(uint8_t v) { uint16_t c = (80 -(v -40)); c = (((c * c) >> 3) * c) >> 3; return c; // Received Beacon? //update parent cost parents[i].cost = _bmsg->cost; // get cost of from the beacon message parents[i].estimate = (parents[i].estimate) + correlation(_msg->lqi) ; // compute total cost to connect with BS parents

Figure 2 .

 2 Figure 2.8(a) illustrates ([91]) that the Packet Reception Rate (PRR) does not drop linearly. Similarly, we used the Estimated Cost (EC) function from the MultihopLQI as it also gives the non-linear curve and for the high values of LQI, the EC cost is quite low (Figure 2.8(c)). MultihopLQI chooses routes with lowest Total EC. However, EC function encourages nodes to communicate over shorter routes to minimize the EC as shown inFigure 2.8(b). Here, node A will connect directly with the base node.

Figure 2 . 8 :

 28 Figure 2.8: LQI and the Estimated Cost Relationship

  (a) Neigbour table (b) Arrival of new beacon from node A (c) Acknowledgement fails (d) Arrival of new beacon from node A (e) BEACON TIME OUT, node A is evicted

Figure 2 . 9 :

 29 Figure 2.9: Neighbour table management

Figure 2 .

 2 Figure 2.10: Delta Application configuration. Direction of arrows indicates interface provider/user relationships NOT data flow direction.

Figure 2 .

 2 Figure 2.11: MultiHopRouter configuration. Direction of arrows indicates interface provider/user relationships NOT data flow direction.

Figure 3 . 1 :

 31 Figure 3.1: ZigBee Network Topology Models

  Network Simulator 2 (NS2) [10] is used to simulate the environment. It is an open-source object oriented discrete-event simulator for Network research. The simulator is written in programming C++ with and OTcl (Object Tool Command Language) interpreter used as the command interface. The C++ part constitutes the core if the simulator, where detailed protocol is implemented. On the other hand, the OTcl is used primarily for simulation configuration. Therefore, to analyze the existing protocols the only prerequisite is the knowledge of OTcl. The knowledge of C++ is useful while implementing new protocols or developing the new models.

Figure 3 .

 3 Figure3.2 shows a tree structure comprised of RFD and FFD nodes. We use the similar architecture to construct our network topologies. The RFD nodes will connect with FFD nodes. LEACH algorithm is used in principle to select the Cluster Head and the following changes are made in implementation of LEACH algorithm[START_REF]Network simulator 2 leach implementation[END_REF] in the Network Simulator (NS2).

Figure 3 .

 3 Figure 3.2: Network Model

Figure 3 . 4 :

 34 Figure 3.3: Messages

Figure 3 . 5 :

 35 Figure 3.5: Nodes alive in the network

  It is remarkable that a science which began with the consideration of games of chance should have become the most important object of human knowledge. Théorie Analytique des Probabilitiés (1812). Pierre-Simon Laplace Chapter 4 Experimental Study: Link quality and Deployment issues in Sensor network Last chapter illustrates that Fully Functional Devices should be used in wireless sensor networks. Once the choice of selection of node is made, it is imperative to understand the issues related to the deployment of real sensor networks. This chapter does the preliminary analysis of the Link Quality Indicator between the nodes. 1 This chapter will show how the simulation studies fail to capture the real time issues in the sensor networks. The chapter discusses the deployment experiences by the real sensor network. Principle reason where simulators fail is to capture the uneven nature of network topology. Some nodes may have free space propagation model while some might have different wave propagation model. E.g., a network where few nodes are on the ground

  [START_REF] Wahba | An empirical evaluation of embedded link quality[END_REF], Wahba et al. used two motes and evaluated link quality over distance and various power levels. Polastre et al.[START_REF] Polastre | Telos: enabling ultra-low power wireless research[END_REF] presented preliminary evaluation results for Telos motes (based on CC2420) and suggested that the average LQI was a better indicator of packet reception rate (PRR).

  have conducted 45 different scenarios and have recorded observations for more than 900 minutes (grand total of all scenarios) per sensor. All these scenarios are different either in terms of number of nodes, distance between the nodes, transmission power level of nodes, transmission power level of Base Station (BS) or finally, in terms of topology i.e. straight-line/grid (Figure 4.1). Initially, the experiments are conducted outdoors and later indoors. The experiments are performed at different power levels.

Figure 4 . 1 :

 41 Figure 4.1: Straight-line (a) and Grid (b) deployment.

Figure 4 . 2 :

 42 Figure 4.2: Front and Back of the Tmote Sky module

  BS, Distance = 1.5m, in Straightline B 6 nodes + BS, Distance = 3m, in Straightline C 6 nodes + BS, Distance = 4.5m, in Straightline D 12 nodes + BS, Distance = 4m, Grid 3x6 E 25 nodes + BS, Distance = 6m, Grid 5x5

Figure 4 . 3 :Scenario 1

 431 Figure 4.3: Topology-Scenario1, BS TPL=31, node TPL=25

Figure 4 .

 4 Figure 4.4 shows the LQI of the BS's beacons received by the nodes. The higher values for the confidence interval indicate the perturbation at the physical channel. The average

Figure 4 . 4 :Figure 4 . 5 :Scenario 2

 44452 Figure 4.4: LQI of the Beacons Received from the BS at different sensors, BS TPL=31, node TPL=25

Figure 4 .

 4 Figure 4.5 shows the topology. The sensor acting as BS is connected to Laptop.Figure 4.6

Figure 4 . 6 shows

 46 Figure 4.5 shows the topology. The sensor acting as BS is connected to Laptop.Figure 4.6 shows the LQI of the BS's beacons received by the nodes. The high variation in LQI is due to the constant movement of people around the deployed area. On the positive side, the results confirm LQI values of around 105 for the distance up to 30m.

Figure 4 . 6 :Figure 4 . 7 :Scenario 3

 46473 Figure 4.6: LQI of the Beacons Received from the BS, BS TPL=31, node TPL=25

Figure 4 . 57 Figure 4 . 8 :Scenario 5

 457485 Figure 4.8: LQI of the Beacons Received from the BS, BS TPL=25, node TPL=25

Figure 4 .

 4 Figure 4.12, shows that the sensors can receive Beacons from the BS but they can't communicate with the BS. It is a classical example of a cold chain warehouse where BS is

Figure 4 .Figure 4 .Figure 4 . 12 :

 44412 Figure 4.10: Scenario-4, LQI of the Beacons Received from the BS, BS TPL=25, node TPL=25

4. 6 . INDOOR DEPLOYMENT 59 Figure 4 . 13 :Figure 4 .Scenario 6

 65941346 Figure 4.13: Topology-Scenario-6, BS TPL= 31, node TPL =25

4. 6 . INDOOR DEPLOYMENT 60 Scenario 7

 6607 In this scenario, the transmission power of the sensors is set at TPL= 20 and altogether there are 12 sensors including BS and each being separated by 3 meters. Due to random movement of people in and around the deployment area the LQI values vary between sensor nodes and the BS with distance. This change induces the variation in topology of the network.

Figure 4 . 15 :

 415 Figure 4.15: Random movement of People caused topology change, Topology-Scenario-7, BS TPL= 20, node TPL =20

Figure 4 .Figure 4 . 17 :Scenario 8 Scenario 9

 441789 Figure 4.16: LQI of the Beacons Received from the BS Scenario 7, BS TPL= 20, node TPL =20

Figure 4 .

 4 [START_REF]Zigbee Specification V1[END_REF] shows the LQI value of the BS received by other nodes. Scenario 10 Figure 4.20 shows the LQI of the beacons received by different nodes, positioned at 9 meters apart in a straight line. It is an homogeneous network, with both BS

Figure 4 . 18 :Figure 4 . 19 : 63 Figure 4 . 20 :Scenario 12 Figure 4 .

 41841963420124 Figure 4.18: LQI of the Beacons Received from the BS, Scenario 8, BS TPL= 20, node TPL =20

Figure 4 . 23 ,

 423 Figure 4.24, Figure 4.25, shows the LQI of the BS beacons received by different nodes in the Scenario 13, 14 and 15 respectively.

Figure 4 . 21 :Figure 4 . 22 :Figure 4 . 23 :Figure 4 . 24 :Figure 4 . 25 :

 421422423424425 Figure 4.21: LQI of the Beacons Received from the BS-Scenario 11, BS TPL= 31, node TPL =20

Scenario 16 , 17 Scenario 18 Figure 4 .

 1617184 In both case, the BS transmits at 31 TPL and other nodes are deployed at 15 TPL. Therefore, the scenarios exhibit heterogenous network, like in case of the cold chain warehouse. For most of the time, for the distance of up to 25 meters from the BS, the LQI of the BS beacons remains within the range of 104. The results (Figure 4.25 and Figure 4.26) confirm the values as in Scenarios1,2,5,6,8,11,12.Uncertainty Region, the Scenarios1,2,5,6,8,11,12,16,17 also confirm the existence of the region where LQI varies a lot. 28 shows the LQI distribution of the BS beacons received at different sensors. Figure4.29 shows the topology of the network. Since the BS transmits at very high TPL than the other nodes, the senors try to connect directly with the BS (Figure4.29). The next section discusses this affect.

Figure 4 . 26 :Figure 4 . 27 :Figure 4 . 28 :Figure 4

 4264274284 Figure 4.26: LQI of the Beacons Received from the BS, Scenario 16, BS TPL= 31, node TPL =15

Figure 4 .

 4 30(a), Figure 4.30(b) and Figure 4.30(c) shows the LQI for the Scenario 19, 21 and 23 respectively.

Figure 4 . 30 :

 430 Figure 4.30: LQI of the Beacons Received from the BS, (a) Scenario 19 (b) Scenario 21 (c) Scenario 23. BS TPL= 10, node TPL =10

Figure 4 .

 4 Figure 4.31: LQI of the Beacons Received from the BS, (a) Scenario 20 (b) Scenario 22. BS TPL= 31, node TPL =10

Scenario 25 , 27 , 29 Figure 4 .

 2527294 33(a),Figure 4.33(b) and Figure 4.33(c) also confirm that in the sparse network, the deployment configuration does not affect the LQI behaviour.

Figure 4 . 32 :

 432 Figure 4.32: LQI of the Beacons Received from the BS, (a) Scenario 24 (b) Scenario 26 (c) Scenario 28. BS TPL= 31, node TPL =5

Figure 4 . 33 :

 433 Figure 4.33: LQI of the Beacons Received from the BS, (a) Scenario 25 (b) Scenario 27 (c) Scenario 29. BS TPL= 5, node TPL =5

Figure 4 .

 4 [START_REF] Delye | Correction, generalisation and validation of the "max-min d-cluster formation heuristic[END_REF] presents the LQI values between various sensors and the BS. We have observed that troughs in the graph suggests discontinuity in the network and shaper troughs in LQI reading lead to disruption of communication channel/link. Furthermore, positioning of the BS can have a subtle effect on the performance of BS. Also, all the nodes are placed on the floor next to wall. We have run this scenario for over 1200 seconds. Even though, there are another 6 nodes (excluding

Figure 4 . 34 :

 434 Figure 4.34: Real time evolution of LQI.

Figure 4 . 35 :

 435 Figure 4.35: Impact of position of Base Station.

  ( BS:31,Sn:5)Distance from BS= 6m Scn: 26 ( BS:31,Sn:5)Distance from BS= 18m Scn: 27 ( BS:5,Sn:5)Distance from BS= 6m Scn: 27 ( BS:5,Sn:5)Distance from BS= 18m

Figure 4 . 36 :

 436 Figure 4.36: Impact of high power of Base Station.

Figure 4 . 37 :

 437 Figure 4.37: LQI variation with time, scenario 33.

Figure 4 .

 4 38(a),Figure 4.38(b) and Figure 4.38(c), we analyze the results of these tests according to three distinct cases. The first case, when the Base

Figure 4 . 38 :

 438 Figure 4.38: BS transmission power effects.

Figure 4 . 39 :Figure 4 . 40 :

 439440 Figure 4.39: Average number of hops.

Figure 5 . 1 :

 51 Figure 5.1: A typical Warehouse

Figure 5 .

 5 Figure 5.3 shows the grid topology of the network.

Figure 5 . 4 :

 54 Figure 5.4: Message Receive Percentage for different nodes placed in a 2 meter wide corridor open to public in three different scenarios. BS TPL= 31 in all the cases.

Figure 5 .

 5 Figure 5.4 shows the Message Receive Percentage (MRP) for 6 different nodes with their respective distances from the BS (scenario1-29).For the ease of understanding, we

Figure 5 . 5 :

 55 Figure 5.5: Message Receive Percentage for different nodes placed in a 2 meter wide corridor open to public.

Figure 5 . 6 :

 56 Figure 5.6: Message Losses in different deployment surroundings

Figure 5 . 7 :Figure 5 . 8 :

 5758 Figure 5.7: Comparison of Message Loss Percentage when nodes are placed on the Floor Vs placed on the Table, BS TPL =3 and Node TPL=10

Figure 6 . 1 :Figure 6 . 1 .

 6161 Figure 6.1: LQI of the BS received by the 6 different nodes, when Base Station TPL = 0 dbm and -20 dbm. In both cases nodes transmit at -20 dbm

Figure 6 . 2 :

 62 Figure 6.2: Average number of hopcounts of the nodes from the BS when BS transmits at 0 dbm and -20 dbm. In both the cases, 6 other nodes transmit at -20 dbm

Figure 6 . 2 .

 62 Figure 6.2. shows the average number of hops needed by 6 different nodes to reach the BS. When the BS was at -20 dbm, the hopcount increases with distance. When BS

Figure 6 . 3 :

 63 Figure 6.3: Average number of hops from the Nodes to the BS, when nodes are deployed in 3x6 grid topology. In all the cases, 17 nodes transmit at -20 dbm.

Figure 6 . 4 :

 64 Figure 6.4: HybridLQI routing Algorithm

Figure 6 . 5 :

 65 Figure 6.5: Deployment Topology, where BS is the simple node, which is attached to the Laptop

Figure 6 . 6 :

 66 Figure 6.6: HybridLQI Vs MultihopLQI Losses at various Transmission Power Levels. 5x10 nodes (including BS) are deployed over 250 m 2 .

Figure 6 .

 6 Figure 6.6 compares the Average Loss Percentage over the whole network of both

Figure 6 . 7 :

 67 Figure 6.7: Message Receive Percentage of HybridLQI Vs MultihopLQI for 6 out of 7 nodes. Each node is separated by 6 meters. BS TPL= 0 dBm and Node TPL= -20 dBm.

Figure 6 . 8 :

 68 Figure 6.8: LQI of various nodes with node 24, when all nodes transmits at 0 dBm

Figure 7 .

 7 Figure 7.1 illustrate a typical clustering where final destination is the Base Station,

Figure 7 . 1 :

 71 Figure 7.1: A typical cluster

  real life, due to their small size, they have a number of limitations. Selecting the optimum sensors and wireless communications link requires knowledge of the application and problem definition. There are various design parameters which must be considered before undertaking the design of wireless sensor networks. A few such silent issues that must be examined are Network Size, Connectivity, Network Topology, User Traffic, Operational Environment, Energy Requirement, Performances Metrics and Cost. Some objectives of clustering are listed below:

  to a stationary Poisson Point process Φ b of intensity λ b . The point of Φ b are marked independently by random numbers uniformly distributed over (0,1). the dependent thinning retains the point x of Φ b with mark m(x) if the sphere b(x, h) contains no points of Φ b with

c = b d h d λ = 1 -

 1 exp(-λ b c) c (7.3) 7.2. BUILDING CLUSTERS 111 where λ is the intensity of the resulting point process or in other words the mean number of nodes which have become CHs, λ b is the intensity of the original point process or in other words the mean number of nodes inside that Boreal. λ will give us the lower bound of minimum number of HP nodes required under the condition that the network remains fully connected.

Figure 7 . 2 :

 72 Figure 7.2: CH positions after applying Matérn Hard core poisson Process. Parameters are: Intensity of the nodes λ =1000 and h =0.1. The side length of the square is one.

Figure 7 .

 7 Figure 7.2 shows the locations of cluster heads of sensors of distributed via Poisson

Figure 7 .

 7 Figure 7.4 illustrates the distribution of the CHs when thinning process based on

Figure 7 . 3 :

 73 Figure 7.3: Lower bound of number of CH required as a function of Coverage Radio Range of a Cluster Head. Number of nodes = 1000 distributed over a unit area.

Figure 7 . 4 :

 74 Figure 7.4: MHP in grid

Figure 7 . 5 :

 75 Figure 7.5: Matérn Algorithm

Figure 7 . 6 :

 76 Figure 7.6: Max-Min Algorithm

Figure 7 . 7 : 1 . 2 . 4 .

 77124 Figure 7.7: Clusters produced by Max-Min, Number of nodes =12

Figure 7 . 8 : 7 . 8 . 13 .

 787813 Figure 7.8: Clusters produced by Max-Min, Number of nodes =12

Figure 7 .

 7 Figure 7.10: Clusters produced by Max-Min, Singleton

Figure 7 .

 7 Figure 7.11 and Figure 7.12 show the clustering for the Max-Min and MHP respectively. The nodes are different but they are deployed in the similar conditions.

Figure 7 .

 7 Figure 7.13 and Figure 7.14 show the output for the Max-Min and MHP respectively. It can be seen that after sending close to 300 packets, one node experienced BEA-CON TIME OUT and according to the Max-Min the clustering should begin. So, close to 200 packets per node should follow. However, in case of MHP, to send close to 4000 around 30 special messages were required.

Figure 7 . 12 Figure 7 .Figure 7 . 13 :Figure 7 .

 71277137 Figure 7.11: Max-Min clusters with no maintenance, number of nodes = 12

Figure 7 . 15 :

 715 Figure 7.15: Matérn Hardcore process in dense network

7. 4 . 4

 44 Matérn Hardcore Process in large network, 450 m 2

Figure 7 .

 7 Figure 7.17 illustrates the positions of CHs when 63 sensors were deployed in an area of 17 m by 27 m. The transmission power was set to -25 dbm and threshold LQI was 106. CHS are more or less evenly distributed. Average number of special packets needed

Figure 7 . 16 :Figure 7 . 17 :

 716717 Figure 7.16: Output of Matérn Hardcore process in dense network

  implement round robin technique, we choose links/routes based on the LQI base costing. LQI estimation via CC2420 has its own limitations. The major problem being the high variability shown by the LQI. The problem is acute when nodes transmit at low power level. Fig.8.1 shows the distribution of LQI of the Base Station (BS) beacons received by different sensors when BS transmits at different power levels. Sensors are placed in a straight line with internodes distance of 3 meters.

Figure 8 . 1 :

 81 Figure 8.1: LQI distribution of BS Beacons received by different sensors as function of Transmission Power of the BS and sensor's distance from the BS.

Figure 8 .

 8 Figure 8.3 shows the state diagram for the retransmission process in the sensor networks. It shows 8 different states. The process begins at state Original Message when a node is ready to send its packet to its neighbour and ends at one of the absorbing state, i.e., Success or Packet drop. The neighbour can be a BS or some other node. Let l 1 , l 2 , l 3 , l 4 , l 5 and l 6 be the link probabilities of packet reception as shown in the Figure 8.3.

Figure 8 . 3 :

 83 Figure 8.3: State diagram for the retransmission process

p 0 = l 2 1 ( 8 . 1 )p 1 = 2 ( 8 . 2 )p 2 = p 1 + ( 1 -p 1 )l 2 3 ( 8 . 3 )p 3 = p 2 + ( 1 -p 2 )l 2 4 ( 8 . 4 )p 4 = p 3 + ( 1 -p 3 )l 2 5 ( 8 . 5 )p 5 = p 4 + ( 1 -p 4 )l 2 6 ( 8 . 6 )Figure8. 4 ,

 18112822113833214844315855416864 Figure8.4, shows the PRPD after each retransmission for different link reception probabilities. It can be clearly seen that packet delivery becomes very high after five retransmissions.

Figure 8 . 4 :

 84 Figure 8.4: Probability of Reliable Packet Reception after retransmissions

Figure 8 . 5 : 8 l 3 =0. 7 l 4 =0. 6 l 5 =0. 5 l 6 =0. 4 "

 85837465564 Figure 8.5: Load Balancing Model

5 .

 5 At the BS, all packets based on their Sequence Number and Node-Id are processed and final packet losses are calculated per node in the network. Round-Robin and MultihopLQI are also deployed without any retransmission. It makes us easier to compare both algorithms directly.

Figure 8 .

 8 Figure 8.6 shows the average number of neighbours per node over the whole network when the nodes are set at 0dbm, (-5)dbm, (-11)dbm and (-20)dbm.

Figure 8 . 6 :

 86 Figure 8.6: Average number of Neighbour per node

Figure 8 . 7 :

 87 Figure 8.7: Average number of Hopcounts per node

Figure 8 . 8 :

 88 Figure 8.8: Packet Reception in different routing Algorithm

  and Mrs. Sunita Gupta and my younger brother Dr. Ankit Gupta. Their constant support and sacrifices have made this thesis possible. "Thanks" is too little a word to express my

	x xiii 154 A CC2420 Power Characterics xiv CONTENTS Bibliography
	Contents List of Figures
	feelings.
	List of Figures	xiv
	List of Tables	xviii
	Abbreviations	xix

1.1 Layered Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Radio Irregularity Reality [101]. . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Schematic view of the data packet [1] . . . . . . . . . . . . . . . . . . . . . 2.3 Modulator [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Typical Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 LR-WPAN vs Non-Overlapping WLAN Channel Allocations . . . . . . . . 2.6 Sensornet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 MultihopLQI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 LQI and the Estimated Cost Relationship . . . . . . . . . . . . . . . . . . . 2.9 Neighbour table management . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Delta Application configuration. Direction of arrows indicates interface provider/user relationships NOT data flow direction. . . . . . . . . . . . . . . . . . . . . . 2.11 MultiHopRouter configuration. Direction of arrows indicates interface provider/user relationships NOT data flow direction. . . . . . . . . . . . . . . . . . . . . . 3.1 ZigBee Network Topology Models . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Energy Consumed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Nodes alive in the network . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  HybridLQI routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Deployment Topology, where BS is the simple node, which is attached to the Laptop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 HybridLQI Vs MultihopLQI Losses at various Transmission Power Levels. 5x10 nodes (including BS) are deployed over 250 m 2 . . . . . . . . . . . . . 6.7 Message Receive Percentage of HybridLQI Vs MultihopLQI for 6 out of 7 nodes. Each node is separated by 6 meters. BS TPL= 0 dBm and Node TPL= -20 dBm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8 LQI of various nodes with node 24, when all nodes transmits at 0 dBm . . 7.1 A typical cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 CH positions after applying Matérn Hard core poisson Process. Parameters Lower bound of number of CH required as a function of Coverage Radio Range of a Cluster Head. Number of nodes = 1000 distributed over a unit area. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 MHP in grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Matérn Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Max-Min Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7 Clusters produced by Max-Min, Number of nodes =12 . . . . . . . . . . . . 7.8 Clusters produced by Max-Min, Number of nodes =12 . . . . . . . . . . . . 7.9 Max-Min cluster formation, number of nodes 30 . . . . . . . . . . . . . . . . 7.10 Clusters produced by Max-Min, Singleton . . . . . . . . . . . . . . . . . . . 7.11 Max-Min clusters with no maintenance, number of nodes = 12 . . . . . . . 7.12 Matérn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.13 Max Min with 12 nodes, after one BEACON TIME OUT, no cluster maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.14 MHP with 12 nodes with cluster maintenance . . . . . . . . . . . . . . . . . 7.15 Matérn Hardcore process in dense network . . . . . . . . . . . . . . . . . . . 7.16 Output of Matérn Hardcore process in dense network . . . . . . . . . . . . . 7.17 Output of Matérn Hardcore Process in grid topology . . . . . . . . . . . . . 8.1 LQI distribution of BS Beacons received by different sensors as function of Transmission Power of the BS and sensor's distance from the BS. . . . . . . 8.2 Simple Multihop Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . 8.3 State diagram for the retransmission process . . . . . . . . . . . . . . . . . 8.4 Probability of Reliable Packet Reception after retransmissions . . . . . . . . 8.5 Load Balancing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.6 Average number of Neighbour per node . . . . . . . . . . . . . . . . . . . . 8.7 Average number of Hopcounts per node . . . . . . . . . . . . . . . . . . . . 8.8 Packet Reception in different routing Algorithm . . . . . . . . . . . . . . . . A.1 Output power configuration for the CC2420 . . . . . . . . . . . . . . . . . . A.2 Operating Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . . . Hardware Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Experimental Results Cont.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Experimental Results cont.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Beacon Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	LIST OF FIGURES 7.3 xviii xvii
	List of Tables
	2.1

are: Intensity of the nodes λ =1000 and h =0.1. The side length of the square is one. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 2

 2

		.1: Hardware Comparison
	Radio	Hardware	Data Rate Keying
	CC1000	Mica2	19.2Kbps	BFSK
	CC2420 micaZ, Teleos, Tmote Sky	256	OQPSK

Table 2 .

 2

	2: Experimental Results	Authors Technology/Hardware Mote type Deployment Observation	Couto et 802.11b, node with stationary 29 nodes ETX showed better results over simple minimum hop	al. [32], Cisco/Aironet 340 Linux PC placed in algorithm.	2003 PCI 802.11b card, office.	omnidirectional 2.2	dBi dipole antenna	(a rubber duck)	Woo et 4 MHz Atmel Micro-Mica 60 nodes scat-	al. [97], processor with 128 ter around an • Increase in transmit power resulted in augment-2003 KB programmable open tennis ing higher effective region. memory and 4KB court.	data memory. • Some individual pairs exhibited high variations.	RF Monolithics, • Proposed Window Mean with Exponentially ASK, 916 Mhz ra-Weighted Moving Average( WMEWMA) link es-dio,Maximum Radio timation technique. throughput=40kbps	Zhao et ASK, 433 Mhz radio, Mica 60 nodes	al. [100], ISM Band, Radio deployed in • No Acknowledgement usage for the received 2003 throughput=20kbps, office, park packets. 4Mhz Atmel proces-and a secluded	sor(128k EEPROM parking lot	and 4KB RAM)

Table 2 .

 2

	4: Experimental Results cont..	Mote type Number Observation	of	Motes	Tmote 20	Sky • RSSI appears to degrade as an exponential func-	tion of distance.	• LQI very closely correlated to packet yield.	• Found symmetrical links while both sending and	receiving data.	MicaZ 30	• RSSI is better indicator of Packet Reception	than LQI.	• Threshold RSSI.	• Average LQI is better than instantaneous LQI.	Tmote 2	Sky • Formation of high-quality and low-quality link	region.	• However, results were very limited.
		Technology/Hardware			CC2420 [1], 2.4GHz, IEEE	802.15.4 compliant						CC2420						Micro-controller operating	at 8Mhz, 48K of ROM,	10K of RAM, a 2.4GHz	ZigBee wireless transceiver
		Authors			Holland	et al. [49],	2006				Srinivasan	et al. [91],	2006			Wahba et	al. [96],	2007

  Sensor networks are divided into two types of categories: -homogeneous networks where each device in the network has equal capabilities and the heterogeneous networks where some devices are more powerful than the other devices. A Zigbee network is an example of heterogeneous networks. In 2003, a consortium of industrial partners called Zigbee alliance published first specification for Low Rate-Wireless Personal Area Network.

	2.6. ZIGBEE	22
	implement sleeping mode in our algorithms.
	2.6 Zigbee

The Zigbee

[14]

protocol is implemented on top of the IEEE 802.15.4 radio communication standard. The Zigbee specification is designed to utilize the features supported by IEEE 802.15.4. In particular, the scope of Zigbee lies in applications with low requirements for data transmission rates and devices with constrained energy sources. Zigbee proposes a classical layered architecture where each layer assumes a specific role and provides services to upper-layers. General characteristics of IEEE 802.15.4 are:

Table 2 .

 2

5: Beacon Message Parent LQI based Estimated cost Hopcount TimeStamp

Table 3 .

 3

		1: Simulation Scenario
	Scenario Network	Topology Type Node Range
	1	Simple LEACH	Homogeneous	80m
	2	Hierarchical Clustering Homogeneous	50m
	3	Hierarchical Clustering Heterogeneous 50m
	4	Hierarchical Clustering Heterogeneous 30m
		Table 3.2: General Simulation Parameters
	Simulation Area	150m*150m
	Location of Base station	67.745, 92.58
	Number of Nodes	40 (including Base Station)
	Mobility model	Random Way point
	Node speed	1m/s
	Node Pause time	8s
	CH Rotation frequency	10s
	Time out time for Child	5s
	Packet Size	127 byte
	Traffic CBR	0.2 interval time
	Energy of Base Station	5000
	Minimum thresh hold Energy 1 J
	Total Energy in the Network 187 J(excluding BS)
	Average Energy per node	4.864 J
	Simulation Time	3700 s

Table 3 .

 3 In Scenario 2 by decreasing the radio range, we increase the level of hierarchy in the network. Now, some nodes need more than two hops to communicate with the BS and not every CH is single hop away from the BS.• Scenarios {3, 4} represent heterogeneous networks i.e., only few nodes are capable of routing. Different radio ranges are used to have different network topologies. The higher the number of intermediate hops, the higher the probability of the route breakdown.

	3: Heterogeneous network parameters
	Number of Fully Functional Device	10
	Number of Reduced Functional Device 29
	Energy of Fully Functional Device	10J
	Energy of Reduced Functional Device	3J

Motivation-Orphaning phenomenon In Scenario {3, 4}, as not all the nodes are capable of routing, some nodes can be orphan and could be searching the cluster head consistently or might just have joined the cluster head who itself has become orphan. It is not the case in Scenario {1, 2} as all nodes are capable of routing and hence, no orphaning problem. The use of random waypoint mobility model (RWP) added the fair degree of randomness in the network. The reason behind the selection of radio range in Scenarios

Table 4 .

 4

		3: Grid Scenario Description
	Scenario Nodes count BS-TPL Node-TPL Distance
	30	4x4	31	10
	31	4x4	10	10
	32	4x4	3	10
	33	4x4	31	5
	34	4x4	5	5
	35	3x6	31	10
	36	3x6	10	10
	37	3x6	3	10
	38	3x6	31	5
	39	3x6	5	5
	40	3x6	3	5

Table 4 .

 4

	4: Emulating RFD and FFD in real time
	Nodes count	25+ BS
	Distance CH to BS	20 m
	Distance Nodes to BS	5-9 meters
	Total Area	1700m ( irregular circular shape)
	BS potion	center
	Cluster Topology	5x(1+4)
	Nodes (RFD) TPL	3
	CH (FFD) TPL	25
	BS TPL	31

Table 5 .

 5

	1: Scenario Description	Description Observation			Different permutations of TPL Connectivity problem, whenever there is	were employed. Nodes deployed movement. Direct communication with	on the floor in a straight line, sep-BS when TPL is high, or, multihop com-	arated by 3,6 and 9m respectively. munication when BS TPL is lower than	10 points.	Similar to a typical sensor net-Nodes connected directly with BS with	work, where BS is very powerful message reception less than 10%.	compared to other nodes.	Nodes randomly replaced by HP Less direct communication with BS and	nodes at the corner and the cen-very much less message loss. Some nodes	ter of the network. Increasing the behave like cluster-heads and act as in-	number of HP nodes from 1 to 5 termediate routers, stable topology.	in steps.	Mostly, direct communication stable topology.	with BS, just one corner node	connected via single hop.	Corner Node Diagonally opposite stable topology.	BS, have TPL=31, i.e TPL=31.	Nodes placed on the table approx Network has stable topology. Negligible	(height= 80cm). losses, less than 0.4%.	Nodes placed in grid separated by Very high loss rate , around 40-49%.	4 meters, on the ground	Internode distance-4 meters, on Less direct communication with BS. Neg-	the ground. ligible message losses around 1% for most	nodes.	Internode distance-4 meters, Mostly direct communication with BS.	placed indoors on a shiny surface.	Internode distance-4 meters, In-45% of Messages lost.	side room with lots of unarrange	furniture and metallic objects.
		BS Node	TPL TPL		31, 25, 25, 20,	20, 15, 15, 10,	10, 5 5			31 5			3 5					5 10			10 10		3,5,10 5,10		3 10		5 10			31 31		31 31
		Scenario Number	of	Nodes	1-29 12,7,5,	straight	line			30 10x4	Grid		31-34 10x4	Grid				35 6x3	Grid		36 6x3	Grid	37-51 6x3	Grid	52 10x5	Grid	53 10x5	Grid		54 10x5	Grid	55 10x5	Grid

  Routing table of HybridLQI for a node is shown in Table6.1. Routing table contains two metrics: 1. Estimated LQI cost of the downlink channel and 2. Packet Loss Percentages (PLP) between the nodes in the uplink channel. By combining both the metrics, we can estimate the wireless links more efficiently. As the PLP is calculated internally, there is no additional routing cost. HybridLQI algorithm has four phases: Initialization, Routing table, Route selection and Route maintenance (Figure 6.4).

	6.3. ALGORITHM		98
	6.3 Algorithm
	Table 6.1: Routing Table of Node A
	Node Estimated Cost PLP
	B	1000	3
	E	900	5
	C	900	10
	D	800	20

Table 6 .

 6

	2: Experimental Parameters for Dense Network
	Number of Nodes	50 in grid topology
		(5x10), obstacle rich en-
		vironment
	Distance between nodes	3m
	Packet Size	98 byte
	Frequency	10 packet/ minute
	Beacon Frequency	2 per minute
	Duration	20-45 minutes
	Maximum Number of retries 5

Table 6 .

 6

			3: Dense Network Scenarios
	Scenario BS TPL (dbm) Node TPL (dbm) Network type
	1	0	0	Symmetric
	2	0	-11	Asymmetric
	3	0	-20	Asymmetric
	4	-11	-11	Symmetric
	5	-20	-20	Symmetric

Table 6 .

 6

	4: Experimental Parameters for Sparse Network
	Number of Nodes	7 in straight line, direct line of sight
	Distance between nodes	6 m
	Packet Size	98 byte
	Frequency	10 packet/ minute
	Beacon Frequency	2 per minute
	Duration	80 minutes
	Maximum Number of retries	5

Table 6 .

 6

			5: Sparse Network Scenario
	Scenario BS TPL (dbm) Node TPL (dbm) Network type
	6	0	-20	Asymmetric

table .

 . Beacon message is similar to the MHP, however additional information is added into the parent table.

	typedef struct BeaconMsg {
	uint16_t parent;
	uint16_t cost;
	uint16_t hopcount;	// from me to "base station"
	uint16_t cluster_id; // 111 for Invalid cluster Head
	uint16_t cluster_head_connected;// if connected to cluster head or not
	uint16_t cluster_hopcount; // to know how many hops I am away from cluster head
	uint16_t clusterhead;	// if I am clusterhead or not
	} BeaconMsg;
	typedef struct ParentEntry {
	uint16_t addr;
	uint16_t cost;
	uint16_t estimate;
	.....
	.....// Info for routing
	uint8_t weight_p1; // to store weight of neighbours after phase one is finished
	uint8_t weight_p2; // to store weight of neighbours after phase two is finished
	uint8_t weight_p3; // to store weight of neighbours after phase three is finished
	uint16_t senderaddr;// to store weight's second component
	} ParentEntry;

Table 7 .

 7

	1: Deployment Parameters
	Packet Size	78 byte
	Frequency	6 packet/ minute
	Beacon Frequency	2 per minute
	BEACON TIME OUT	4 x Number of nodes
	Maximum Number of retries	5
	Transmission Power	-25 dBm
	Maximum Transmission Range Possible 5-6 meters
	Frequency Channel	11
	Threshold LQI	106
	Maximum Distance for Threshold LQI 3 meters
	Intercluster Routing	HybridLQI

Table 7 .

 7 1 lists network deployment parameters for the rest of the chapter.

  Once, the CH is evicted, the hopcount between the nodes varies with time, as we use HybridLQI as the routing algorithm between the two clusters. Later, we will evaluate the performance of the Max-Min without any route maintenance, i.e., if Cluster Head is evicted from the routing table, the Max-Min should stop and new cluster formation should take place. For ease of analysis, in Figure7.8, we are not updating the Clusterheads and the parents according to HybridLQI.What is interesting is the number of Phase Messages. For 12 nodes we needed close to 200 phase messages per node to complete all the phases of the Max-Min. The reason being that the nodes switch ON at random time and then they enter different phase at different time. Therefore, a sufficient time with enough number of phase messages are needed to fully propagate the state of the network; Figure7.9 illustrates the number of clusters produced by the Max-Min, when 30 nodes were in the network while the neighbour table size was set to 12. Several clusters were formed including several singleton cluster. As, we have mentioned earlier, Max-Min basic requirement is to know the state of the network for at least up to a node which is d hop away from it. In this work, the physical difference between the nodes may not exceed more than 2 hops, however via clustering it may be up to 3 hops.When the nodes were in initial phase and were receiving packets, they were able to store state of maximum up to 12 neighbours. As we can see from the Figure7.10 most of the nodes have weight equal to 12. What has happened that the node A was in the neighbour table of node B but node B was not in the neighbour table of node A (I am in your neighbour table, but you are not in my neighbour table). Hence, several nodes become CH after the Max and Min phase and more nodes become singleton clusters as fewer nodes

	7.4. ANALYSIS HybridLQI. 7.4. ANALYSIS	122 123

Here, in this experiment node 4 is the candidate to become CH after all the phases of the Max-Min. So, node 4 sends its beacon declaring that I am CH. Similarly, node 30 which is a BS (default CH), is also sending its beacon declaring itself to be CH. Nodes which can not become CH waits for these beacons and on receiving beacons from the CH, they join the cluster of that node. So, nodes receiving beacons of BS earlier joins with BS directly.

Case 2: 30 nodes including BS Figure 7.9: Max-Min cluster formation, number of nodes 30

  .2 shows a typical sensor network where a node Si sends packet to Sj en route towards the BS. When the packet is received by Sj it sends acknowledgement to Si. If the acknowledgement is not received, packet is retransmitted by the node Si.

	Figure 8.2: Simple Multihop Sensor Network
	8.2.1 Retransmission Model-Absorbing Markov Chain
	Let p be the probability of successful transmission to next hop. Let us also assume
	that the uplink and down-link are symmetric. Whenever a node receives a data packet, Ac-
	knowledgement is automatically sent. Therefore, the probability of reliable communication
	between two nodes without any retransmission can be given as p 2 .

Now, question arises how to model the system? So, whenever node has to route the packet to the BS, it selects its next hop neighbour and if the transmission fails, depending upon the type of the routing some packets are retransmitted to the new neighbour or the previous parent. So, when a node (Figure

8

.3) sends its packet for the first time, it is in the state Original Message. From this state, the node can go to either state Success or to the next state Retrans-1 . From the Retrans-1 state, now the node can go to Success or to Retrans-2 state. Finally, if the node is at Retrans-5 and again the acknowledgement fails from its parent, the node will be in the state Packet Drop and packet will be dropped, which will contribute to the losses in the network. If the acknowledgement is received, node will be in the Success state.

Since, the node can go to absorbing state from any of its transition state, this network fully satisfies the condition for the absorbing Markov chain. Following are the definitions for the Absorbing Markov chains: Definition A state s i is called absorbing if it is impossible to leave it(i.e., p ii =1). A Markov chain is absorbing it has at least one absorbing state, and if from every state it is possible to go to an absorbing state (not necessarily in one step).

  So, if the communication link has a success rate of 90%, there is 0.9999 is the expected number of times a node will be in the state S. Let p 0 ......p n , be the probability of reliable packet delivery (PRPD) up to n retransmissions. Then,

	
	
	 .9999 0.0001 
	
	 0.9998 0.0002 
	  0.9987 0.0013 
	 0.9931 0.0069 
	
	 0.9639 0.0361 
	
	0.8100 0.1900

  Route 0 Route 1 Route 2 Route 3 Route 4 Route 5 So, in case a route with 70% success is chosen, there are 25% chances that at least 3 retransmissions are necessary before successfully transmitting the packet to the next neighbour.Matrix B gives the success and loss probabilities of the routes. If Route 3 is chosen, it has 40% packet drop probability.

								
	1	0.19	0.068	0.034	0.022	0.016	 
	0	1		0.36	0.18	0.11	0.088	 
								
	0	0		1	0.51	0.32	0.24	 
	0	0		0	1	0.64	0.48	 
								
	0	0		0	0	1	0.75	 
	0	0		0	0	0	1
					
				S	L
					
		Route 0	  0.9859 0.0141  
					
		Route 1	  0.9260 0.0740  
	B =	Route 2	  	  0.7944 0.2056 
		Route 3	  	0.5968 0.4032   
		Route 4	 	 0.3700 0.6300 
					
		Route 5		0.1600 0.8400

Table 8 .

 8

	1: Experimental Parameters
	Number of Nodes	30 (5x6) in grid topol-
		ogy, very smooth sur-
		face, direct line of sight
	Area	12 m X 36 m
	Packet Size	60 byte
	Frequency	10 packet/ minute
	Beacon Frequency	2 per minute
	Duration	30-40 minutes
	Maximum Number of retries 5

Table A .

 A

		1: TPL to dbm
	TPL	dbm
		0
		-9.14E+02
		-3.01E+03
		-6.10E+03
		-1.00E+04
		-1.45E+04
		-1.95E+04
		-2.47E+04
		-3.00E+04
		-3.52E+04
		-4.03E+04
		-4.52E+04
		-5.00E+04
		-5.47E+04
		-5.94E+04
		-6.44E+04
		-7.00E+04
		-7.63E+04
		-8.33E+04
		-9.12E+04
		-1.00E+05
		-1.10E+05
	9	-1.21E+05
	8	-1.34E+05
	7	-1.50E+05
	6	-1.69E+05
	5	-1.92E+05
	4	-2.18E+05
	3	-2.50E+05
	2	-2.87E+05
	1	-3.30E+05

Part of this work is done with the collaboration with IRIT-Toulouse, particulary under the guidance of Prof. Andé-Luc Beylot and Dr. Riadh Dhaou (at Toulouse). Experiments were carried out jointly with Rahim Kacimi at Telecom-SudParis and IRIT-Toulouse.

Experiments were carried out with the help of Chérif Diallo

Overall, in this chapter, we present 55 Scenarios (Table 5.1) running for 20 minutes each (approximately). These Scenarios take into account various permutations for TPL, inter-sensor distances, grid or straight line. In all the scenarios, BS is connected to a Laptop. Figure 5.3 shows the grid topology. In chapters 4 and 5, we have seen that how asymmetric links can affect the packet delivery performance of the sensor network.

In this chapter 1 , we propose a simple way to improve the behavior of the Mul-tihopLQI algorithm without requiring to transmit additional information about the state of the network. To face the problem of the asymmetric links, the information about the quality of the links is needed. The MultihopLQI obtains link quality from the LQI calculated from the received beacon (downlink). On the other hand, acknowledgments are implemented (and necessary because of the dynamic nature of the routes, which makes it impossible to use negative acknowledgements). We propose the use of this acknowledgment based link estimation to measure the uplink channel quality. So, in the downlink, we measure the LQI provided by MultihopLQI and for the uplink we use acknowledgment based Packet Loss Percentage (PLP). Measuring the LQI for the uplink channel would require additional transmission over the network which we want to avoid. As MultihopLQI already uses acknowledgements, link estimation via PLP does not introduce any cost to the network.

Unlike OLSR [START_REF] Jacquet | Optimized link state routing protocol (olsr)[END_REF], in HybridLQI there is no multipoint relay. 1 Mohit Sharma contributed in the development of the code in TinyOS 93 6.1. BACKGROUND 94

Background

In the MultihopLQI algorithm each node X periodically broadcasts its beacons.

Beacon messages are broadcast messages with TTL=1 (time to live). It contains information such as hop-count and cost (EC-estimated cost) of reaching BS from that node. This cost is zero for the Base Station. The neighbour Y on reception of the beacon estimates the LQI of the link between X and Y . Later, the overall cost of the path is computed by adding LQI of the received beacon with the EC of the beacon. The main drawback of MultihopLQI is the assumption that the links are symmetric. Actually, when the node Y receives beacon from the node X, it assumes LQI from X to Y is equal to LQI from Y to X. But it may not be true. To understand this, let us consider a network with two nodes and the BS.

Suppose BS transmits at higher power and both A and B are in the radio range of BS.

Let us also assume that BS is out of radio range of the node A. If Aś estimated cost of directly reaching the BS is lower than via node B, it will try to send a packet directly to BS. The acknowledgement from BS will fail, as the BS will never receive this packet. Then, node A will send this packet to node B and as per the behavior of MultihopLQI algorithm it continues sending its packets to node B till acknowledgement fails from the node B.

When node B's acknowledgement fails, node A looks at its routing table. Again it sends its message to the BS. Acknowledgement will fail again and node A will send its messages via node B. This cycle will continue. Therefore, it is important to take into account the history between the nodes.

Motivation

As per the documentation of CC2420( See Appendix A) "The link quality indication (LQI) measurement is a characterization of the strength and/or quality of a received packet, as defined by IEEE 802.15.4 standard([14])." In the Tmote Sky the range of LQI lies from 50-110. Higher the LQI is, better the channel is.

During the initialization phase of the MultihopLQI, each node sends its beacons containing the estimated cost of reaching the BS. This cost is zero for the beacon sent by the BS. Nodes also estimate the LQI of the received beacon. By parsing the cost from the received beacon and adding it with the new LQI cost, total cost is estimated for reaching the BS. Then the node insert this cost in its beacon and sends a new beacon. The node • Therefore, Max-Min needs to know and store information for all of its neighbours, which is a cumbersome and requires memory.

• Node must send its beacon messages repeatedly so that it neighbours could be able to receive them. Nodes only in Phase 1 can participate in Max-Min cluster formation heuristic.

• A pause is necessary after this phase as nodes switch ON at random time, therefore to have a correct view of the network, a node must wait for some time.

2. Phase 2: Once, a node finishes computing its weight, it needs to broadcast that weight again with TTL=1. So, its sends phase message. On reception of these packets by other nodes, nodes which are in Phase 2 could only be able to process these packets.

Based on these packets, each node can compute maximum weight with the sender id.

typedef struct PhaseMsg { uint16_t phase;// to check phase uint8_t weight; // to send weight of its own uint16_t sender;//weight second component } PhaseMsg;

• Node must send its phase messages repeatedly so that it neighbours could be able to receive them.

• A pause is necessary after this phase as nodes enter in Phase 2 at different time, therefore to have a correct view of the network, a node must wait for some time.

3. Phase 3:Nodes send phase messages with their maximum weight information in it, so as their neighbors update their neighbor table. This marks the end of floodmax phase.

• Node must send its phase messages repeatedly so that it neighbours could be able to receive them.

• A pause is necessary after this phase as nodes enter in Phase 3 at different time, therefore to have a correct view of the network, a node must wait for some time.

4. Phase 4: Once, the max weight is known, nodes perform another set of calculations to know the Min and then broadcast it.

ANALYSIS

memory requirement can cause problems if network is denser so that node cannot store information of all of its neighbors.

• In Max-Min Heuristic, number of phase messages required is directly proportional to number of neighbours. This results in energy consumption. Number of control messages required in MHP is lower. Hence, we can say that overall overhead in MHP is lower.

In order to shake a hypothesis, it is sometimes not necessary to do anything more than push it as far as it will go.

Denis Diderot (1713-1784)

Chapter 8

Performance of load balancing in real world

In this thesis, we have seen how difficult it is to implement sensor networks in the real world. In Chapter 3 via simulation studies, we saw how topology effects sensor networks. In Chapter 4, we saw the problems associated with the LQI. Similarly, in Chapter 5 we saw the use of LQI for cluster head selection mechanism. In Chapter 7 we improved the performance of the MultihopLQI in the asymmetrical links networks.

In this chapter, we investigate the idea of load balancing for increasing the life time of the sensor network. The question arises whether load balancing is really implementable.

If yes, what should be the minimum requirement? How far can we push this hypothesis?

Finally, can we apply the load balancing techniques in generic manner? In this chapter, we investigate some of these issues. We apply link quality based algorithms and compare their performance with the round robin algorithm.

Introduction

More often than not sensor networks are assumed to have symmetric links. Many experimental studies [START_REF] Gupta | Understanding topology challenges in the implementation of wireless sensor network for cold chain (to appear)[END_REF], [START_REF] Becker | Experimental study: Link quality and deployment issues in wireless sensor networks[END_REF], [START_REF] Lal | Measurement and characterization of link quality metrics in energy constrained wireless sensor networks[END_REF], [START_REF] Zhao | Understanding packet delivery performance in dense wireless sensor networks[END_REF] and [START_REF] Son | Experimental analysis of concurrent packet transmissions in wireless sensor networks[END_REF] have shown that in wireless sensor networks (WSN) radio links are not reliable. Also, during the real deployment of sensor networks there are too many parameters which make sure that links may not remain symmetric.

List of Publications International Conferences

Appendix A CC2420 Power Characterics