Cross Layer Design for Wireless Sensor Networks

Keywords: Wireless Sensor Networks, Data Dissemination Architecture, Routing Metrics, Multichannel Design

The sensor networks are considered to have the potential to create efficient monitoring applications. A typical wireless sensor node comprises of sensing, computing and networking capabilities. These devices are cooperatively networked to gather, process and forward the data towards the interested users. They have limited battery capacity and sometimes the battery replacement is not considered to be a practical option. In case of video monitoring applications, they have to forward the multimedia packets having realtime deadlines. Thus, there is a need to have an energy efficient and a minimum delay data dissemination design techniques based on the application requirement. Keeping in mind the processing capabilities of these devices, it is considered a challenging task.

This thesis presents an energy efficient and minimum delay data dissemination design for a disaster management application installed inside a building. In this application, a building is considered to be in a disastereous situation such as on fire. Based on the data forwarded by the installed sensor network, the first responders decide the rescue and fire extinguishing strategy. There exists two class of network associated with this application. One considers the monitoring of physical parameters such as temperature, pressure and humidity inside the building and the second one performs the task of video surveillance inside the network. Sensing physical parameters do not need large processing capabilities due to less amount of data communication. Thus, the main research interest is to optimize the energy consumption due to data transmission. On the other hand, video surveillance application has to forward a large amount of video streaming packets. There is a need to not only minimize the energy consumption but also to minimize the packet delivery delay in order to meet the application layer deadlines.

Thus, we focus on the efficient delivery of data for these two network classes. The first contribution of the thesis talks about the virtual data dissemination architecture for collecting the data in an energy efficient manner. The considered network collects the physical parameters such as temperature, pressure and humidity inside the building. The second contribution focuses on the energy efficient minimum delay routing metrics for the video streaming application operating inside the building. It minimizes the delay so that the application layer deadlines are fulfilled with minimum energy consumption. The third contribution explores the usage of multichannel design in the sensor network. The centralized and distributed channel allocation mechanisms are described that tries to minimize the interference between communicating nodes in order to increase the network throughput. The first contribution targets the physical parameters monitoring network and second and third contribution focuses on video surveillance network. The efficiency of the proposed appraches are evaluated through simulations in Network Simulator NS-2.

In 1888, Heinrich Rudolf Hertz produced the first radio wave ever. By 1894, these radio waves became a way of communication. In 1930, first high-temperature thermostat metal was introduced that led to the development of first room thermostat in 1933. The first integrated circuit was born in 1958 by Jack Kilby that advanced the development of microprocessor systems. The advancement in these three fields of wireless communication, sensors and processors had inspired the research for low-power wireless sensor networks in late 90's. Today, a large number of sensor networks are deployed throughput the world for a wide range of applications from building automation to underwater monitoring applications.

Context

We are living in an era where technological developments have changed our lives. This has led to increase the automation in everyday life activities and it is expected to increase in future. This automation can be achieved by monitoring various aspects of different activities that tells us the importance of a sensor device. These devices have sensing, computing and communication capabilities. This has enabled us not only to detect certain events but to transmit the information to get the required job done. In the last decade, a number of applications have been realized using sensor networks. However, there are many research issues in wireless sensor networks that needs to be considered. These devices are installed in places where the battery replacement is difficult so the energy consumption is an important aspect of research. Also, systems such as video surveillance applications have lead to take account of real time data reporting deadlines and the research is also focussed on developing strategies to achieve these targets. For example, for forest fire detection application, sensors can have low sensing frequency and routing delay but they should maximize the lifetime. Conversely, surveillance of a person working alone in sensible zones The earliest research activities on sensor network targetted the development of low-power devices allowing the deployment of a large-scale networked sensor system in the project SensIT [START_REF]Sensit[END_REF]. In the same way, there are a number of research projects for sensor networks such as SensorSim [START_REF]Sensorsim[END_REF] resulted in a simulation framework for analyzing sensor networks, SmartDust [START_REF]Smartdust[END_REF] provides a milli-meter scale platform using optical reflector technology and GEODES [6] targets the energy optimization in a disaster management application. In this context, the work presented in this thesis has been carried out at Electronics, Antennas and Telecommunication Laboratory (LEAT), from University of Nice-Sophia Antipolis aiming to provide mechanisms that address the challenges of energy efficient and fast data collection algorithms for GEODES Project [6]. This project targets a disaster management application for a building on fire and fire fighters perform the rescue operation (figure 1.1). This application has to perform two operations so the network is divided into two parts. The first part of the network senses the environmental parameters such as temperature, humidity and the second part of the network gathers the video of the building partition on fire (figure 1.2). Thus, the considered partition of network is static and do not move. This information helps in making a suitable decision for the firefighters. Both of these separate networks have to conserve the energy as there might not be a source of electricity in a building on fire. Also, the part of the network that performs video monitoring has realtime data reporting constraints in addition to the energy constraints.

In this chapter, first the objectives are described followed by a brief introduction to the thesis contribution. At the end, the thesis organization is explained.

Objective and Motivation

Sensor networks consist usually of cheap, low-power devices having sensing capabilities. These are installed in a network to gather the required information. A vast range of applications requires event detection in timely and energy efficient manner. Different type of data dissemination architectures can be used for efficient data delivery that can help to reduce the energy consumption. Delay minimization is another aspect that needs to be considered in addition to energy consumption minimization as there are many applications such as the disastor management that requires the information to be communicated as soon as possible. In high traffic rates, the classical channel allocation might provide poor performance due to channel collision. Here, we need to consider the multichannel allocation to minimize the interference in order to decrease the energy consumption as well as packet reporting delay.

Thus, there is a need to have efficient data dissemination techniques that on the one hand minimize the energy consumption and on the other hand has to take care of data rate for certain applications. The efficient techniques that are employed at network level consists of network partitioning strategies for efficient data delivery, multi power level data transmission, multichannel allocation design etc. These are different network parameters that can help us in finding an efficient network design.

In this thesis, we focus on the data collection architecture design that leads to energy efficient and timely delivery of data to the required nodes. The sensor networks are usually organized into clusters based on the geographic location of nodes to get better network management. Here, we use a clustered network design and explain various algorithmic techniques to achieve our goals.

Based on this practical context, this thesis focus on the following research ques- How an energy efficient and delay minimization data delivery can be possible in a wireless sensor networks by using the geographical routing techniques.

Contribution

This work claims to propose a network architecture to minimize delay as well as energy consumption in a clustered wireless sensor networks. The main contributions of the thesis are:

• Development of network partitioning techniques for energy efficient data gathering.

• Development of routing metrics to consider the delay as well as the global energy consumption for multiple power transmission case.

• Multichannel design for interference minimization to get increased packet delivery rate and minimized energy consumption.

Report Organization

This thesis report is organized as follows. In chapter 2, the sensor network basics are described. The sensor node composition as well as the available sensor platforms are discussed. Target applications are also described and the parameters that are needed to be optimized are discussed as well.

Chapter 3 describes the energy efficient data gathering network partitioning techniques for the data dissemination. These are also compared with the existing grid based data collection architectures.

The next chapter 4 describes the inter-cluster routing to minimize energy consumption as well as delay. This can be used in a partitioned network using clustering techniques to avoid violation of application layer deadlines as well as to minimize the energy consumption.

Chapter 5 describes the centralized as well as distributed channel allocation mechanisms for a clustered wireless sensor networks. It investigates which type of channel allocation is more appropriate by considering different scenarios. In the following chapter 6, we describe how to combine the approaches for energy and delay minimization proposed in chapters 4 and 5. Finally chapter 7 concludes the thesis and discusses the perspective work. In this chapter, sensor node composition, available sensor devices and sensor network design techniques are discussed. Each device has different processing capabilities and based on these capabilities, choice of a sensor device for a certain application is made. The research area focuses on the design of an energy efficient and minimum delay sensor network architecture. This can be achieved by exploring various parameters for sensor devices that are introduced in this chapter.

Sensor Node

A sensor network consists of tiny, low-cost and limited power devices having sensing capabilities. Together they form a network that is capable of sensing physical activity of interest and communicating the sensed data using the deployed network. A sensor node consists of the following components (figure 2.1).

• Sensing Unit: This part performs the task of sensing a physical phenomenon such as temperature, humidity, light, vibration, motion detection, surveillance, etc. for the application that we want to deploy.

• Processing Unit: This is the unit that performs the task of processing based on the data collected by the sensing unit. The sensor devices that need to process a small amount of data sensed may use the sensor devices having low processing speed and memory space. On the other hand, the applications that need to process a large amount of data, there is a need to use a device having a processor with higher operating frequency as well as larger memory.

Sensing Unit

• Transceiver Unit: It comprises of low power short range radio. For example, the transceiver unit can operate on 2.4 GHz Industrial, Scientific and Medical (ISM) band or on un-licensed 868-915 MHz band. Typical data rates are from 50 kbps to 250 kbps. Some of them also support multiple frequency channels which can be used to design a multichannel, minimum interference design.

Components such as CC1000 and CC2420 provided by Texas Instruments are some examples of radios used in the available devices and their features are listed in table 2.1.

• Power Unit: The sensor devices typically use batteries, such as rechargeable AA batteries having 2.7V-3.3V. As it can be difficult to replace these batteries in a deployed network, there is a need to have energy efficient design approaches at the system as well as the network level to minimize the unnecessary wastage of power. Some features of commercial sensor devices listed in table 3.1 are illustrated below.

• Stargate [5]: This node has a 32MB flash memory and a maximum clock speed of 400 MHz allowing its utilization for image processing or video surveillance applications.

• Imote2 [5]: It has an operating frequency range of 13-416MHz and thus energy can be saved by operating at lower frequency for an application that does not have stressing realtime deadlines while this device can be operated at higher frequency to meet the realtime deadlines.

• Mica2/Micaz [5]: These nodes have a less operating frequency as compared to the other two nodes described above. It can be used for applications that do not involve high computing or communication requirements such as multimedia processing and routing.

• TelosB [5]: It operates at lesser frequency thus it can be used in applications that do not have large amount of data to be relayed.

• PowWow [START_REF]Powwow[END_REF]: These nodes consist of a MSP430 motherboard, CC2420 radiochip and an Actel IGLOO coprocessing FPGA board that allows for hardware acceleration.

The computation, communication capabilities of various sensor devices are plotted against their size, power consumption in figure 2.2.

Applications

Sensor devices are normally deployed in a place for monitoring applications. Typical applications consists of:

• Surveillance Applications: These applications are used to perform video surveillance for security related applications. These are not event driven applications but they periodically send the data towards the node that needs it. They require nodes with high computational powers and video capabilities such as iMote2 or Stargate Node. In [START_REF] Sikka | Wireless adhoc sensor and actuator networks on the farm[END_REF] is illustrated an example of such application that is used for monitoring on a farm.

• Disaster Management: In this type of applications, nodes are for instance deployed in a building that helps in detecting some disastrous event such as fire. Based on the detection of such events, first responders can come for rescue. This network if deployed in such a building will have energy as well as realtime constraints for data to be transferred. This is so because in such a situation it is probable that all the devices would be working on battery power due to unavailability of electric power. In [START_REF] Kumar | Robot and sensor networks for first responders[END_REF] is illustrated an example of such application where a sensor network directs the first responders for efficient disaster management.

• Industrial and Building Automation: In this application, the network is deployed in a building or industry and the main task of such network is to perform autonomously some global control activities for different devices. But in a building these devices can be connected to an energy supply source so they will not be subjected to tight energy constraints [START_REF] Ramamurthy | Wireless industrial monitoring and control using a smart sensor platform[END_REF], [START_REF] Chintalapudi | Monitoring civil structures with a wireless sensor network[END_REF].

• Health Care: Sensors in this application area could be used for the monitoring of patient data [31] or for tracking doctors and patients inside hospitals [START_REF] Hamalainen | Wireless applications in healthcare and welfare[END_REF]. The constraints that need to be addressed are for energy as well as the delay. This application should use a multichannel design in order to reduce interference with other devices in the hospital that could exploit the same bandwidth.

• Underground Applications: Sensor networks could be deployed in mines [START_REF] Akyildiz | Wireless underground sensor networks: Research challenges[END_REF] which are used to collect various parameters such as the hazardous gas level inside the mine for miners' security. There are other underground applications that involve the soil monitoring for agricultural applications [START_REF] Chehri | Uwb-based sensor networks for localization in mining environments[END_REF], [START_REF] Li | Underground coal mine monitoring with wireless sensor networks[END_REF].

• Maritimes Applications: These are some sensor networks that are used to focus on maritime applications such as water distribution monitoring. The design of such applications involves the accurate channel design for better performance. In [START_REF] Lin | Wireless sensor network: Water distribution monitoring system[END_REF] is an example of such an application that targets a water distribution management system.

These applications are resumed in table 2.3 and their communication versus computation requirements for various available devices are shown in figure 2.3.

Inputs and Outputs in a Sensor Network Application Model

Applications deployed over sensor network involve data traffic in the network. A sensor node that generates data is a source and a sensor node that is in need of data is called a sink. The sensor nodes can also forward the data generated from source towards the sink. The application scenario is modeled such that the data is periodically or aperiodically sent from a source towards a sink. It can also be a query based data generation where a query is sent form a node towards the sink and the sink will reply in response to that query. Thus, the constant bit rate traffic generated from each source needs to be considered in order to accurately model the application. The data is relayed through the neighboring nodes and they are named as relay nodes. This is shown in figure 2.4. If a node is over loaded with the task of data forwarding, it will consume more energy than other nodes and will earlier finish its battery resources. This phenomenon is called the hot spot creation. If the network consists of similar type of nodes, it is called the homogeneous network. Otherwise, if it consists of different type of nodes, it is called a heterogeneous network. The sensor network protocol stack consists of application, transport, network, medium access control and physical layer and it is illustrated in the figure 2.5. The application layer consists of main application and various network management features specific for each application. The transport layer in sensor network is responsible for ensuring data reliability and congestion control. The network layer is responsible for routing the data packets towards the destination while the medium access control is responsible for efficiently sharing the communication resources between the nodes. The physical layer is responsible for actually placing the data packet on the communication medium.

Geographical Division for Network Management

To reduce the complexity of network management, traditionally the network is geographically divided into partitions where each partition is assigned a certain function for data forwarding. There are different ways to divide the network from a set of geographically dispersed nodes. Some nodes inside that network are assigned the task of data relaying. For example, we can divide the network into:

• Cluster Based Division: The network is divided into clusters of appropriate size based on factors such as the antenna communication range and the presence of obstacles. For example, avoiding any obstacle in cluster formation process will help in reducing the energy consumption for data collection inside the cluster. This helps in better network management and some examples of these techniques include [START_REF] Li | A cluster based on-demand multi-channel mac protocol for wireless multimedia sensor networks[END_REF] and [START_REF] Starobinski | Nearoptimal data dissemination policies for multi-channel, single radio wireless sensor networks[END_REF]. The nodes lying inside the cluster • Grid Based Division: The network is organized into a grid based structure. It is a special case of cluster based design where each cluster is of equal size and in the shape of a square. Some examples include [START_REF] Kweon | Grid-based energy-efficient routing from multiple sources to multiple mobile sinks in wireless sensor networks[END_REF] and [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF]. The nodes lying inside the cell are called member nodes and the member node that is responsible for locally gathering and forwarding the data is called the cell head. The inter cell data forwarding can use some geographical routing technique such as XY routing where first the packet is forwarded in X direction and then in the Y direction until the packet reaches its destination.

• Regular Geometric Shaped Division: In this type of network division, the network is divided into regular sized geometric shapes such as a rectangle [START_REF] Shin | Railroad: virtual infrastructure for data dissemination in wireless sensor networks[END_REF], a line [START_REF] Ben | A line-based data dissemination protocol for wireless sensor networks with mobile sink[END_REF] or a quad tree [START_REF] Mir | A quadtree-based hierarchical data dissemination for mobile sensor networks[END_REF].

Some of the nodes lying on these structures are responsible for data forwarding. We discover this aspect in chapter 3.

Routing Protocols

The task of routing protocol is to forward the data traffic towards the sink(s). There are certain objectives that a routing protocol should be able to cope with. These are listed below:

• Quality of Service (QoS) Parameters: Here, the quality of service is attached to the application perspective. The objective is to route the traffic through a path that minimizes the delay for a packet to reach its destination. Thus, routing protocols will concentrate on choosing a path that will minimize the delay. It can be a path having minimum number of hops towards the sink or the path that avoids to choose a congested path. The minimum number of hop path ensures to have minimum communication delay. While the minimum congestion path makes sure that the packet processing delay is minimized by reducing the packet loss due to buffer overflow at a node.

• Energy Consumption: This routing metric tries to choose a path that consumes minimum energy to forward the data towards the sink. Because of limited energy resources of the sensor nodes, energy consumption is the main concern for developing a routing protocol. Thus, shortest path routing may not be very useful in optimizing this metric. Communication constitutes an important contribution to energy consumption in sensor nodes. This implies the need to route the packets towards the sink in an energy efficient manner that not only minimizes the energy consumption but it also avoids to overwork small number of nodes. These overworked node are called the hotspots to emphasize their excessive energy consumption.

• Connectivity: It should be able to have a connectivity from source to the sink to have a reliable data delivery. If the path is broken, the routing protocol should be able to redirect the traffic via another route towards the sink. The path may be broken due to node death after its energy is consumed.

The routing techniques can be classified into various categories. These are listed below:

• Proactive Routing: These protocols decide the data forwarding path based on a pre-calculated path saved in a table. This imposes a large amount of data to be stored for memorizing all the paths. Some examples of reactive routing protocols are listed below:

-DFR (Direction Forward Routing) [START_REF] Lee | direction" forward routing for highly mobile ad hoc networks[END_REF]: This scheme is based on direction of arrival of path updates. If the predecessor which is responsible for providing updates for routing the packets has changed its position, then the routing information is not valid. Thus, it takes mobility into account for selecting optimized routes in an adhoc network.

-Guesswork [START_REF] Parker | Guesswork: robust routing in an uncertain world[END_REF]: In this scheme, flooding packets are generated from the sink node. That is a technique which helps in minimizing the flooding packets for route discovery. The route selection is based on expected transmission count metric.

-OLSR (Optimized Link State Routing Protocol) [START_REF] Olsr | [END_REF]: This protocol uses Hello and Topology control messages to discover and disseminate link state information in mobile adhoc networks. The sender can select its multipoint relays (MPR) based on one hop node that offers the best routes to the two hop nodes. Where, MPR is the node that performs the job of relaying message between nodes.

-WAR (Witness Aided Routing) [21]: This protocol targets mobile adhoc networks. The goal is to minimize number of errors and effectively handle errors when they occur. It tries to eliminate the use of unidirectional routes.

• Reactive Routing: These routing protocols decide the next hop path for each packet by flooding the route request packets in the network. The main disadvantage is the increase in network traffic due to flooding packets. Thus they do not need to pre-calculate the next hop path for all the destinations. Examples of such a routing technique are listed below:

-ESAODV (Extra Secure Ad Hoc On Demand Vector) [START_REF] Satria Mandala | A variant of merkle signature scheme to protect aodv routing protocol[END_REF]: It is an extension of Ad hoc On Demand Distance Vector (AODV) Protocol [1] to include the security features using Merkel Signatures.

-RSRP (Robust Secure Routing Protocol) [START_REF] Afzal | Rsrp: A robust secure routing protocol for mobile ad hoc networks[END_REF]: It is a reactive routing protocol that considers security features in its mechanism by including authentic broadcast mechanisms.

-Multirate Ad hoc On-demand Distance Vector Routing Protocol [START_REF] Paoliello | Improving reactive routing on wireless multirate ad-hoc networks[END_REF]: This is an extension of AODV Protocol [1] and it optimizes AODV by electing high throughput routes while not increasing the signalling overhead for multirate environments.

-Reliable Ad hoc On-demand Distance Vector Routing Protocol [START_REF] Khurana | Reliable ad-hoc ondemand distance vector routing protocol[END_REF]: This protocol proposes a cooperative security scheme based on local monitoring to solve the problem of malicious attacks as well as selfish behavior of nodes.

-CHAMP (CacHing And MultiPath routing) [START_REF] Valera | Cooperative packet caching and shortest multipath routing in mobile ad hoc networks[END_REF]: It uses cooperative packet caching and shortest multipath routing to reduce the packet loss due to frequent route breakdowns.

-Dynamic NIx-Vector Routing [START_REF] Lee | Dynamic nix-vector routing for mobile ad hoc networks[END_REF]: It is a reactive protocol that tries to find stable route by maintaining few routes per destination.

• Geographical Routing: This type of routing protocols decide the data forwarding path based on the geographical coordinates of the destination node. This is useful in applications involving a network deployed in one geographical location so time to reach a certain destination can be minimized by choosing a next hop node that is lying closest to the destination direction. Normally this type of protocols are used in sensor network applications. Some examples include:

-Decomposition-based Routing Protocol (DRP) [START_REF] Kermarrec | Greedy geographic routing in largescale sensor networks: a minimum network decomposition approach[END_REF]: It is a centralized protocol that divides the network into minimum number of greedy routing components.

-Greedy Distributed Spanning Tree Routing-3D (GDSTR-3D) [START_REF] Zhou | Practical 3d geographic routing for wireless sensor networks[END_REF]: It considers a 3D environment for data forwarding. Each node has a 2-hop neighbor information to increase the forwarding success.

-Geographic routing for lossy links [START_REF] Zúñiga | Efficient geographic routing over lossy links in wireless sensor networks[END_REF]: It is geographic routing protocol that considers the next hop selection to avoid the lossy links. This is done by considering a product of packet reception rate and the distance to the destination for a neighbor as the routing metric.

-Geographic Routing with Environmental Energy Supply (GREES) [START_REF] Zeng | Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply[END_REF]: This is a geographic routing protocol that takes care of renewal environmental energy capacity in addition of the lossy channel conditions.

-Geographical Power Efficient Routing (GPER) [START_REF] Wu | Power-aware single-and multipath geographic routing in sensor networks[END_REF]: This geographical routing protocol tries to use multipaths for sending a packet towards the sink in order to do the energy load balancing.

-Hierarchical Geographic Multicast Routing (HGMR) [START_REF] Koutsonikolas | Hierarchical geographic multicast routing for wireless sensor networks[END_REF]: This protocol considers a grid based network division for location based multicast routing.

-Forwarder Selection Approach in Three Dimensional Wireless Sensor Networks [START_REF] Kumar | An improved forwarder selection approach for energy aware geographic routing in three dimensional wireless sensor networks[END_REF]: This protocol considers the next hop selection for a 3D scenario based on the greedy geographic routing that may result in energy depletion of repeated selected nodes.

• Hierarchical Routing: These routing techniques divide the network into different hierarchies of clusters and each hierarchy forwards the packet to the adjacent hierarchical level to reach the destination. This hierarchy organization can be done for a specific objective such as minimizing number of hops to the sink, reducing the energy consumption, etc. Some examples of hierarchical protocols are listed below:

-A top-down hierarchical multi-hop routing protocol [START_REF] Singh | A new top-down hierarchical multi-hop routing protocol for wireless sensor networks[END_REF]: It is a solution that divides the network into different clusters and the clusterhead in one hop away from each node.

-A Hierarchical Routing Protocol for IP-based Addressing [START_REF] Kwon | A hierarchical routing protocol for sensor network reconfiguration[END_REF]:

This protocol considers the IP-based addressing schemes for the hierarchical routing schemes.

-Hierarchical Routing Protocol for Energy Efficiency [START_REF] Huang | Energy-efficient hierarchical routing protocol for wireless sensor networks[END_REF]: It considers an energy efficient load distribution for the clusterheads based on the residual energy.

-Energy-Efficient Multi-hop Hierarchical Routing (EMHR) [START_REF] Huang | Energy-efficient multihop hierarchical routing protocol for wireless sensor networks[END_REF]: This protocol is a multihop routing technique that avoids choosing low energy nodes for the clusterhead.

Due to the routing table size constraints, the reactive routing is applicable to small sized networks. Also, the proactive routing is more applicable to adhoc networks where the routes are frequently broken due to mobile nodes. The geographical routing techniques are appropriate for networks whose nodes know their relative geographic position. Thus, its difficult for geographic routing to support the mobility except if each node has a Global Positioning System (GPS) that updates its position each time it moves or if a localization technique is implemented [START_REF] Mao | Wireless sensor network localization techniques[END_REF]. The hierarchical routing can be adopted to large sized networks but with little node mobility support. Based on this discussion, we conclude that for sensor networks with no mobility it is appropriate to implement either geographic or hierarchical routing.

Medium Access Control (MAC) Protocols

If the sensor nodes are operating on a single channel, the transmission of the node is listened by multiple sensor nodes. Thus, the medium is shared by these transmissions. This implies the design of an efficient MAC protocol. It should ensure that the collisions are minimized when neighboring nodes talk with each other. The minimized interference will make sure that the retransmission at the MAC layer is minimized. This will have an important effect on the energy consumption of an individual node. The main challenges for MAC protocol design are listed below:

• Energy Consumption: The limited energy level of sensor devices require an energy efficient MAC design. The communication, reception and listening energy consists of a significant percentage of energy consumed by a sensor device. Thus, MAC should make sure that the communication and reception energy consumption per packet is minimized. The main sources of MAC energy consumption are listed below:

-Collisions: The collisions occur when closely located sensor nodes send the data to the same receiver on overlapping time intervals. This can lead to non-reception of a packet leading to collision. Thus, MAC protocol should be able to minimize the collisions.

-Retransmissions: The collisions or packet loss due to channel condition for a particular channel lead to the retransmission of data. This costs in terms of transmission and reception energy consumption. The MAC protocol should be able to minimize this by considering the channel conditions.

-Idle Listening: This occur due to overlistening of channels by a node when there is no data transmission. Also, a packet that is not destined to a node is received consumes energy as well.

• Delay: Delay is the amount of time spent by a packet in MAC layer before it is transmitted. It depends on the choice of MAC layer as well as the traffic load. This has a significant impact on the Application layer QoS requirement of the network as MAC can prioritize traffic based on the traffic classes [START_REF] Felemban | Mmspeed: Multipath multi-speed protocol for qos guarantee of reliability and timeliness in wireless sensor networks[END_REF].

• Throughput: It is the rate with which the messages are processed by the communication system and is usually measured in terms of bits/second. The wireless channel and choice of MAC protocol impacts the network throughput. Thus, it is an objective of MAC protocol to maximize the throughput.

• Scalability: It is the ability of system to meet its performance parameters when the size of the network is increased. In large scale sensor network with high node density, it is a challenging research question. The MAC protocol should be able to meet its performance metrics in presence of these challenges.

The MAC protocols are classified into various categories. These are listed below:

• Contention based Medium Access Protocols: Contention based protocols for medium access provide flexibility as there is no need for message exchange. This may be important for many WSN applications as it does not require an infrastructure. This provides the scalability to the network but it may increase the collision probability as a function of node -S-MAC [START_REF] Ye | An energy-efficient mac protocol for wireless sensor networks[END_REF]: S-MAC protocol schedules the activity of a node such that it sleeps for a specific interval of time and awakes for the rest of time. S-MAC ensures that nodes within the transmission range synchronize according to a fixed sleep schedule. This is achieved using synchronization messages which are shown in figure 2.7. It consists of the node ID and the time until which the sender switches to the sleep mode. Unlike pure CSMA, it is not active for all the time so this reduces the energy consumption of the nodes.

-Low Power Listening (LPL) [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF]: In LPL, the main idea is to send a preamble before each packet in order to wake up the intended receiver.

The goal is to minimize the listen cost associated with the fixed duty cycle operation protocols. Each node periodically wakes up and check for any activity. If the activity is detected, it stays in receiving mode. Otherwise, it switches back to sleep state.

• Reservation based MAC Protocols: In this class of protocols, each node transmits the data during a reserved time-slot. This reduces the collision that increases the energy efficiency at a reduced throughput but there is a need to have a global synchronization. Time Division Multiple Access (TDMA) protocols have a reservation period that is used to reserve their time slot for communication through a centralized agent. This is shown in figure 2.8.

-Low Energy Adaptive Clustering Hierarchy (LEACH) [START_REF] Rabiner Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF]: It uses a TDMA based approach in a clustering network hierarchy. Each node in a cluster is assigned a time slot for data communication. the inter-cluster interference is managed using Code Division Multiple Access (CDMA) scheme.

-Traffic Adaptive Medium Access (TRAMA) [START_REF] Venkatesh Rajendran | Energyefficient collision-free medium access control for wireless sensor networks[END_REF]: It is a time slot based structure with a distributed scheme where pairwise communication between neighbors is performed for scheduled transmission slots. The superframe structure is shown in figure 2.9. It consists of signalling slots in reservation period and transmission slots in data period.

• Hybrid MAC Protocols: The third class of protocols combines the features of the two protocol classes described earlier. These protocols try to have the -Z-MAC [START_REF] Rhee | Z-mac: a hybrid mac for wireless sensor networks[END_REF]: It is a hybrid protocol that uses the knowledge of topology to improve MAC performance under high contention. The communication depends on a TDMA type solution but if a time slot is not used by a node, it can be taken by other node that needs it. Thus, it behaves like CSMA under low contention and as TDMA under high contention.

-Funneling MAC [START_REF] Gahng-Seop Ahn | Funneling-mac: a localized, sink-oriented mac for boosting fidelity in sensor networks[END_REF]: It is a hybrid MAC protocol that targets the choice of MAC based on the network traffic. As the traffic is directed towards the sink, therefore, there is a high traffic overhead near the sink. The CSMA protocol is used network wide but near the sink, TDMA protocol is used to avoid collisions. This created a funneling effect which is shown in figure 2.10.

The choice of MAC protocol depends on the data traffic rate as well as the network configuration. Our focus in this thesis is to analyze various routing approaches as it has a significant effect on the network energy consumption and the end-to-end delay. So we have considered a contention based MAC approach for analyzing these routing approaches in simulation. As in a medium scale network installed inside a building, the contention based protocol may increase the overall network throughput.

Multichannel Allocation for Interference Minimization

Most of the protocols listed above use single channel allocation for communication.

In case of high data rate applications, this strategy might not result in a high throughput due to increased interference and congestion risks. There is a need to use a multichannel allocation to minimize the interference and thus gain in terms of energy as well as throughput. The idea is to allocate multiple channels to the neighboring communication links so that the communication of one link doesn't interfere with the other. This is explained with the help of figure 2.11. If transceiver B wants to communicate with the transceiver A, it sends the data on a certain frequency say f1. The transceiver should be tuned to frequency f1 in order to receive the data. However, if transceiver C is also tuned on the same channel, it will receive this data as well. This may increase its energy consumption due to listening of data. However, if we use a design where transceiver C is tuned to a frequency other than f1, it will reduce the energy consumption of the associated node. This basic principle will be used to propose the multichannel design. But this type of channel allocation strategy brings the extra challenge of how to allocate the channel. This can be done offline as well as on network runtime. Both have certain advantages as well as disadvantages that are discussed below:

• Static Channel Allocation: In this type of channel allocation mechanism, the channel is allocated based on the channel condition at the time of initial network configuration. Thus, it is a simple technique and it can have better performance as compared to the single channel allocation design. But in case there is a change in channel quality this can lead to the decrease in network throughput. In [START_REF] Starobinski | Nearoptimal data dissemination policies for multi-channel, single radio wireless sensor networks[END_REF], [START_REF] Yen | Integrated channel assignment and data aggregation routing problem in wireless sensor networks[END_REF], we find the examples of static channel allocation.

• Dynamic Channel Allocation: In this type of channel allocation, the channel assignment is done at run-time based on the channel condition. This type of channel switching is needed when the channel condition change gradually or abruptly during run-time avoiding a decrease in the overall network throughput. But this approach includes an overhead of configuration packets that needs to be periodically sent before switching the channel. Some of the examples of dynamic channel allocation are [START_REF] Mo | Comparison of multi-channel mac protocols[END_REF], [START_REF] Bahl | Ssch: slotted seeded channel hopping for capacity improvement in ieee 802.11 ad-hoc wireless networks[END_REF] and [START_REF] Tzamaloukas | Channel-hopping multiple access[END_REF].

Cross Layer Design

The relationship between different layers can be used to enhance the network performance. These interactions are important for cross layer design in sensor networks and are confirmed by various studies such as [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: energy and latency performance[END_REF], [START_REF] Vuran | On the interdependence of congestion and contention in wireless sensor networks[END_REF]. For example, the low-power design depends on the energy consumed at the physical layer by packet communication. This fact can be taken into account by upper layers to form an efficient protocol design. In this section, we describe various approaches for cross layer design explained in the literature:

• MAC and Physical Layer: In [START_REF] Mehmet | Spatial correlation-based collaborative medium access control in wireless sensor networks[END_REF], spatial correlation in physical phenomenon is used for designing a medium access control protocol. Also, [START_REF] Ozlem | Mc-lmac: A multi-channel mac protocol for wireless sensor networks[END_REF] proposes a Multi-channel Medium Access Control protocol (MC-LMAC) . It makes use of interference and contention free parallel transmissions on different channels to maximize the wireless sensor network throughput.

• Routing and Physical Layer: [START_REF] Bai | An energy optimization protocol based on cross-layer for wireless sensor networks[END_REF] describes a cross-layer solution between routing and physical layer. It proposes a feedback algorithm that computes proper transmission power level between different nodes. Based on this information, the next hop path is selected. Thus, the physical layer information is used to make an appropriate routing solution that optimizes the energy consumption.

• Application, Network and MAC Layer: In [START_REF] Felemban | Mmspeed: Multipath multi-speed protocol for qos guarantee of reliability and timeliness in wireless sensor networks[END_REF], the application layer deadlines are used to prioritize the network traffic into various classes. This interaction is shown in figure 2.12. These traffic classes are prioritized so that the application layer deadlines can be fulfilled. This is fed into various MAC layer priority queues by the network layer and the routing is performed using the idea explained in [START_REF] He | Speed: A stateless protocol for real-time communication in sensor networks[END_REF].

Wireless Sensor Network Simulators

Designing new MAC or routing protocols or low power strategy need to evaluate their impact on global performance. This performance evaluation through the development of a sensor network could be complex and time consuming, thus simulation tools for sensor networks is generally considered for evaluating new sensor network related approaches. A number of wireless sensor network simulators are found during our search in order to identify a suitable network simulator fulfilling our requirements. Some simulators can be used for measuring the performance of a routing protocol with respect to the shortest path finding mechanism while a few of them focuses on finding the power efficient routing scheme for the given network scenario.

Objective Modular Network Testbed in C++ (OMNeT++) [START_REF] Varga | An overview of the omnet++ simulation environment[END_REF] is an objectoriented C++ based discrete event simulator. An OMNeT++ model consists of modules performing communication by passing messages. The active modules are known as simple modules and C++ is used to write them by utilizing the simulation class library. List of different simulation models available in OMNET++ are TCP/IP networks, Peer-to-peer networks, LAN/MAN Protocols and Ad-hoc, wireless and sensor networks. Some frameworks developed in OMNET++ are Mobility Framework (MF) [7] and Power Aware Wireless Sensor Networks (PAWiS) [START_REF] Pawis | [END_REF]. The Mobility Framework supports simulation of wireless and mobile networks within OMNeT++. This framework is intended to support wireless and mobile simulation within OMNeT++ and it implements the support for node mobility, dynamic connection management and a wireless channel model. On the other hand, the PAWiS Simulation Framework facilitates the simulation of wireless sensor networks as it includes the internal structure of the sensor nodes as well as the network connecting them. The WSN node in PAWiS is splitted into functional blocks like a physical, a MAC, a routing, an application layer, a CPU, timer, AD converters and so on. Each of these blocks are mapped to modules in simulation. The work flow is such that at the beginning the node is composed from one module implementation per module type from the module implementation library. Then the modules are configured and in the next step the model is simulated and the results are evaluated. Based on the results the individual models could be refined. Out of these frameworks, PAWiS is a suitable option for wireless sensor network simulation but there is a little technical support for this framework, furthemore it seems to be no longer under development.

Castalia [2] is a Wireless Sensor Network (WSN) simulator for early-phase algorithm/protocol testing built at the Networks and Pervasive Computing program of National ICT Australia. It supports channel and radio models, and provides support for defining physical processes. It also supports enhanced modeling of the sensing devices and other often-neglected attributes of a WSN such as node clock drift. In Castalia, channel/radio model is based on empirically measured data and multiple transmission power levels are available. It has a physical process model as well. It senses device noise, bias and power consumption. Node Clock Drift, ressource Monitoring, MAC Protocol with large number of parameters to use, designed for expansion and adaptation. TOSSIM [START_REF] Levis | Tossim: accurate and scalable simulation of entire tinyos applications[END_REF] includes TinyOS program simulation as well as a bit error radio model. SENSE [START_REF]Sense[END_REF] is a wireless sensor simulator that can be used by high-level users, network builders and the component designers. It uses component-port model which frees simulation model from inter-dependence. These simulation framework looks to be an interesting choice but lack of technical support is the main hurdle to utilize them for wireless sensor network research. NS-2 [8] is a discrete event network simulator and is used in the simulation of routing and multicast protocols, among others, and is heavily used in ad-hoc research. NS-2 supports an array of popular network protocols. Unlike the simulation platforms described above, the plus point of NS-2 is a large community that leads to the development of features that are needed for wireless sensor network research. That is why, we have chosen NS-2 for simulating our proposed approaches using it.

Power Consumption Model

A wireless sensor node has limited battery lifetime and the battery capacity consumption mainly depends on the transmission and reception energy dissipation. The main causes of transmission and reception is either when a node generates a packet for a particular destination, or it has to receive and forward the packet towards the destination or it receives a packet when it is in idle state and the packet is not destined towards it. Thus, these are the main energy consumption sources in a typical sensor node. This is explained in figure 2.13 taking the Micaz sensor node as a reference model.

The power consumption model that is usually used for evaluating the energy consumption is given by [START_REF] Akyildiz | John wiley publishing company[END_REF]:

E c = E tx (packet_size, distance) + E rx (packet_size)
where communication energy consumption E c depends on transmission E tx and reception E rx energy consumption of a packet. The transmission energy consumption depends on the distance as well as packet size while the reception energy consumption depends on the packet size only.

The NS-2 defines two parameters to know whether a packet has been received correctly or not. These are the Reception and Carrier Sense Threshold and it depends on the transmission power consumption for a packet. For receiving a packet, there are three cases which are described below:

• If the distance between sender and receiver is less than what specified by the reception threshold, the packet will be received correctly. In this case, energy will be consumed by the receiver for the packet reception.

• If distance is greather than reception threshold but less than carrier sense threshold then the packet will be received with errors. In this case, energy will be consumed for the packet reception at the receiver.

• If the distance is greater than carrier sense threshold, the packet will not be received. In this case, energy will not be consumed for the packet reception at the receiver.

This packet reception model considers the packet collisions due to physical layer interference. Thus, it can be used for evaluating the effect of a routing approach on transmission and reception energy consumption. As we have used a CSMA based MAC protocol for evaluating different routing protocols. The idle energy consumption can be ignored [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF] because it does not account for the routing protocol efficiency in presence of CSMA based MAC protocol. The NS-2 energy consumption modeling technique for sensor networks is verified in [START_REF] Courtay | Wireless sensor network node global energy consumption modeling[END_REF].

Conclusion

In this chapter, we have described the research issues associated with the design of sensor networks. The static network involved in the design of a disaster management application is considered. For this type of network, grid or cluster based network division can be considered. The role of the node responsible for data gathering and forwarding should be rotated after periodic interval of time to equalize the energy consumption. The geographic data forwarding approach such as XY routing is suitable for inter cluster or inter cell routing. For a data traffic having real time constraints, QoS data reporting techniques should be used that consider the energy consumption. Also, the multichannel capabilities can be used to increase the overall network throughput and minimize the delay. In the sequel, the dissertation will address all these topics. The next chapter targets the design of a network partition strategy using a grid based design where the role of cell head is rotated to balance the overall energy consumption.

Chapter 3

Virtual Data Dissemination Architecture In this chapter, we target to find an energy efficient data dissemination approach for the considered application. It targets the network architecture for limited data rate networks deployed in a building sensing temperature, humidity, etc. These nodes consist of devices having low battery and processing capabilities and they may consists of different type of sensor devices. Thus for a transmitted packet, each device may consume different amount of energy.

Virtual Data Dissemination Architectures

Energy efficient network management is of particular importance for sensor networks which consists of devices having limited battery capacity. The sensor networks are divided into various partitions such as equal sized cells using uniformly distributed grids which helps in better network management. [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF], [START_REF] Mir | A quadtree-based hierarchical data dissemination for mobile sensor networks[END_REF], [START_REF] Shin | Railroad: virtual infrastructure for data dissemination in wireless sensor networks[END_REF], [START_REF] Ben | A line-based data dissemination protocol for wireless sensor networks with mobile sink[END_REF], [START_REF] Rabiner Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF], [START_REF] Ali Khan | Analytical model for energy consumption analysis in grid based wireless sensor networks[END_REF], [START_REF] Kweon | Grid-based energy-efficient routing from multiple sources to multiple mobile sinks in wireless sensor networks[END_REF], are some examples that gives energy efficient network management solutions for sensor networks. The common approach in these solutions is a mechanism that divides the network into partitions and each partition has some nodes that are responsible for communicating most of the network traffic over the structure formed by these nodes. Here, we discuss one by one the structures generally adopted in literature.

• Railroad: It uses a structure in the form of a rectangle that is called the railroad [START_REF] Shin | Railroad: virtual infrastructure for data dissemination in wireless sensor networks[END_REF]. The nodes lying on this railroad architecture are responsible for the major network communication as the source node is mobile (illustrated in figure 3.1). Source notifies the event directly to the rail road nodes (communication 1 in figure 3.1). When a sink is in need of data, it will forward its query towards the nearest node of the railroad that will use the nodes lying on railroad to send the query towards the source (communications (2-1), (2-2) and (2-3) in figure 3.1). Then there is direct communication between source and sink for data transmission (communication 3 in figure 3.1).

• Line Based Data Dissemination (LBDD) : This protocol [START_REF] Ben | A line-based data dissemination protocol for wireless sensor networks with mobile sink[END_REF] allocates the nodes lying in a vertical strip as the responsible for major network communication. The sink sends the query towards the nearest node lying on the line.

The nodes lying on this line forwards the query towards the source. Thus, it is the structure that is responsible for sink-source network communication. But this creates the hot spots for the nodes lying on the line. This is depicted in • Grid Based Data Dissemination: There are a number of techniques that use the grid based data dissemination. Two-tier Data Dissemination (TTDD) [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF] describes the grid construction based on the detection of a new event.

The nodes of the grid are responsible for forwarding the query towards the source. In this approach, there is a need to form grid again and again if the source is mobile. However, the drawback is that static source will create hot spots in the network. Thus, the first analysis technique considered in the next section is similar to [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF] and it is called the static grid technique. The data communication from source to sink is explained in figure 3.4 (a). Gridbased energy-efficient routing (GBEER) [START_REF] Kweon | Grid-based energy-efficient routing from multiple sources to multiple mobile sinks in wireless sensor networks[END_REF] proposes such a grid based data The network is divided into equal sized cells using grid and each cell has a head that locally collects the data and also performs the task of inter-grid communication. In order to send the request, it is forwarded in the request quorum and the data is sent from source to sink in data quorum where a quorum is a column or row of cells. The request quorum lies along x-axis and the data quorum is along y-axis. The query forwarding process is explained in figure 3.4 (b). Energy-efficient data dissemination protocol (EEDD) [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF] presents a grid based data dissemination protocol for wireless sensor networks where the role of cell head is rotated whenever its energy is decreased below a certain threshold. As already discussed, this technique creates hot spots in the network as it changes the cell head only when their available energy is lower than the threshold value. Also, the approach in [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF] sub-divides each grid into four sub grids as explained in figure 3.4 (c) and allocates to each sub-grid a time slot for data collection. Three scenarios for data dissemination are considered. These are: (a) target location aware data dissemination (b) target area aware data dissemination and (c) target location unaware data dissemination. [START_REF] Jin | A energy efficient data-dissemination protocol with multiple virtual grid in wireless sensor network[END_REF] is an enhancement of [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF] where multiple virtual grids are formed by minimizing the original size of grid as explained in figure 3.4 (d). This helps in reducing the number of hops to destination. By this way energy is reduced but still there is not rotation of cell head and hot spots a created in the network. [START_REF] Liu | A grid-based distributed multi-hop routing protocol for wireless sensor networks[END_REF] tries to balance the energy consumption by rotating the role of cell head and by choosing a path having maximum available energy. But the learning process for choosing a minimum energy path is an energy consuming process. Also, the selected energy efficient path can increase the end-to-end delay. The resultant grid is illustrated in figure 3.4 (e). [START_REF] Zhuang | Energy-optimal grid-based clustering in wireless microsensor networks[END_REF] presents a grid based data dissemination such as the one explained in figure 3.4 (e). In this technique, an election based cluster head selection mechanism is employed to balance the energy consumption that is similar to Figure 3.4: Grid Based Data Dissemination Techniques [START_REF] Rabiner Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF]. However, periodic election may not be useful in case of heterogeneous network.

Problem Formulation

In this chapter, two grid based data dissemination architectures to minimize the hot spot problem are proposed. As explained earlier, there is a need to divide a large scale network into small regions using grids which are called the cells for better network management as the task of data forwarding is assigned to each cell. One such network is shown in figure 3.5. If we consider only one cell as shown in figure 3.6, then there will be a node that is responsible for gathering the data from the nodes as well as it will be responsible for forwarding the packets received from neighboring cell heads. In figure 3.6, there are four nodes in each cell (triangle, square, circle and pentagon) which have sufficient energy to become the cell head candidate. The target is to explore different strategies of cell head selection and find which strategy is better for which scenario.

In this chapter we propose Dynamic Grid Based and Load Balancing Based Data Dissemination Schemes. Their energy consumption analysis is compared with a Static Grid Based Scheme whose grid formation technique is similar to [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF], [START_REF] Jin | A energy efficient data-dissemination protocol with multiple virtual grid in wireless sensor network[END_REF] and [START_REF] Youn | Efficient data dissemination and aggregation in large wireless sensor networks[END_REF]. These schemes are also compared for the cases of heterogeneous as well as homogeneous networks and utility of each scheme is illustrated for a specific scenario.

Grid Based Data Dissemination Techniques

In this section, three classes of grid based data dissemination techniques are detailed. The first scheme is recalled from the literature and the other two schemes are proposed for optimizing the energy consumption.

Technique 1: Static Grid Algorithm

As explained earlier, the first algorithm is based on a fixed cell head selection and it is named the static grid approach and is similar to [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF], [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF], [START_REF] Youn | Efficient data dissemination and aggregation in large wireless sensor networks[END_REF]. As shown in figure 3.5, the network is divided into equally sized cells using uniform grids based on the antenna range. Each cell consists of only one cell head. This cell head is responsible for local data collection as well as its onward transmission towards the sink. Figure 3.6 shows one typical cell but for this case there will be only one cell head and the rest of the nodes act as the member nodes which direct the data towards the cell head for onward transmission towards the sink. Thus, the source sends the data towards its nearest cell head which sends the data towards the sink's cell head using XY multi-hop routing. In this mechanism, the node which has to forward the packet will analyze its geographical coordinates with the destination node's coordinates. First, the packet is forwarded in x-direction until x-coordinates of the current cell head's equals x-coordinates of sink. Then, it will be forwarded in y-direction, until the y-coordinates of the current cell head equals the y-coordinate of the destination. Thus, packet reaches at the sink's cell head which will then forward the packet towards the sink.

Sensor Nodes

Sink

Figure 3.5: Grid Based Network Division

Routing techniques in static grids is expected to create hot spots in the homogeneous as well as heterogeneous network because it overloads the single cell head.

Technique 2: Cooperative Load Balancing Algorithm

The second approach is based on a cooperative load balancing technique where each cell head transmits the data based on its remaining battery capacity and the transmission energy consumption. A cooperative algorithm is proposed which performs the load balancing with respect to the transmission energy consumption of each potential cell head. For using such a scheme, the packets are sent by a node towards the cell head within its region. Then based on the packet forwarding capacity of each potential cell head, only one (square, triangle, pentagon or circle node shown in fig- As shown in figure 3.6, each region has four nodes that are responsible for forwarding the data. If we consider only one cell and the backbone nodes have different energy profiles then the load of packet forwarding should be equally divided. For example, assume an energy capacity of forwarding the packets by each node is 7, 4, 2 and 10 packets respectively for circle, triangle, pentagon and square nodes. Assume also that the cell forwards 8 packets in each round. Using the load balancing algorithm, circle, triangle, pentagon and square nodes will forward 3, 1, 0 and 4 packets, respectively. After using such an algorithm, the energy capacity of each node will be 4, 3, 2 and 6 packets. Thus, the energy consumption of each node will balance out using the cooperative load balancing scheme which will increase the lifetime of the network.

For the sake of periodically determining the remaining packet forwarding capacity of each potential cell head, extra control packets have to be transmitted. These consists of broadcasting node's capacity based on remaining battery capacity and energy consumption to forward each packet. Based on this announced value, current cell head will evaluate and broadcast the capacity of all the potential cell heads. The role of cell head will be rotated once a cell head is reached its limit to forward the calculated number of packets. This rotation will be done using a technique similar to token ring approach.

A system having n nodes is considered and each node knows its battery capacity and energy consumption to transmit a packet. Based on this information, they decide the percentage of load distribution for packet forwarding.

Let η be the total packet arrival at the cell. The total packet forwarding capacity of each node is given by µ i for the same interval of time. The total packet forwarding capacity µ i depends on the battery capacity and the average energy needed to send a packet. If E i (β i ) denotes the expected energy consumed by the node to forward β i packets, we express the optimization problem as follows:

minE i (β i ), i = 1, ..., n subject to: β i ≤ µ i , i = 1, ..., n n i=1 β i = η
The first constraint describes the stability condition while the second is the conservation law.

Inspiring from [START_REF] Grosu | Load balancing in distributed systems: An approach using cooperative games[END_REF], the solution for the considered problem is obtained by solving the following optimization problem:

max n i=1 ln(µ i -β i ) subject to: β i ≤ µ i , i = 1, ..., n n i=1 β i = η
In order to get the solution for the load balancing cooperative problem, it is solved first without requiring the number of packets forwarded by a node (β i ) to be greater than its packet forwarding capacity (µ i ).

The solution to the optimization problem without the constraint β i ≤ µ i is given by:

β i = µ i * η n j=1 µ j
However, this solution cannot give guarantee that β i ≤ µ i for all nodes. A way to walk around this problem is to not include a node i for doing the packet forwarding when µ i ≤ η n . This is due to the fact that a node such that µ i ≤ η n is dead or cannot be used for doing the packet forwarding task. The algorithm solving the load balancing cooperative problem is depicted in Algorithm 1.

It is expected that this scheme will perform better for a heterogeneous network due to the extra control overhead that determines the optimal amount of traffic that each cell head should forward. This strategy can also be used in a cluster based sensor network where the role of cluster head is rotated after some interval of time.

Technique 3: Dynamic Grid Algorithm

In the previous technique, the cell head is selected in each cell so as to do a load balancing according to the energy capacity of each node in the cell. For this technique, rather than considering a fixed grid in which cell heads are selected, we consider a set of dynamic grids which determines as many as cell heads actuated in a periodic scheme. This scheme tries to rotate the role of cell head nodes for data forwarding in a grid based data forwarding mechanism. It divides the network into equally spaced grids where nodes of each grid are responsible for communication after periodic interval of time. Virtual grid formation and periodic shift of grid role for data forwarding is explained below.

Virtual Grid Construction

From a set of n nodes, N grids are formed in the network as illustrated in figure 3.7.

Each grid has a cell size of c and distance between two neighboring grids is delta_c such that c = N x delta_c. Only one virtual grid is active at any time and that grid has the responsibility of inter-cell communication.

The position of the active virtual grid will change with respect to a predefined time period. Accordingly, the cell head will change as a function of virtual grid position at a particular time. The nodes nearest to the crossing points of the grid lines will be chosen as cell heads for the inter-cell communication. For example, in figure 3.7 if we consider a value of period T equals to 10 seconds, then active interval times of each virtual grid could be:

0 ≤ t0 ≤ 2.5sec 2.5 ≤ t1 ≤ 5sec 5 ≤ t2 ≤ 7.5sec 7.5 ≤ t3 ≤ 10sec
For time interval T+t0, circle nodes are active and responsible for backbone communication. Similarly, triangle nodes, pentagon nodes and square nodes are responsible for backbone communication between time intervals T+t1, T+t2 and T+t3 respectively. The nodes of currently active grid will act as cell heads. If a sink or source node wants to communicate, it will first communicate with its cell head which is the nearest node on the currently active grid. Thus, the idea of grid based dynamically changing cell head structure is to have more than one grid for inter-cell data communication. Thus in figure 3.6, each potential cell head will remain cell head for equal amount of time or alternatively, each will forward the equal amount of packets thus equalizing the energy consumption of the cell heads. This is the special case of cooperative load balancing algorithm as:

µ 1 = µ 2 = ... = µ n = µ
and thus we get

β i = µ i * η n * µ as µ i = µ ⇒ β i = η n

Packet Forwarding Mechanism

The packet forwarding mechanism is based on XY routing technique applied on a grid network. As the active virtual grid change periodically some adaptation are necessary, they are illustrated through the example of figure 3.8. We consider at time t 1 , the nodes on the grid which are responsible for communication (figure 3.8 (a-b)) are denoted by g 1 and the nodes responsible for communication at t 2 are denoted by g 2 . When g 1 is responsible for communication, then the packet forwarding mechanism is described in figure 3.8(a). The query is sent from sink to its cell head of grid g 1 as depicted by step (1). In step ( 2) and ( 3), the query is sent from sink's cell head to the source's cell head. In step (4), the query is forwarded from source's cell head towards the source. The same process is repeated to forward back the data from the source to the sink. Now, when g 2 is responsible for communication, then the packet forwarding mechanism is described in figure 3.8(b) using the same algorithm. Assume now that a query is generated by the sink at time t 1 + ∆t < t 2 . The query will follow the grid g 1 responsible for communication at this time. If at time t 2 when the active grid swaps from g 1 to g 2 the query which is routed on grid g 1 continues on that grid until it reaches its destination. This choice allows the routing algorithm to be simplified even if the energy consumption is not totally balanced in that case. The same situation occurs when the grid changes whereas the data is sent backwards to the query node. In this manner this protocol tries to send equal number of packets on each grid. This way it evenly distributes the communication energy on all the nodes of the network. As a result, the probability of sudden death of a node decreases which helps in removing the hot spot problem. This scheme has no control overhead so it is expected to have better energy consumption profile for homogeneous network and not for heterogeneous networks. When the network consists of heterogeneous nodes having variable lifetime, the problem of energy balancing between nodes remains can be tackled by using a cooperative load balancing algorithm.

Comparative Energy Consumption Analysis

Analysis Technique

To perform a comparative analysis of all above mentioned techniques, a specific case is used where the static cell head is lying at the center of the cell. An analysis is performed by considering one cell where each cell consists of member nodes (as per figure 3.6). Some of the nodes have sufficient amount of energy which make them candidate for the cell head selection and the others can only generate useful Thus, the energy consumed by the cell head and cell member is given by:

E cellhead = E packets_received + E packets_f orwarded (3.1) E member_node = E packets_sent (3.2)
Algorithm 2: Cooperative Load Balancing Algorithm

In order to estimate the energy cost per communication for cooperative load balancing algorithm, we consider the following activities:

• Locally Generated Packets

• Energy Notification Packets sent by cell members for Algorithm Execution

• Cell Head notification messages

• Packets received from neighboring nodes for onward transfer

The energy consumed by the cell head and the cell member is given by:

E cellhead = E packets_received + E packets_f orwarded (3.
3)

E member_node = E packets_sent + E notif ication_packet_received (3.4)

Algorithm 3: Dynamic Grid Algorithm

In order to estimate the energy cost per communication for dynamic grid algorithm, we consider the following activities: The energy consumed by the cell head and cell member is given by:

E cellhead = E packets_received + E packets_f orwarded (3.5) E member_node = E packets_sent (3.6)
The figures 3.9(a) and (b) explains the type of packets processed by a cell head of static/dynamic and cooperative load balancing schemes respectively.

Energy Consumption Analysis Results

The energy consumption analysis is performed by considering the network to be a homogeneous as well as heterogeneous network and then perform the analysis. The analysis considers different power levels for intra cell communication and inter cell communication. The analysis parameters are detailed in table 3.1 and the energy consumption profile of each node is similar to the one used in [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF], [START_REF] Jin | A energy efficient data-dissemination protocol with multiple virtual grid in wireless sensor network[END_REF], [START_REF] Youn | Efficient data dissemination and aggregation in large wireless sensor networks[END_REF]. The results of analysis are shown in table 3.2 and 3.3. These results show that heterogeneous network consumes more energy as compared to the homogeneous one. Also, the static scheme gives the worst energy consumption results and creates hotspots in the network. Dynamic scheme has less energy consumption in case of homogeneous network as compared to heterogeneous one while the load balancing scheme performs better for heterogeneous case. If the value of maximum energy difference between two cell heads is less, it tells that the energy consumption profile of the cell heads is same thus the possibility of hot spot creation in the network is minimized. Thus for heterogeneous networks, load balancing scheme minimizes the hot spots but dynamic scheme is unable to do so while for homogeneous both the techniques are able to minimize these hotspots.

Incoming

Simulation Results

In this section, the proposed techniques are compared with the static grid technique which is based on the idea of [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF], [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF], [START_REF] Youn | Efficient data dissemination and aggregation in large wireless sensor networks[END_REF]. In this section, the comparative simulation results obtained using NS-2 are discussed. In the first subsection, the single cell case that only considers the intra cell traffic is discussed and the second subsection details the results after including the intercell traffic. The simulation parameters are listed in table 3.1 and the energy consumption profile of each node is similar to the one used in [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF], [START_REF] Jin | A energy efficient data-dissemination protocol with multiple virtual grid in wireless sensor network[END_REF], [START_REF] Youn | Efficient data dissemination and aggregation in large wireless sensor networks[END_REF] as well as in the analytical analysis. The network size is 30m x 30m, a CSMA based protocol is used at MAC layer and XY routing technique performs inter cell communication. It is assumed that each sensor node knows its geographical position, the value of BER inside a cell is constant and the cell size is constant. The data packet are generated by each sensor node after 0.2 sec destined towards the sink.

Single Cell Network -Intra Cell Traffic Analysis

In the first step, a single cell with four cell head and four member nodes is considered where the role of cell head is changed based on the criterion for each scheme. The cell head collects the locally generated packets as well as the packets sent by the neighboring cell heads and forward it towards the sink. The average cell head energy consumption for the three schemes as function of data generation timer is given in tables 3.4 and 3.5. Where, data generation timer is the time period after which the data is generated from each source. which Static scheme has the worst energy performance but dynamic and load balancing scheme have the similar average energy consumption results. Notice the results of analysis technique in previous section conclude to a similar relative behavior in energy consumption. However, the maximum energy difference between two cell head at the end of simulation is given in tables 3.6 and 3.7. If the value of this factor is low, it tells that the energy consumption profile of the cell heads is same thus the possibility of hot spot creation in the network is minimized. This parameter shows that load balancing scheme has better profile in heterogeneous network (the nodes have different transmission energy consumption) while dynamic has better profile in the case of homogeneous network (the nodes have similar transmission energy consumption). This is due to the fact that load balancing scheme has extra overhead for determining the optimal number of packets forwarded by a cell head. This extra control is not very useful for homogeneous network case but its effectiveness is proven in heterogeneous network case.

Multiple Cell Network -Inter Cell Traffic Analysis

The next step is to perform the simulation for a larger network as shown in figure 3.10. Each member node generates the periodic data that is directed towards the sink located in cell 0. XY routing approach has been used for forwarding the data packets towards the destination cell. The simulation results are plotted in figures 3.11 and 3.12 and tabulated in table 3.8. The results show that closer the cell to the cell containing the sink consumes more energy because it has to transfer more packets. Also, the static scheme has multiple hot spots due to the presence of only one head within a cell. The energy consumption profile for heterogeneous network is better for load balancing based scheme while cell heads using dynamic scheme have irregular energy consumption profile. However, for homogeneous network the dynamic scheme performs a bit better than load balancing scheme. This outcome authenticate the single cell simulation and analytical results.

The average delay is the measure of time taken by a packet generated from cell 2 to reach the sink located at cell 0. This value is worst for the dynamic scheme because it changes the cell heads quite rapidly, thus it results in increased delay due to scheduling delay between the two cell heads. The average delay for static and load balancing scheme is nearly same due less frequent change of cell head.

Conclusion

In this chapter, three data dissemination techniques in grid based sensor networks were analyzed for homogeneous as well as heterogeneous cases. The first scheme is recalled from the literature and the other two schemes were proposed for optimizing the energy consumption. The results show that static scheme has worst energy consumption profile. On the other hand, dynamic scheme performs a fine load balancing in homogeneous networks but at the cost of increased delay. However, for heterogeneous network its performance deteriorates and here the load balancing schemes performs better. Thus in spite of it adds the extra overhead of periodic load determination for each cell head, it helps in equalizing the energy consumption of the cell heads. We can use dynamic scheme in a homogeneous network and load balancing scheme in a heterogeneous as well as heterogeneous network for balancing the routing energy consumption. However, these energy efficient data dissemination techniques that are proposed for grid based sensor networks may not perform efficiently when there is a application layer real time deadline for multimedia applications. For disaster management application, the part of the network that performs the video monitoring task has realtime data reporting deadlines as well as Wireless multimedia sensor networks can be used in video surveillance applications for disaster management inside buildings. To make sure, efficient, reliable and low power routing, various metrics are proposed. It is generally assumed that network consists of homogeneously distributed nodes having no physical obstruction. However, in application of building automation there exists walls and physical obstacles resulting in increased signal distortion and path loss. Thus, existing energy efficient data routing solutions cannot be directly applied to this application class because they may not obey the realtime deadline of the application. In this chapter, we propose an adaptive routing metric which helps in minimizing the energy consumption as well as meeting as much as possible the realtime deadlines of the application. The proposed metric is compared with energy efficient and QoS aware data routing metrics using NS-2 simulation environment.

Introduction & Related Work

For efficient communication in wireless sensor networks, various network division approaches such as clustering is used. The main objective of clustering is to achieve scalability, load balancing and fault tolerance. In the case of video surveillance application within a building, the existing solutions will form the clusters based on the geographical locations of the nodes and not on the physical channel conditions between the nodes. Thus, they may form clusters which will include a wall or physical obstruction which may increase the communication energy consumption of some cluster nodes. On the other hand, the existing solutions for inter cluster routing propose the metrics that may be either QoS aware or energy efficient. In case of energy efficient routing scheme, the traffic will be forwarded towards the minimum energy path. This routing scheme may choose a path for a packet that minimizes the occurrence of a wall or physical obstruction in its way but may increase the end-to-end delay. While, the QoS aware inter cluster routing algorithm may choose the path based on the application deadline that might include paths having many physical obstructions. Thus, techniques that may increase for specific timed constraint purpose in increase of the overall energy consumption of the network could be considered. In this section, various clustering mechanisms and routing metrics that can be used for multimedia streaming applications for disaster management inside the buildings are addressed.

Clustering

There is a wide range of research done in the field of clustering for managing the wireless sensor networks. In [61], the authors describe the unequal clustering mechanism that tries to do the load balancing near the base station. This is so because there is a large volume of traffic that the clusters near the sink have to forward towards the sink. But it may not be directly applied to the building automation application where there is a need to have clustering based on the geographic location of nodes. This type of clustering mechanism is shown in figure 4.1. [START_REF] Wang | Attribute-based clustering for information dissemination in wireless sensor networks[END_REF] forms the hierarchical clusters based on the geographical location but it requires to have an efficient application running on the top of sensor nodes. [START_REF] Ding | Distributed energy-efficient hierarchical clustering for wireless sensor networks[END_REF] proposes a weight based hierarchical clustering where weight depends upon the energy as well as distance from the neighbors but its performance may decrease in presence of physical hurdles between different nodes. Unlike these schemes, we propose the cluster formation procedure based on the physical channel condition of the building because it may reduce the energy consumption inside a cluster for local data gathering.

Routing Metrics

The existing solutions that can be used for inter-cluster routing are either QoS aware or energy efficient approaches. In [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF] and [START_REF] Kweon | Grid-based energy-efficient routing from multiple sources to multiple mobile sinks in wireless sensor networks[END_REF], energy efficient routing mechanisms are defined. These protocols find the energy efficient path to the sink but they may not meet the realtime deadlines of the packet. On the other hand, SPEED [START_REF] He | Speed: A stateless protocol for real-time communication in sensor networks[END_REF] presents a realtime communication protocol that uses geographic routing to find a path that attains a specific speed. The speed is calculated as shown in figure 4.2. The node i sends the packet to j rather than the final destination k if forwarding to j maintains a specific speed. The speed is calculated by dividing the distance that a packet has to travel from j to k by the estimated delay to j. If this calculation ensures the required speed, it will choose it otherwise it will forward it to the final destination. [START_REF] Felemban | Mmspeed: Multipath multi-speed protocol for qos guarantee of reliability and timeliness in wireless sensor networks[END_REF] enhances [START_REF] He | Speed: A stateless protocol for real-time communication in sensor networks[END_REF] for the multimedia traffic. It maintains different paths for achieving a specific speed based on the application requirement. Thus, the packets are assigned the path based on their speed requirement. The speed calculation method is similar to the SPEED protocol. In [START_REF] Vehbi | A real-time and reliable transport (rt) 2 protocol for wireless sensor and actor networks[END_REF], the contribution targets the congestion control and timely delivery of the packet. All these approaches target a realtime traffic objective but have little provision for energy efficiency. In [START_REF] Akkaya | An energy-aware qos routing protocol for wireless sensor networks[END_REF], energy and QoS aware routing is proposed that tries to equalize the throughput of each link by meeting the application QoS requirements. But if each link transmits at different power level, this approach will no longer be an energy efficient approach as it does not consider different power levels for data transfer.

Cluster Formation Phase

In this section, the cluster formation procedure in the sensor network is detailed for the application of video monitoring in a building. The clustering process uses the physical layer information to form the clusters.

Clusters correspond to physical partitions between the nodes and it tries that between member nodes and cluster head, there is no low quality channel. The physical partitions reduce the link quality between two nodes thus a higher transmission power is needed to have the same packet error rate at the receiver [START_REF] Rappaport | Prentice hall. Wireless Communications: Principles and Practice[END_REF]. The Link Quality Indicator (LQI) is a good measure of knowing the environment conditions between different nodes as average LQI is a good measurable indicator of the packet reception probability [42]. It will help in detecting the channel conditions between different nodes. An example of building having sensor nodes is shown in figure 4.3. We assume that each node knows its geographical location, is stationary and do not move during the course of cluster formation. We also assume that nodes are located in only one floor of the building. The antennas attached to these nodes can transmit with multiple fixed power levels to achieve a required Signal to Noise Ratio (SNR) at the receiver end.

The clusters will be formed so that there is no wall between different members of the cluster which is not the case with the existing cluster formation solutions. Thus, node groups 1-8, 9-14, 15-21, 22-25 and 26-29 (4.3) may form one or more than one clusters so that within a cluster each node has to transmit one hop at its lowest power level to reach its cluster head. An algorithm similar to [START_REF] Rabiner Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF] can be used to balance the load of data gathering locally in a cluster or cell.

Inter-cluster Routing

This section describes how to forward the packet from cluster head to the sink under delay and energy constraints. From here onwards, we will only consider the cluster head nodes involved in communication consisting of multimedia traffic having real time deadlines. The different steps needed to perform the routing are detailed below.

Initialization

After neighbor discovery and LQI measurement of each link, the base station starts the route discovery phase. Each node has a finite sized queue which is the bottleneck to forward the packet towards the next hop. The average value of the end-to-end packet forwarding delay is estimated which will be used for our QoS Aware Energy Efficient Routing. This time depends on the MAC layer buffer delay as well as the The base station will send a packet to the nodes that can communicate with it. This packet will be sent by the neighboring nodes towards their neighbors until it is disseminated till the end of the network. This packet will contain the energy required to send the packet to the sender node as well as the cumulative delay from sender to the receiver. Once this process is completed, each node knows the average case cumulative delay as well as the cumulative energy required by the packet to reach the sink by various available paths. This information will help in making routing decision.

Routing Table

The initialization phase help in maintaining a routing table at each node. Each node will have the information of number of hops, total energy required and average case cumulative delay for each path. This will help in making the final decision for routing.

QoS Energy Aware Routing Metrics

This is an important part of the algorithm as the routing metric will help in achieving the goal of energy efficient and QoS aware routing. Various other routing metrics have been described in literature depending on the application requirement. We explain a routing metric to achieve energy efficient QoS aware routing. This routing metric depends on the type of the packet. It classifies different paths with increasing cumulative energy consumption. It chooses that path which consumes minimum amount of energy but it also obeys the end to end deadline of each packet. If a path gives the minimum energy path but don't obey the end to end deadline requirement of the packet, then it will not be chosen. Rather, another path whose cumulative average delay is less than or equal to the packet end to end deadline and that has minimum cumulative energy consumption is chosen. Thus it will not only help in minimizing the overall energy consumption of the network but on the other hand it attempts to respect the end to end deadlines for each packet. This algorithm is listed in Algorithm 2 and elaborated below with the help of an analytical example. In this part, the protocol approach is elaborated with the help of an analytical example. The analysis is based on the energy consumption by each node and the delay faced by each packet. The delay is modeled using two factors, the first one is the buffer delay at each node and the second one is the transmission time at the MAC layer. The end-to-end delay for a given path having M-hops towards the sink is given by:

T Actual = M k=1 t k and t k = t k_buf f er + t k_transmission
where t k_buf f er is the buffer delay at each node and t k_transmission is the time taken by MAC layer to transmit the packet to the next hop. For example, the transmission delay consists of the time to access the channel as well as to successfully transmit the packet on the channel for the 802.11 MAC protocol. The expected transmission time [START_REF] Bouabdallah | On balancing energy consumption in wireless sensor networks[END_REF] is given by:

E[T (k, n)] = d(k, n) + b(k, n) + s(k, n) + c(k, n)
where:

• d(k,n) is the average time taken for a successful transmission of a packet from sender k to receiver n.

• b(k,n) is the average time spent by the node k in backoff state when it waits to transmit a packet.

• s(k,n) is the time taken by the neighborhood nodes sharing the channel with k for successful transmission.

• c(k,n) is the number of times the unsuccessful transmission is done by k between two successful transmissions.

Note that in this delay analysis propagation delay is neglected because it is much less than the time to access the channel.

The average transmission delay [START_REF] Lee | Dynamic power efficient qos routing algorithm for multimedia services over mobile ad hoc networks[END_REF] at a node is calculated by:

t k_transmission = RT T 1 -p
where RTT is the round trip time between sender and receiver and determined by:

RT T = (1542 + 8L DAT A_M AC R DAT A × 10 -6 s)
where L DAT A_M AC is the packet size and R DAT A is the data transfer rate. The probability that the packet is lost is given by:

p = 1 -(1 -p ACC ) × (1 -p CT S ) × (1 -p ACK )
where p ACC is the probability of channel access failure, p CT S is the probability that Clear to Send (CTS) packet is not received after the Request to Send (RTS) packet is sent and p ACK is the probability that ACK packet is not arrived after sending the data packet. The queueing delay [START_REF] Lee | Dynamic power efficient qos routing algorithm for multimedia services over mobile ad hoc networks[END_REF] at node is determined under the assumption that packets arrive according to Poisson process with rate µ.

t k_buf f er = µ × (1 + p) × RT T 2 j 2 × (1 -p) × (1 -p -µ × RT T j )
The problem is to find the next hop such that cumulative transmission energy consumption per packet is minimized and such that T Actual ≤ T E2E where T E2E is the deadline for a packet to reach the base station. As shown in figure 4.4, we assume each node can be the head of a cluster and is responsible for data transmission to the sink. The packet generated from the node located at the far end of the network is potentially the one which has the longest delay to reach the base station. The figure 4.4 shows two high speed paths (fast path 1, 2) having higher energy consumption for packet transmission and two low speed paths (slow path 1, 2) that need less energy to forward the packet. This could occur for example when nodes are physically located near to each other but due to physical obstacles [START_REF] Rappaport | Prentice hall. Wireless Communications: Principles and Practice[END_REF] it needs high transmit power to have a required PER at the receiver. We define these paths as: P ath s is the slowest path through Nodes 4 and 10 P ath f is the fastest path P ath sf is the path through Node 4 and using Fast Path 1 P ath f s is the path through Node 10 and using Fast Path 2 The problem is to find the optimal path in terms of energy consumption as well as which meets the application end-to-end deadline which could require to travel through some of the high speed path. We have to compute the number of high speed, high energy paths that the packet has to travel based on its end-to-end deadline and the delay model. Here, we assume that the packets generated from node 1 will suffer the worst case delay. If following the slow paths P ath s , the packet will not be able to meet the deadline, then it will traverse the high speed, high energy path P ath f . The analysis parameters are listed in table 4.1 and the results of the analysis are presented in table 4.2. This table shows the impact of choosing one fast path and one slow path (P ath sf or P ath f s ), two fast paths P ath f and no fast path P ath s to transfer a packet generated from node 1, on network energy profile as well as the end to end delay of the packet. This analysis shows that the routing metric helps in choosing an efficient path which not only helps in meeting the deadlines but minimizing the overall energy consumption of the network. This is the basics of the routing approach defined in the Algorithm 2.

Performance Analysis

In this section, the performance analysis of different routing metrics is described. The simulation environment is NS-2 and we shall describe the routing metrics with which the proposed metric is compared, average case delay estimation procedure and the simulation results. The network parameters are listed in table 4.3 and the network that is simulated is shown in figure 4.5. The energy consumption parameters are similar to the ones used in [START_REF] Luo | Ttdd: twotier data dissemination in large-scale wireless sensor networks[END_REF] that considers the transmission and reception energy consumption of a sensor node.

Routing Metrics

The following routing metrics are used to compare with the proposed routing metric: [START_REF] Zhou | An energy-efficient datadissemination protocol in wireless sensor networks[END_REF], [START_REF] Kweon | Grid-based energy-efficient routing from multiple sources to multiple mobile sinks in wireless sensor networks[END_REF] This metric chooses the path that has minimum cumulative transmission energy. This is the sum of energy needed by the packet to reach the sink. If more than one energy efficient paths are available then the protocol will rotate the role of data transmission between different paths in order to have the load balancing between different routes. Thus it tries to optimize global as well as local energy consumption of the node. This metric is evaluated in the initialization phase. [START_REF] He | Speed: A stateless protocol for real-time communication in sensor networks[END_REF], [START_REF] Felemban | Mmspeed: Multipath multi-speed protocol for qos guarantee of reliability and timeliness in wireless sensor networks[END_REF] This metric chooses the next hop path that has the minimum cumulative delay. It is the sum of average case delays that a packet is expected to have by choosing a specific route. Thus it chooses the path that is expected to have a minimum delay. This metric is evaluated in the initialization phase.

Minimum Cumulative Delay Routing

Delay Estimation

The average case delay on a node is estimated by lancing a simple simulation using NS-2 where node 1 is sender and node 2 is the receiver. The node 1 sends a packet periodically towards the node 2 and node 2 returns it back to the node 1. Initially the number of packets sent in the burst is set to 75% of the buffer size. It is then gradually increased to a point where the packet faces maximum delay. This gives the worst case round trip time. The average of the initial delay value and the worst case value gives us the average case delay that a packet is expected to have on a node which is set to be the initial end-to-end delay. After that, each node periodically updates this value by sending a packet towards the next hop neighboring node which contains the information regarding packet generation time. On receiving the packet, the neighboring node replies by sending the estimated delay from this node to reach the sink. This estimated value, round trip time as well as previous estimated delay value help in estimating the average end-to-end delay from the sender node. This periodic delay estimation helps in updating the end-to-end delay value thus making it an adaptive routing metric that changes with respect to network conditions. This process is explained in the figure 4.6. The period for this delay estimation can be evaluated for a network by considering a period that minimizes the energy consumption for the node that consumes maximum amount of energy and that has maximum traffic load. In the considered network, it is node 4 and the table 4.4 shows its energy consumption for the proposed routing metric as a function of fraction of delay estimation period over data packet generation period. The delay estimation period that minimizes the energy consumption is chosen for evaluation.

Simulation Results

Each node generates a packet having a real time deadline after a period of 5sec and it is directed towards node 1 (sink). The direct link between nodes 9 and 5 as well as between 5 and 1 are high energy links. These links give the high speed path in order to meet the end to end deadline of a packet but on the other hand, they have a high energy associated with them (4 times the minimum power to transmit the packet). Thus it will only be used if the estimated average case time to reach the sink is less than the deadline of the packet. The simulation results are plotted in figures 4.7-4.10. Figure 4.7 plots the remaining time to deadline for a packet (laxity) generated from node 9 when it is received at the sink. It explains that QoS energy aware routing is comparable to minimum cumulative delay routing when the application has lower end to end delay but its delay increases when end to end deadline is large and it starts optimizing the energy. Figure 4.8 plots the average leftover energy for each node of the network at the end of the simulation and it shows that in low deadline values, average energy profile is not as good as with high deadline values. Again, it explains the fact that in order to meet the deadlines, the protocol chooses the path having high energy but it chooses low energy paths when it has large end-to-end deadline. Also at lower application deadline values, the average leftover energy per node is even lesser than the minimum cumulative delay routing metric. This is due to the overhead of periodic end-to-end delay estimation messages. Figure 4.9 plots the minimum leftover energy of a node of the network at the end of the simulation while figure 4.10 plots the maximum leftover energy difference between any two nodes of the network at the end of the simulation. Figures 4.9 and 4.10 explain whether the energy is uniformly consumed by all the nodes of the network during the simulation and QoS Energy aware protocol scores low in low deadline values but it starts performing well in high deadline values. This is due to the reason that the proposed adaptive metric tries to meet the end-to-end deadline as a first priority.

Interference Region Minimization

Increasing the transmission power increases the interference region of the antenna. This increase in power level helps in meeting the real time deadlines but increases the reception energy consumption of cluster member nodes. The average listening energy consumption for a member node of the network shown in figure 4.5 are listed in table 4.5. These values are computed for a 50 bytes packet generated from far away cluster for an ideal MAC Protocol. If we assume a perfect multichannel design where each cluster is assigned a unique channel for communication and the transmission of each cluster do not interfere with each other, then this listening energy consumption can be decreased. This is shown in table 4.5. This table show that the average reception energy for the designs targetting real time deadlines is higher than low energy design. But if we have an ideal multichannel allocation where each cluster has unique channel allocation, this can significantly reduce the energy consumption for the real time designs in comparison with low energy design.

Conclusion

The chapter presents cluster formation and intercluster routing mechanism for building automation application. In this application, the clustering is performed between network nodes that have no physical boundary between them. The intra cluster packet forwarding is one hop routing and the inter cluster routing is done by taking into account the Link Quality Indicator between different nodes and the application layer deadline. The proposed routing metric performs well under different application deadline cases as it takes into account the effect of congestion on a particular path by periodically estimating the delay values and the uneven energy consumption on different paths by using LQI value. The approach is validated by simulations in NS-2 for varying packet delivery deadlines. This design can be enhanced by using a multichannel allocation. This will increase the design complexity but it will help in reducing the energy consumption due to interference. The video surveillance applications for disaster management usually employ single channel design approach whereas at a given instant several video or image streams should be delivered in the meanwhile. However, the available antennas for numerous sensor devices support multiple channels that can be used for the network design.

Based on the channel conditions, more than one channels for the clustered sensor network design can be used. The channels that have better packet reception ratio for a particular environment are thus selected for network design and this design approach can improve the packet reception rate (PRR) as well as overall energy consumption of the network. But, it can enhance the design complexity for data reporting. If the channel conditions change gradually or rapidly then a dynamic decentralized channel allocation can be considered, otherwise, in fixed channel conditions an offline channel allocation strategy could be effective due to minimized overhead. The investigated channel allocation techniques are based on the quality level of each channel in order

to increase the network reliability. In this chapter, multichannel allocation schemes for clustered wireless sensor networks are proposed. These are based on an offline binary linear programming approach as well as a game theory based distributed channel allocation techniques. They are evaluated using simulations with NS-2.

Introduction

The protocols for wireless sensor networks generally employ a single channel communication design for the entire network. However, the number of orthogonal channels available in CC2420 antenna is 16 [3] which can be used for deploying a multichannel network design. This design approach can increase the network throughput and reduce the packet loss due to minimized interference between the communication channels. Thus, as a consequence the overall network energy consumption will be decreased as well. The main problem lying in multichannel design is the cost of overhead to find the optimum channel allocation as well as the synchronization overhead at the MAC layer. In this section, existing multichannel allocation techniques are introduced that will be considered next in this chapter for designing multichannel allocation algorithms. Existing multichannel allocation techniques could be classified into static (offline) or dynamic (online) allocation techniques.

Static Multichannel Allocation

Most of the static multichannel allocation related research is done by allocating channels to the nodes using a graph coloring approach. But usually they don't consider channel allocation by taking into account the quality of each channel [START_REF] Wu | Realistic and efficient multi-channel communications in wireless sensor networks[END_REF]. In [START_REF] Yu | Multichannel assignment in wireless sensor networks: a game theoretic approach[END_REF], a channel assignment technique based on the best response dynamic is used but it does not consider a large network for designing a multichannel architecture as it results in a large increase in computation complexity. The problem is solved in this dissertation by considering the hypothesis of a large network and partition it using clusters to reduce the complexity of the problem. In [START_REF] Wu | Realistic and efficient multi-channel communications in wireless sensor networks[END_REF], the authors considers a tree based network configuration where the members of tree are the ordinary nodes of the network. But most practical systems use the cluster based network infrastructure to have a robust design. Thus, it may be an impractical approach and to tackle this problem, we consider the tree formation approach in a clustered design. Also [START_REF] Maheshwari | A measurement study of interference modeling and scheduling in low-power wireless networks[END_REF] describes a channel scheduling and interference modeling technique but it does not propose a global network management scheme using multichannel design. [START_REF] Li | A cluster based on-demand multi-channel mac protocol for wireless multimedia sensor networks[END_REF] describes a scheduling and transmission mechanism for MAC layer in a clustered wireless sensor network. The slot assignment is done for different clusters that are operating on different frequencies. But they do not consider channel quality while assigning the channels. [START_REF] Gupta | Exploiting multi-channel clustering for power efficiency in sensor networks[END_REF] targets a temperature sensing application and it distributes the nodes into clusters based on the range of temperature a node has to measure. Then each cluster is assigned a channel without considering the respective channel quality of each channel. This technique is only compared with the single channel technique. [START_REF] Hossein | An adaptive cross-layer multichannel qos-mac protocol for cluster based wireless multimedia sensor networks[END_REF] introduces a multichannel MAC protocol that assigns channels without considering their quality. Also, it prioritizes the traffic at MAC layer by giving most priority to the multimedia traffic and least priority to the data traffic. [START_REF] Starobinski | Nearoptimal data dissemination policies for multi-channel, single radio wireless sensor networks[END_REF] proposes a data dissemination architecture using multichannel for delay minimization and evaluates the protocol parameters for increasing the network size only. [START_REF] Yen | Integrated channel assignment and data aggregation routing problem in wireless sensor networks[END_REF] constructs a tree and assigns the channels to the respective nodes by only considering the interference from the neighboring nodes. It does not consider the channel quality for channel allocation. [START_REF] Li | Energy efficient event detection and dissemination scheme for clustered wireless sensor networks[END_REF] considers a clustered design whose MAC layer has contention as well as no contention period. It is a multichannel design but the interference is minimized only by assigning unique channels to nodes without considering the channel quality.

Dynamic Multichannel Allocation

The design techniques described in the previous sub-section consider the static approach for multichannel allocation. However, dynamic channel allocation/switching mechanism can be used to increase the network performance in varying channel conditions. Such as [START_REF] Hieu Khac Le | A practical multichannel media access control protocol for wireless sensor networks[END_REF] presents the network channel selection based on the sink location as well as congestion in the network. It may not reduce the channel interference and the dynamic channel switching will cost a lot in terms of energy.

To solve the channel allocation problem, we consider in static channel conditions a tree based channel allocation while for the changing channel conditions, we use a distributed game theory based channel allocation that is similar to the approach proposed in [START_REF] Puschini | Temperature-aware distributed run-time optimization on mp-soc using game theory[END_REF] which investigates a multi-criteria optimization technique for distributed multiprocessor systems. These allocation mechanisms are described in the following section:

Centralized Offline Multichannel Design

A network consisting of n nodes and a sink randomly deployed in the network is considered. Each node has a single antenna that can transmit/receive the packets. Each antenna can support upto l orthogonal channels and it can operate on a single channel at a time. It will only interfere the communication of neighboring antennas working on the same channel. If the neighboring antennas are working on different channels, it will minimize the interference resulting in reduced packet loss as well as increased packet throughput. This will also decrease the overall energy consumption of the network.

In this section, an offline design strategy based on the channel measurements in the environment is proposed. The network is partitioned using clusters and based on the LQI values for all the available channels of the cluster head as well as the channels selected by the neighboring clusters, the appropriate channel for that cluster is selected. For example, the LQI value of the CC2420 transceiver is an indicator of the Bit Error Rate (BER) or the packet reception ratio (PRR) of a specific node. The clusters are classified into different tiers so that the tier nearest to the sink will have the highest priority to select a channel. This is so because the clusters in that tier have a high traffic volume to be forwarded towards the sink. If they operate on a channel with lower quality, it will increase the number of retransmissions to forward a packet and thus leading to increase the overall energy consumption of the network. So, to minimize the retransmission overhead, it appears to be better to use such a channel selection strategy.

It is assumed in this case that the channel conditions remain the same during the whole network lifetime. It is also assumed that the sink can operate on multiple frequencies using multiple antennas for packet reception [START_REF] Wu | Realistic and efficient multi-channel communications in wireless sensor networks[END_REF]. To support multiple channels, the sink needs to have a multi-interface antenna.

Network Configuration

In this section, the process of network configuration is discussed. The objectives of the network configuration for static channel allocation scheme are:

1. It should support a clustered design.

2. Each cluster is a part of only one branch of the tree. All the clusters that are member of a particular branch of the tree are operating on a single channel. This approach minimizes the synchronization overhead for communication between clusters operating on different frequencies.

3. It is preferable that the neighboring clusters of the same tier should have different channels.

4. The clusters near the sink have higher priority to select a channel as it has the maximum traffic volume that needs to be forwarded towards the sink.

The network configuration process consists of following steps:

1. Cluster Formation Process 2. Channel Assignment for Tier 1 Clusters

Cluster Tree Formation Process

We discuss all these steps in detail.

Cluster Formation Process

The cluster formation based multichannel design is used. We consider a network divided into equal area clusters. However, the proposed multichannel allocation scheme can be applied to the unequal area clusters. Each cluster has a cluster head that is responsible for gathering the data from the cluster members and to forward it towards the sink. The basic reason for a cluster formation of the network is that is that it enhances the connectivity of the network. If a node dies in a tree based channel assignment architecture, it will break the tree based communication and the leaf nodes of that tree will suffer. This is not the case in a cluster based tree structure where the cluster head is changed after a specific interval of time. Also, the cluster based design can be used to do load balancing in the network resulting in prolonged network lifetime [START_REF] Rabiner Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF]. The cluster radius is taken to be less than the antenna range for a given transmission power. This radius will be used by the nodes near the sink for forming the Tier 1 of clusters. Then, this process will be done for the whole network until all the nodes of the network are part of a cluster. Thus, equal sized clusters will be formed in the network. The resulting structure is shown in figure 5.1. As mentioned above, the higher priority for selecting a channel for the communication lies with the cluster that has to forward a large amount of traffic i.e. the sink node. So the highest priority for channel selection is assigned to the clusters near the sink and lowest to the clusters lying far away from the sink. The channel is selected for a cluster head based on the LQI measurements. The LQI is a measure of Packet Reception Ratio for a certain cluster head assuming no external interference from the neighboring clusters. The set of available channels C = { C 0 , C 1 , ..., C l-1 }, are the channels having LQI greater than a threshold value fixed at LQI min which is fixed at 80% in [START_REF] Wu | Realistic and efficient multi-channel communications in wireless sensor networks[END_REF]. Thus, each cluster head knows after measurement which channel will give it the highest payoff in terms of LQI. But on the same time, two neighboring clusters in Tier 1 should not share a common channel to minimize the interference.

The payoff for selecting a channel lies with the channel LQI for that cluster as well as its neighboring clusters' channel selection. We use a Binary Integer Linear Programming Approach for channel selection of the Tier 1 clusters. Two neighboring clusters should not select the same channel in Tier 1 and it is assumed that LQI value for a channel inside a cluster is almost same.

The problem is defined as: There are m clusters in Tier 1 of the network that have to select their operational frequency. The payoff for selecting a particular channel for a cluster depends on the LQI value of that cluster. The problem is thus to maximize the payoff given that neighboring clusters have non-overlapping frequencies.

We define,

x ij = 1 if i th cluster chooses j th channel 0 otherwise
where i={1,2,...,m}, j={0,1,...,l-1}. w ij are the corresponding weights or the payoffs of each cluster where i={1,2,...,m}, j={0,1,...,l-1}.

The neighboring nodes are listed in order. That is, neighbors of node a are a-1 and a+1 located in the same cluster and the frequencies of the node pairs (a, a-1) and (a, a+1) are non-overlapping.

The problem is to maximize the following function:

max m i=1 l-1 j=0 w ij x ij (5.1)
subject to the following constraints:

∀ clusters i, l-1 j=0 x ij = 1 (5.2)
Also, for all immediate neighboring clusters b of cluster a = {1,2,...,m}:

x aj + x (a-1)j + x (a+1)j ≤ 1 (5.3)
where, j={0,1,...,l-1}. And for all clusters i,

m i=1 l-1 j=0 w ij x ij ≥ LQI min (5.4)
The first constraint shows that each cluster should only choose one channel, the second constraint account for the fact that the neighboring clusters should have disjoint frequencies and the third constraint ensures that the channel quality of all the clusters is greater than a minimum threshold, that is, LQI min .

Cluster Tree Formation Process

The tree formation is done after the process of channel assignment for the Tier 1 clusters. The cluster tree formation process is started from the center based on the selected frequency by each cluster in Tier 1. The tree is constructed in such a manner that clusters of Tier Z choose a neighboring cluster in Tier Z+1 that has the maximum LQI value for the frequency chosen by Tier Z cluster. Thus, it ensures that the Tier Z+1 cluster that joins the tree has the best channel quality. The Tier Z+1 clusters that are unable to join a cluster tree of Tier Z joins the nearest cluster tree of Tier Z that maximizes its LQI. Thus, two neighboring clusters in the same tier can have the same channel. This process continues until all the clusters are part of a branch of the tree. This is explained in Algorithm 3.

Algorithm 3 Function for Choosing Next Hop Tree Member

n ← 1 while n <= maximum_number_of_tiers do for All Clusters of Tier n do select the next branch of tree from a Tier n+1 neighboring cluster using Next-hop function if a cluster left without no frequency assignment in Tier n+1 then Assign the frequency of nearest cluster in Tier n that maximizes its LQI n = n + 1 Next-hop function input: for all next Tier neighboring clusters Assign the same frequency to a next tier neighboring cluster that maximizes its LQI payoff Thus, the tree formation process is started from Tier 1. The Linear Programming function for choosing the next hop tree works as follows. Various next Tier clusters can join the current cluster with same frequency as a part of the tree formation. As shown in figure 5.2, we have Tier 2 clusters that can possibly join a Tier 1 cluster to become part of a branch of tree. The problem is to choose a channel for a cluster that has maximum LQI value for the cluster. In other words, we have to color the graph to find the next hop branch of the tree so that choosing a color has maximum LQI. The uncolored clusters in Tier 2 become part of a nearest tree that maximizes its payoff. This process is continued until all the clusters are part of a branch of the tree. The tree formation is explained with coloring in figure 5.3. This structure is then used for inter-cluster data traffic forwarding without the need of a synchronization mechanism as all of the clusters lying on a tree are operating on a single channel.

Performance Evaluation of Centralized Channel Allocation

In this section, the performance evaluation of the offline channel allocation approach is described. The tree based channel approach is compared with a single channel design approach, a random tree formation approach and a graph coloring based tree formation technique. The graph coloring based tree formation technique is based on [START_REF] Wu | Realistic and efficient multi-channel communications in wireless sensor networks[END_REF] that creates the tree using nodes of the network while we use same technique and form the tree using clusters as an individual member of the tree. In technique described in [START_REF] Wu | Realistic and efficient multi-channel communications in wireless sensor networks[END_REF], the channel conditions are not taken into account in graph coloring process. It first creates a fat tree and the clusters that are not part of a tree join the nearest one as a second step of the tree formation process. The simulation parameters are listed in table 5.1 and we take results after varying the number of nodes as well as the transmission distance of each antenna. The simulation is per- [4]. The effect of network size and the antenna transmission range is observed On the other hand, changing antenna transmission range changes the interference region and helps in realizing its effect on network quality assessment parameters for multichannel allocation techniques.

Effect of Network Size

In the first set of simulations, the effect of increasing the network size is observed. We nearly double the number of nodes in a cluster to see its effect on the energy consumption, throughput and delay. In Fig. 5.4, it is observed that increasing the number of neighbors in the network increases the per hop average delay for all the techniques due to increased interference and retransmissions. The worst delay is for single channel design due to increased retransmissions resulting in buffer overflow. The delay is best for the linear programming based design as it has least number of retransmission at the MAC layer due to minimized interference and thus have an impact on the average delay for each node of the network. The design technique of graph coloring is better than random channel selection technique and has better delay profile.

Figure 5.5 shows that increasing the number of neighbors in the network de- The design technique of graph coloring often forms a tree with more number of hops towards the sink thus it decreases the throughput. The random channel tree formation process cannot guarantee the optimal channel allocation in a clustered multichannel network. In Fig. 5.6, it is observed that increasing the number of neighbors in the network increases the average energy consumption of the nodes for all the techniques. However the single channel design has worst average energy consumption. The per node average energy consumption is best for the linear programming based design due to high packet reception rate towards the sink node. The graph coloring design technique often forms a tree with more number of hops towards the sink thus it increases the power consumption. The random channel tree formation process provides better results than the single channel design but it performs lower than graph coloring and linear programming based techniques.

Effect of Antenna Transmission Range

In the second set of simulations, the multichannel design approaches have been evaluated by changing the sensitivity of the receiving antenna. In these simulations, the carrier sense threshold value is taken to be double of the reception threshold value. Thus, the transmission distance of the sender is changed and its effect is observed on all the studied techniques. Fig. 5.7 shows that increasing the transmission distance increases the per-hop average delay for all the techniques due to increased interference and retransmissions. But for the single channel design, worst delay is observed due to increased retransmissions resulting in buffer saturation. The average per-hop delay is minimum for the linear programming based design as it has better packet reception ratio. The graph coloring technique has a better channel selection technique than random approach, thus it has a better delay profile. In Fig. 5.8, it is observed that increasing transmission distance in the network decreases the application layer throughput of the nodes. The throughput is best for the linear programming based design as it has least number of retransmission at the MAC layer and thus has a positive impact on the average application layer throughput of the network. The worst throughput is for the single channel design due to low packet reception rate. The design technique of graph coloring often forms a tree with more number of hops towards the sink thus it decreases the throughput. But its throughput decreases drastically on increasing the transmission distance to 30m. It is so, because the transmissions from the tree of a particular channel starts receiving interference from a tree operating on the same channel.

Increasing the transmission distance of the sender will have more interference region and it increases the average energy consumption of the nodes for all the In general, the performance of single channel design techniques is lower than the multichannel design techniques. For multichannel techniques, the linear programming approach performs because it considers the LQI of each channel for allocation process inside a cluster. Also, the random channel selection can be preferred ahead of graph coloring based design approach as it is a low complexity method and provides results close often to those of the graph coloring based technique.

Evolving Channel Conditions

The proposed approaches are evaluated in a constant channel conditions and we have shown that the linear programming based approach performs better. However, the performance may degrade if the channel condition changes. The figures 5.10 and 5.11 show that the delay and the throughput may not be deterministic in randomly evolving channel conditions for Linear Programming Based Multichannel design approach. While, the evolving changing conditions are simulated by randomly changing the BER value for a cluster head. Thus, there may be a need to have a dynamic channel switching mechanism that changes the channel for each cluster

Distributed Multichannel Design

In this section, the distributed multichannel allocation is discussed. Usually, the sensor networks do not consider dynamic channel switching approaches such as described in [START_REF] Hieu Khac Le | A practical multichannel media access control protocol for wireless sensor networks[END_REF] due to increased overhead. However, if environmental condition may change after network deployment, then a dynamic channel switching scheme that updates the channel for all the clusters could be considered if that scheme does not induce prohibitive overhead while throughput and energy are improved. For that sake, the dynamic decision making of process of game theory based solutions can be considered. We consider a network model similar to the offline channel allocation technique. However, this technique needs some extra parameters that have to be learned by cluster heads periodically. Each cluster has a neighbor set S and each neighbor is connected through a inter cluster communication. Each cluster head gathers data locally and forwards it towards the sink using cluster head to cluster head communication. Thus, the objectives for network configuration for distributed multichannel design are listed below:

1. It should be a clustered design. 3. Assign same channel to the neighboring clusters in case the LQI of unique channel is very low.

Introduction to Game Theory

Game theory is considered as a branch of applied mathematics. A game is a scenario composed of rational players, each one having a set of possible actions. Regarding the whole system including interactions, these actions produce consequences that are quantified as outcomes. In such scenario, each player makes strategic choices over the set of possible actions to execute the best one, pursuing some predefined objective in terms of outcome. The individual success of each player depends not only on its own choice but also on the actions chosen by other players in the game.

In this kind of scenarios, game theory studies the interactions between players. It aims at understanding the choices and behavior of players and how special situation such as equilibriums are reached. It proposes some mathematical descriptions to problems such as game models, solutions and optimizations. By using probabilistic theory, it also studies dynamic games, where scenarios change during the game. John Nash formalizes the most famous solution concepts: the Nash Equilibrium. Game theory has been recognized as an important tool in many fields and up today eight game-theorists have been laureated by the Nobel prize in Economic Sciences. Game-theoretic concepts are usually used in many different domains such as economy, biology, sociology, political sciences, international relations, engineering and computer sciences.

Non-cooperative Games

As explained earlier, a game essentially consists of three components: the players, a set of actions per player and the preferences of each player.

The simplest of strategic games is that composed of only two players and with few actions per player. These games are usually represented by two-dimensional tables.

A game [START_REF] Osborne | Oxford univ. press. An Introduction to Game Theory[END_REF] may be defined as a system G = ((N, S i , u i ), i = 1,...,n ) where:

1. N represents the set of n players, N = {1,...,n}.

2. for each player iεN , S i represents the set of actions S i = {s i1 , s i2 , ..., s im }; S = S 1 × S 2 × ... × S n is the set of all possible game situations;

3. for each player iεN , u i : S → R represents the payoff function.

A strategy profile (strategy or action vector) is a vector s = (s 1 ,...,s n ), where s i ∈ S i is a strategy (or action) of the player i.

By (s i , s * -i ), we denote the strategy profile obtained from s * by replacing the strategy of player i with s i , i.e.

(s i , s * -i ) = (s * 1 ,s * 2 ,...,s * i-1 ,s i ,s * i+1 ,...,s * n ).
The most frequently used steady-state concept in the game theory is the Nash Equilibrium (NE). Informally, a strategy profile is an NE if no player can improve her payoff by unilateral deviation.

Formally, a strategy profile, x is an NE if and only if

u i (x) ≥ u i (y i , x -i ), ∀ i ε N, y i εS i
An NE may be interpreted as a steady state where each player holds a correct expectation of the other players behavior and acts rationally.

Game Theory Based Channel Allocation

In this section, we describe how game theory could be used as a solution for the described problem. The Nash equilibrium solution proposed in [START_REF] Puschini | Temperature-aware distributed run-time optimization on mp-soc using game theory[END_REF] computes the steady state for a multicriteria problem in a multiprocessor on chip system and we adopt this approach for the considered channel allocation problem. The objective is to maximize the payoff for a chosen strategy based on the choice of other players strategy in the last period where the period defines the periodic time interval after which the channel switching decision is made. The algorithm is explained in Algorithm 4.

Algorithm 4 Nash Equilibrium Solution

for All strategies do if Payoff(New strategy, Other Player's strategy in last step) > Payoff(My strategy in last step, Other Player's strategy in last step) then My strategy = New Strategy

In this technique, distributed multichannel design technique is used. The channel LQI is taken for all the channels of an antenna. They will learn the channel quality matrix of the available channels. Based on the value as well as the channel selected by the neighbors in the previous period, they will decide the channel for the next period.

Each cluster head is modeled as a player into a non-cooperative game. It has to choose its operating frequency which is the game variable. It can choose that frequency based on the channel quality parameters for that cluster. These parameters for a particular channel is its LQI value. The frequencies to each cluster is assigned after a periodic interval of time. The channel values for neighboring clusters from the previous period are used to decide the channel in the next period. Thus, it gives the priority to select a channel that is not selected by a neighbor by reducing the payoff for selecting a channel if it is already possessed by its neighbors. The payoff computation for all the channels is described in Algorithm 5 and illustrated in figure 5.13. If a channel is not possessed by a neighboring cluster in the previous period, then its selection payoff is equal to LQI value of the channel. Otherwise, if it is possessed by a neighboring cluster, its selection payoff value is reduced as per Algorithm 5. Thus, this technique first tries that all neighboring clusters have different channels. But if there are not sufficient channels that have better LQI, it will choose a channel that maximizes its LQI even if it is already possessed by a neighboring cluster. The channel having highest selection payoff for a particular node will be selected.

Network Initialization and Traffic Forwarding Process

The process is similar to the one described for offline scheme but there are some periodic messages need to be broadcasted periodically by each cluster head. This process informs the neighboring clusters for the channel decision in the current period. Each cluster head is responsible for broadcasting its channel information after making the channel decision at the beginning of each period. This information is broadcasted on all the available channels. This ensures that all the cluster heads are informed of the channel decision of their neighbors that is useful for making its channel decision in the next period. This is an extra overhead for the optimization technique that we have implemented.

Each cluster head gathers all the data from the cluster members and forwards it towards the sink using the minimum distance geographic routing. In this type of routing, the packet will be forwarded towards a cluster that is the neighbor of sending cluster and it is nearest to the sink. As it doesn't use a tree based multichannel clustered design [START_REF] Ali Khan | Multi channel design for clustered wireless sensor networks[END_REF], so the minimum path can be chosen to send the data towards the sink that will minimize the delay. It is to be noted that we do not implement a packet retransmission mechanism at network layer in case of packet loss but it is implemented at MAC layer.

Performance Evaluation of Distributed Channel Allocation

In this section, the technique of game theory based learning technique is compared with the tree based data dissemination schemes. In tree based design of channel assignment, we consider the tree formation described for offline channel allocation mechanism. Using the tree formation scheme, we describe two multichannel allocation schemes and call them the dynamic and static tree formation schemes. The static tree formation scheme is the same as the offline channel allocation mechanism. While the dynamic tree formation scheme uses the same design as static scheme for tree construction but it changes the channel assignment in the whole tree based on the Tier 1 channel selection periodically. Thus the frequency of a branch of the tree changes based on the channel selected by its Tier 1 cluster. These schemes are compared in table 5.2. The effect of network size and the channel conditions on network performance parameters are observed. Changing network size increases the traffic load in the network thus helps in simulating an increased traffic scenario. On the other hand, changing channel conditions are simulated by randomly changing the BER for all the channels in a cluster after certain amount of time. It helps in comparing the multichannel allocation schemes under dynamic environment conditions. The simulation consists of a network that uses CSMA-CA based MAC Protocol and the data is generated towards cluster head that gathers the data and forwards it towards the sink. The simulation parameters are listed in table 5.1.

Channel Selection Period

A channel selection period for schemes needs to be defined first. We use simulations on the case study of table 5.1 to decide the period between successive dynamic channel computation. As per figure 5.14, 10 sec is selected as the channel selection period for dynamic schemes as it is the minimum channel selection period observed for the case study that optimizes the average per-hop delay experienced by a packet generated at the application layer. If this period is reduced to 5 sec, it increases the per-hop delay due to an increase in the network configuration packets. Delaying the channel selection period to 15 sec reduces the network configuration packets overhead but decreases the algorithm efficiency. Due to minimized overall delay, at run-time this channel selection period may increase the network throughput as shown in figure 5.15.

Effect of Variation in BER

The Bit Error Rate (BER) variation is the difference between the minimum (fixed at 0.15 in the simulation) and the maximum (fixed at 0.6 in the simulation) BER range for a specific channel of a cluster head. It is selected randomly and larger this value, higher is the probability of having a lower channel quality for the whole network. The BER is varied at the beginning of channel selection period whose selection is described in previous sub-section.

Figure 5.17 plots the throughput of packets received at the cluster heads lying closest to the sink. Thus it is the throughput at the bottleneck of the network and it shows that in all the cases of variation in BER, the throughput of game theory based scheme is better than offline as well as distributed tree based channel assignment. This is so because of the efficient channel assignment based on the channel variation that eventually increases the number of packets received at the sink. The distributed tree based channel assignment is performing worst as the tree only considers the channel quality in Tier 1 to change the color of the whole branch that effects negatively. The delay is minimized in the game theory based mechanism as shown in figure 5. [START_REF] Afzal | Rsrp: A robust secure routing protocol for mobile ad hoc networks[END_REF]. This is due to the fact that the algorithm selects the next hop based on the geographic location of next tier cluster as it does not follow a tree to send its data towards the sink. In all network sizes, the throughput of game theory based scheme is better than centralized as well as distributed tree based channel assignment. Also, increasing the network size very badly affects the tree based channel assignment schemes while the throughput of game theory based learning technique doesn't change a lot. Also, the delay is minimized in the game theory based mechanism as shown in figure 5.19. Changing the size of network do not have a lot of effect on average per-hop delay faced by a packet. Thus, we can state that for different network configurations, this learning technique is able to increase the network throughput and decrease the per-hop delay. This is achieved at the cost of extra network configuration packets that increases the average energy consumed by each node of the network by 1% as shown in table 5.3.

Conclusion

In this chapter, a centralized linear programming approach as well as a distributed multichannel assignment for the clustered tree formation in wireless sensor networks is proposed. The network consists of randomly distributed nodes and it is partitioned using equal sized clusters. Using Binary Linear Programming Approach, the multichannel trees are formed using each cluster head's LQI value for centralized scheme. The approach is simulated using NS-2 simulator and is compared with the single channel design, random tree formation design and the graph coloring based design. The simulation results show that the approach is better than single channel design in terms of energy consumption and the packet reception rate by assuming that channel conditions remains same during simulation. Also, it outperforms the graph coloring based design as well as the random channel design. This is an offline design technique but its performance deteriorates as the channel conditions start varying. However, it is investigated that in environments where the channel condition changes either slowly or abruptly, this scheme may minimize the network performance parameters. For that case, a distributed learning mechanism is considered to change the channel allocation based on the evolving conditions. For this case, a game theory based learning mechanism is proposed. It increases the throughput and decreases the delay in comparison with other centralized and distributed tree based channel allocation techniques. Despite the game theory based technique increases the number of configuration packets with respect to other approaches, the energy consumed by these extra packets is quite low and represents a little contribution to the total energy required to transfer data packets throughout the network.

For the considered disaster management application, we conclude that multichannel allocation schemes can be useful to increase the throughput and reduce delay for the multimedia sensor network. Depending on the channel variation conditions, we can use either of the proposed schemes to increase the network throughput. The multichannel allocation and switching mechanism proposed in this chapter can also be combined with the QoS energy aware routing mechanism presented in chapter 4 for the disaster management application. This can help in reducing the energy consumption and meeting the end-to-end packet delivery deadlines. The next chapter validates the design approaches proposed in chapters 4 and 5 by combining both of them for a multimedia sensor network installed inside a building.

Chapter 6

Simulation of the Testcase Application Contents In this chapter, we talk about how to use various aspects of the wireless sensor network techniques that we have proposed to enhance the network efficiency in a multimedia sensor network. We have independently explored the aspects with the help of NS-2 simulations to evaluate their energy and delay minimization. In this chapter, we combine some of the proposed contributions for a multimedia sensor network to see how they behave for a given network topology and what performance gain can be extracted.

Introduction

We have described a QoS aware energy efficient routing metric for inter-cluster routing in a network deployed inside a building targetting high traffic volumes in chapter 4. It proposes a routing metric that minimizes the energy consumption by trying to meet the end-to-end packet delivery deadlines. On the other hand, we consider the multichannel allocation technique for a clustered wireless sensor network in chapter 5 for high traffic volumes. It tries to minimize the energy consumption by allocating unique channels to the neighboring clusters. In this chapter, the considered network for simulation consists of the same scenario for the chapter 4. However, rather than considering a single channel design as it was performed in chapter 4, we consider here that the channel could be changed periodically. In section 6.1.1, we describe the scenario and in section 6.1.2, we discuss about the performance analysis.

Multichannel Allocation for QoS Energy Aware Routing in Sensor Network

In chapter 4, we have described a technique for timely delivery of data in an energy efficient manner (Algorithm 2). This approach classifies different paths with increasing cumulative energy consumption. It chooses the path which consumes the minimum amount of energy and which obeys the end to end deadline associated with each packet. Thus it will not only help in minimizing the overall energy consumption of the network but on the other hand it attempts to respect the end to end deadlines for each packet. On the other hand, chapter 5 describes a game theory based distributed channel allocation that can be used for multichannel allocation along with QoS Energy Aware Routing solution. This approach is based on the Nash equilibrium solution proposed in [START_REF] Puschini | Temperature-aware distributed run-time optimization on mp-soc using game theory[END_REF] and chapter 5 shows that the game theory based approach provides better results on delay and throughput than other considered techniques with an equivalent energy consumption. Its objective is to maximize the payoff for a chosen strategy based on the choice of other players strategy in the last period where the period defines the periodic time interval after which the channel switching decision is made. This algorithm is explained in Algorithm 4 in chapter 5.

As both the techniques require to send periodic broadcast messages, so we combine this functionality into one packet. The procedure of combined implementation of the two techniques is explained in figure 6.1. This explains how the periodic message broadcast of the messages in both techniques can be combined to get delay as well as channel information of the neighboring clusters. However, this does not increase the complexity of this scheme as both the proposed techniques needs to transmit some periodic messages to include dynamic behavior. We have combined the periodic messages as explained in figure 6.1 so that complexity does not increase a lot.

The network configuration consists of following steps:

1. The network is partitioned using clusters.

2. Each cluster head is responsible for sending periodic configuration packets that are necessary for delay as well as channel update information.

3. The periodic channel switching is done as per Algorithm 4.

4. The inter-cluster packet forwarding route is selected as per Algorithm 2.

5. Each member node is one hop away from the clusterhead.

Performance Analysis

We have chosen two test cases for the simulation. The first one consists of a small network and the second consists of a larger network. We see whether the algorithm behavior remains the same in both cases. The simulation is done using NS-2 and the simulation parameters are listed in table 6.1. It is to be noted that additional packets for network configuration and channel allocation are taken into account for evaluating the energy consumption.

Inter-cluster routing for 3x3 sized clustered network

For the first case, we have chosen an example similar to the one used in Chapter 4 and is shown in figure 4.5. It consists of nine cluster heads involved in inter-cluster routing. The energy consumption results are shown in figures 6.2-6.4. We observe that using a multichannel allocation, the energy consumption decreases due to minimized interference. Where in all these figures, the part (a) shows the plot of QoS Energy Aware Routing as proposed in chapter 4 and the part (b) shows the modified version of QoS Energy Aware Routing that includes multichannel allocation. The sink is located at (0, 0). In figure 6.2, QoS energy aware routing results in more energy consumption than the multichannel design for the end-to-end deadline of 0.5 seconds for a packet generated from the farthest sink node. Notice that a end-to-end deadline of 0.5 seconds is close to the mean time required for transferring packets between these opposite nodes in the network. The minimum as well as the maximum energy consumed by a node is higher for the design that do not use the multichannel allocation. As in a multichannel approach packets are distributed over the set of channels, the number of packets received by a node is lower using a multichannel design compared with a single channel design. Therefore, due to this packet minimization per channel, the energy consumption induced by packet reception is reduced in a multichannel. The node that can minimize the overall delay but increases the energy consumption for multichannel design is located at the center of the network. In 6.2 (b) multichannel allocation performs well: the central node supports the same traffic on one channel while other nodes are no longer involved in extra packet reception as they are distributed over other channels. If the end-to-end deadline is increased to 1.0 seconds, it leads to overall energy equalization for both the schemes. However as shown in figure 6.3, the energy consumption of multichannel design is much less for all the nodes due to minimized reception of packets at the physical layer. Also increasing the deadline, delivery of data may lead to the selection of less energy consuming path. Further increasing the deadline to 1.5 seconds results in the further equalization of overall energy consumption and the energy consumption of all the nodes becomes quite uniform for the multichannel design (figure 6.4). This is to be noted that uniform energy consumption by all the nodes has direct impact on lifetime maximization of the network. We define laxity as the remaining time to deadline for a packet generated from node 9 4.5) when it is received at the sink. The laxity explained in figure 6.5 is similar to both the cases of single channel and multichannel QoS energy aware routing. But the laxity is generally a bit more for multichannel design due to minimized interference that leads to minimized per-hop delay. Both the strategies try to meet the end-to-end deadline and be energy efficient as well. Thus, both the design approaches helps in minimized energy consumption without a compromise on the end-to-end deadline. But the multichannel design can be energy efficient due to minimized interference. For the second case, we have chosen an example of 5x5 clusters involved in intercluster routing and the sink is located at (0,0). The energy consumption results are shown in figures 6.6-6.8. As previously observed, these figures show that using multichannel allocation, the energy consumption decreases due to minimized interference. Where in all these figures, the part (a) shows the plot of QoS Energy Aware Routing as proposed in chapter 4 and the part (b) shows the modified version of QoS Energy Aware Routing that includes multichannel allocation. The end-to-end deadline for experimental evaluation is doubled in this case because the network size was also increased.

In figure 6.6, QoS energy aware routing results in more energy consumption than the multichannel design for the end-to-end deadline of 1.0 seconds for a packet generated from the farthest node. The minimum as well as the maximum energy consumed by a node is higher for the design that do not use the multichannel allocation due to the fact that reception of packets is reduced at physical layer leading to energy consumption minimization. In figure 6.6 (a) nodes along the diagnol between source nodes and sink node are those that have the highest contribution to the energy consumption. The low laxity for packet delivery forces the QoS energy aware routing algorithm to select this path in order to avoid deadline violations. If the end-to-end deadline is increased to 2.0 seconds, it leads to overall energy equalization for both the schemes because they start to choose a path fro data forwarding that has less energy consumption. However as shown in figure 6.7, the energy consumption of multichannel design is much less for all the nodes due to minimized reception of packets at the physical layer. Further increasing the deadline to 3.0 seconds results in the further equalization of overall energy consumption and the energy consumption of all the nodes becomes quite uniform for the multichannel design (figure 6.8). The overall energy consumption is also increased as compared to a 3x3 sized clustered network because of increase in network traffic. However, the energy consumption for the Multichannel design is not as uniform as that of single channel design for the cases of 1.0 seconds and 2.0 seconds of end-to-end deadline (figures 6.7 and 6.8). This is so because the every cluster do not receive the packet sent by its neighbor due to multichannel allocation and this minimizes the overall energy consumption but results in uneven energy consumption.

The laxity explained in figure 6.9 is similar to both the cases of single channel and multichannel qos energy aware routing. This is so because both the strategies try to meet the end-to-end deadline and be energy efficient as well. Thus, both the design approaches helps in minimized energy consumption without a compromise on the end-to-end deadline. But the multichannel design can be energy efficient due to minimized interference for a small as well as large scale network.

Conclusion

In this chapter, we have described a procedure for how to merge the different research aspects targetting the same objective for the similar network scenario. The QoS Energy aware routing metric and distributed multichannel allocation contributions presented in chapters 4 and 5 respectively are combined for a clustered sensor network having realtime data delivery deadlines as well as having limited energy level. The results show that QoS energy aware routing technique leads to graceful degradation of QoS and if laxity is sufficient it allows energy consumption to be Figure 6.9: Laxity of a Packet versus End-to-end Deadline well distributed. However, the multichannel design do not alter the behavior of QoS energy aware algorithm since laxity remains almost unchanged, but it allows further reduction of the energy consumption. The contribution presented in chapter 3 can not be combined with the contributions of chapters 4 and 5 because it may consist of a heterogeneous network having limited processing resources to implement more sophisticated techniques like realtime data delivery and multichannel allocation. These schemes may eventually cost more in terms of energy for a network having limited processing capability nodes. The wireless sensor networks research flourished in the last twenty years and it still continues to explore various approaches to maximize the network performance parameters. Data Collection is a fundamental functionality of the sensor nodes deployed in the network. The different aspects that needs to be optimized while data collection are to minimize delay and energy consumption based on the application scenario. In this thesis, we focused on the algorithmic aspects of the energy consumption and delay for different partitions of a disaster management application. Precisely, this application targets the situation of a building on fire and the sensor network deployed in the network has to measure either the physical parameters such as temperature, pressure or humidity or extract the video of the region that is on fire. This scenario exhibits two sort of constraints for data dissemination that the network has to deal with: low throughput with low activity and high throughput under end-to-end delay. Our contribution could help to make an efficient decision for responding to the calamity. In the following, we briefly describe our contribution and propose future research directions.

Conclusion

Our approach comprised of three contributions for sensor network design:

1. Virtual Data Dissemination Architecture 2. QoS Energy Efficient Routing

Multichannel Allocation

Using these techniques, we showed that it is possible to improve efficiency of network configuration for the considered application. In chapter 3, three data dissemination techniques for grid based sensor networks were analyzed for homogeneous as well as heterogeneous cases. The results show that static scheme has worst energy consumption profile. On the other hand, dynamic scheme performs a fine load balancing in homogeneous networks but at the cost of increased delay. However, for heterogeneous network its performance deteriorates and here the load balancing schemes performs better. Despite it adds an extra overhead for periodic load determination for each cellhead, it helps helps in equalizing the energy consumption of the cellheads. However, these energy efficient data dissemination techniques that are proposed for grid based clustered sensor networks may not perform efficiently when an application layer imposes some real time deadlines. For example, in disaster management application, the part of the network that performs the video monitoring task has realtime data reporting deadlines as well as energy constraints. This situation requires more sophisticated learning approaches to minimize the packet forwarding delay. The chapter 4 presents cluster formation and intercluster routing mechanism. The proposed clustering approach ensures no physical boundary inside clusters. The intra cluster packet forwarding is one hop routing and the inter cluster routing is done by taking into account the Link Quality Indicator (LQI) between different nodes and the application layer deadline. The proposed routing metric performs well under different application deadline cases as it takes into account the effect of congestion on a particular path by periodically estimating the delay values and the uneven energy consumption on different paths by using LQI value. The chapter 5 describes a centralized linear programming approach as well as a distributed multichannel assignment for the clustered tree formation in wireless sensor networks. The network consists of randomly distributed nodes and it is partitioned using equal sized clusters. Using Binary Linear Programming Approach, the multichannel trees are formed using each clusterhead's LQI value for centralized scheme. This technique is compared with the single channel design, random tree formation design and the graph coloring based design. The results show that the linear programming based approach is better than single channel design and outperforms the graph coloring based design as well as the random channel design in terms of energy consumption and of packet reception rate but by assuming that channel conditions remain unchanged during simulation. This is an offline design technique but its performance deteriorates as the channel conditions start varying. However, it is investigated that in environments where the channel condition changes either slowly or abruptly, this scheme may reduce the network performance parameters. For that case, a distributed learning mechanism is considered to change the channel allocation based on the evolving conditions. For this case, a game theory based learning mechanism is proposed that spends a bit more energy due to increased number of configuration packets but increases the throughput and decreases the delay in comparison with other centralized and distributed tree based channel allocation techniques. Finally, chapter 6 validates the contributions proposed in chapters 4 and 5 for the considered application. This chapter shows that these schemes can deliver data in a timely and energy efficient manner.

Future Research Directions

In this thesis, we have illustrated various techniques that can improve the network performance parameters. Some techniques can be further improved to enhance the communication performance. For example, further improvements for delay and energy consumption can be obtained by proposing the design techniques for forthcoming directive antenna technologies and multiple-input and multiple-output schemes. The other aspect would be to consider different type of applications running on a single platform. These aspects are discussed below:

• Multichannel multi-interface design: If the sensor platform supports a multi-interface to the RF channel, application could benefit from this feature to improve its performance with respect to the realtime deadlines. There are a lot of multi interface designs for mesh networks where one interface is always active to receive the data on one channel while the other interface is adapted to switch to the right channel with respect to the destination node's fixed channel interface. Thus, it will help in meeting the application layer deadlines better than a single interface design where there is a packet loss due to MAC layer synchronization overhead. This type of system is explained in figure 7.1. This figure shows that for a node supporting multiple interfaces can assign a fixed channel to one interface for reception while the other interface can change its channels for transmission to other nodes. • Multiple Applications on one platform: Many embedded operating systems now support multiple application running on the same platform. There is a need to have support for different type of traffic classes for appropriate routing. For example, the traffic could be prioritized in order to support multiple applications on the network. Each class of traffic has different requirement for the application layer deadline. Based on these requirements, different paths can be chosen for each class so that it not only meet the application layer deadline but on the same time it increases overall lifetime of the network. Also, multichannel solution would be another technique that can be considered when different type of applications are running in the same environment.

• Directive Antennas: Directional antenna allows the transmission energy to be maximized in a particular direction configuring a system of multiple antenna arrays. If the transmission energy is well oriented to the receiver node, interference with other nodes in the network will be reduced. This will help in minimizing the interference between neighboring nodes and will minimize the packet loss resulting in increased packet throughput. The functionality of these type of antennas is explained in figure 7.2. • Implementation on a hardware platform: The contributions proposed in this thesis were validated through simulations using NS-2. However, these contributions need to be validated after implemention on the real hardware platform.

• Improvement of channel model for simulation: There is a need to improve the transceiver and platform energy consumption model of the network in simulation to get more accurate results. This will help in realizing the accurate analysis of the system level features as well as the transceiver.

List of Abbreviations

1 1. 2

 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Objective and Motivation . . . . . . . . . . . . . . . . . . . . 3 1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Report Organization . . . . . . . . . . . . . . . . . . . . . . . 4

Figure 1 . 1 :

 11 Figure 1.1: Example of Application Scenario

Figure 1 . 2 :

 12 Figure 1.2: Sensor Nodes Deployed in a Building

Figure 1 . 3 :

 13 Figure 1.3: General Framework

Figure 1 .

 1 Figure 1.3 illustrates the framework of our work regarding context, needs and main contributions.

Figure 2 . 1 :

 21 Figure 2.1: Sensor Network Block Diagram

Figure 2 . 2 :

 22 Figure 2.2: Available Sensor Devices Characteristics

Figure 2 . 3 :

 23 Figure 2.3: Communication versus Computation Requirement

Figure 2 . 4 :

 24 Figure 2.4: Sensor Network Application Model

Figure 2 . 5 :

 25 Figure 2.5: Sensor Network Protocol Stack

Figure 2 . 6 :Figure 2 . 7 :Figure 2 . 8 :

 262728 Figure 2.6: CSMA Mechanism ([20])

Figure 2 . 9 :

 29 Figure 2.9: Frame structure for TRAMA Protocol ([20])

Figure 2 . 10 :Figure 2 .

 2102 Figure 2.10: Funneling MAC Protocol ([17])

Figure 2 .

 2 Figure 2.12: MMSPEED Protocol Structure ([33])

Figure 2 .

 2 Figure 2.13: Micaz Power Breakdown ([20])

Contents 3 . 1 35 3. 3 . 3 37 3. 4 40 3. 4 . 1 40 3. 4 . 2 43 3. 5 45 3. 5 . 1 45 3. 5 . 2 46 3. 6

 3135333744041404243545514552466 Virtual Data Dissemination Architectures . . . . . . . . . . 29 3.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 Grid Based Data Dissemination Techniques . . . . . . . . . 34 3.3.1 Technique 1: Static Grid Algorithm . . . . . . . . . . . . . . 34 3.3.2 Technique 2: Cooperative Load Balancing Algorithm . . . . . Technique 3: Dynamic Grid Algorithm . . . . . . . . . . . . . Comparative Energy Consumption Analysis . . . . . . . . . Analysis Technique . . . . . . . . . . . . . . . . . . . . . . . . Energy Consumption Analysis Results . . . . . . . . . . . . . Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . Single Cell Network -Intra Cell Traffic Analysis . . . . . . . Multiple Cell Network -Inter Cell Traffic Analysis . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Figure 3 . 1 :

 31 Figure 3.1: Railroad Based Data Dissemination Technique (taken from [82])

Figure 3 . 2 :

 32 Figure 3.2: Line Based Data Dissemination Technique (taken from [39])

Figure 3 . 3 :

 33 Figure 3.3: Quadtree Based Data Dissemination Technique

Figure 3 . 6 :

 36 Figure 3.6: Inter and Intra Cell Communication Mechanism

Algorithm 1

 1 Cooperative Load Balancing Calculation Algorithm INPUT: Estimated Packet Forwarding Capacity per Node: µ 1 , µ 2 , ..., µ n Total Packet Arrival Rate: η PROCESSING: j ⇐ Set of Nodes having µ i ≥ η n c ⇐ η n j=1 µ j for all a ε j do β a = c * µ a

Figure 3 . 7 :

 37 Figure 3.7: Virtual Grid Based Data Dissemination

Figure 3 .

 3 Figure 3.8: Packet Forwarding Mechanism in Dynamic Grid Technique

Figure 3 . 9 :

 39 Figure 3.9: Detail of Packet Exchange Between Current Cell Head and The Member Nodes (a) Static and Dynamic Cell Head Selection (b) Cooperative Load Balancing Cell Head Selection

Figure 3 .

 3 Figure 3.10: Simulated Network

Figure 3 . 11 :

 311 Figure 3.11: Energy Consumption Profile in Homogeneous Network (a) Static Cell Head Selection Scheme (b) Cooperative Load Balancing Cell Head Selection (c) Dynamic Cell Head Selection

Figure 3 . 12 :

 312 Figure 3.12: Energy Consumption Profile in Heterogeneous Network (a) Static Cell Head Selection Scheme (b) Cooperative Load Balancing Cell Head Selection (c) Dynamic Cell Head Selection

Figure 4 . 1 :

 41 Figure 4.1: Unequal Clustering [61]

Figure 4 . 2 :

 42 Figure 4.2: SPEED Protocol Geographic Routing Based on these observations, this chapter proposes and analyze an adaptive rout-

Figure 4 . 3 :

 43 Figure 4.3: Sensors deployed in a Building

Algorithm 2

 2 Function for Choosing Next Hop INPUT: Next Hop List: L Cumulative Energy Required and Delay Expected on a Particular Path PROCESSING: next_hop = 0 PathA = minimum energy path from list L while next_hop == 0 do if PathA meets end to end deadline of the packet then next_hop = 1 // this low energy path is convenient for routing packet under end to end delay else PathA = next higher energy path from list L Elaboration:

Figure 4 . 4 :

 44 Figure 4.4: Network for Theoretical Analysis

Figure 4 . 5 :

 45 Figure 4.5: Network for Evaluation

Figure 4 . 6 :

 46 Figure 4.6: Delay Estimation Process

Figure 4 . 7 :

 47 Figure 4.7: Laxity of a Packet versus End-to-end Deadline

Figure 4 . 8 :Figure 4 . 9 :

 4849 Figure 4.8: Average Leftover Energy per Node versus End-to-end Deadline

Figure 4 . 10 :

 410 Figure 4.10: Maximum Leftover Energy Difference versus End-to-end Deadline

Figure 5 . 1 :

 51 Figure 5.1: Cluster Based Channel Allocation

Figure 5 . 2 :

 52 Figure 5.2: Tier n+1 Channel Allocation

Figure 5 . 3 :

 53 Figure 5.3: Cluster Based Tree Formation

Figure 5 . 4 :

 54 Figure 5.4: Per Packet Delay as a Function of Network Size

Figure 5 . 5 :

 55 Figure 5.5: Throughput as a Function of Network Size

Figure 5 . 6 :

 56 Figure 5.6: Average Energy Consumed per Node as a Function of Network Size

Figure 5 . 7 :

 57 Figure 5.7: Per Packet Delay as a Function of Transmission Range

Figure 5 . 8 :

 58 Figure 5.8: Throughput as a Function of Transmission Range

Figure 5 . 9 :

 59 Figure 5.9: Average Energy Consumed per Node as a Function of Transmission Range

Figure 5 . 10 :

 510 Figure 5.10: Delay in Evolving Channel Conditions

Figure 5 . 11 :

 511 Figure 5.11: Throughput in Evolving Channel Conditions

Figure 5 . 12 :

 512 Figure 5.12: Game Theory Model

Figure 5 .

 5 Figure 5.13: Game Theory Based Learning Design

Figure 5 . 14 :

 514 Figure 5.14: Average Energy Consumed as a Function of Channel Selection Period

Figure 5 . 15 :

 515 Figure 5.15: Throughput as a Function of Channel Selection Period

Figure 5 . 16 :

 516 Figure 5.16: Delay as a Function of Variation in BER

Figure 5 . 17 :Figure 5 .

 5175 Figure 5.17: Throughput as a Function of Variation in BER

Figure 5 . 18 :Figure 5 . 19 :

 518519 Figure 5.18: Throughput as a Function of Network Size

Figure 6 . 1 :

 61 Figure 6.1: Multichannel Allocation for QoS Energy Aware Routing

Figure 6 . 2 :Figure 6 . 3 :

 6263 Figure 6.2: Multichannel Allocation for QoS Energy Aware Routing (End-to-end Deadline = 0.5 sec.) for a small sized network (a) QoS Energy Aware Routing (b) Multichannel Allocation Based QoS Energy Aware Routing

Figure 6 . 4 :Figure 6 . 5 :

 6465 Figure 6.4: Multichannel Allocation for QoS Energy Aware Routing (End-to-end Deadline = 1.5 sec.) for a small sized network (a) QoS Energy Aware Routing (b) Multichannel Allocation Based QoS Energy Aware Routing

Figure 6 . 6 :

 66 Figure 6.6: Multichannel Allocation for QoS Energy Aware Routing (End-to-end Deadline = 1.0 sec.) for a large sized network (a) QoS Energy Aware Routing (b) Multichannel Allocation Based QoS Energy Aware Routing

Figure 6 . 7 :

 67 Figure 6.7: Multichannel Allocation for QoS Energy Aware Routing (End-to-end Deadline = 2.0 sec.) for a large sized network (a) QoS Energy Aware Routing (b) Multichannel Allocation Based QoS Energy Aware Routing

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.2 Future Research Directions . . . . . . . . . . . . . . . . . . . 105

Figure 7 . 1 :

 71 Figure 7.1: Multi Interface Multichannel Design

Figure 7 . 2 :

 72 Figure 7.2: Directive Antenna Design([28])

Figure 7 . 3 :

 73 Figure 7.3: MIMO Based Design ([73])

  Sensor Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Inputs and Outputs in a Sensor Network Application Model 11

	Chapter 2
	Wireless Sensor Networks
	Contents
	2.1

2.4 Geographical Division for Network Management . . . . . . 12 2.5 Routing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Medium Access Control (MAC) Protocols . . . . . . . . . . 18 2.7 Multichannel Allocation for Interference Minimization . . . 21 2.8 Cross Layer Design . . . . . . . . . . . . . . . . . . . . . . . . 23 2.9 Wireless Sensor Network Simulators . . . . . . . . . . . . . . 24 2.10 Power Consumption Model . . . . . . . . . . . . . . . . . . . 26 2.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Table 2 .

 2 1: Sensor Network Transceivers (taken from[START_REF] Incel | Multi-Channel Wireless Sensor Networks: Protocols, Design and Evaluation[END_REF])

		CC1000	CC2420
	Frequency	315/433/	2.4GHz
		868/915MHz
	Modulation	FSK	OQPSK, ASK, OOK
	Data Rate	76.8kbps	250kbps
	Transmission		50m
	Range (Indoor)
	Transmission	>100m	125m
	Range (Outdoor)
	Multi-Channel	No	Yes
	Support
	Number of		16
	Channels

Table 2 .

 2 2: Sensor Devices

	Device	Processor/Microcontroller	Memory	Wireless Features
		Intel PXA255	32MB Flash	802.11 Compact Flash
	Stargate	XScale Processor	64MB RAM	802.15.4 through
		at 400MHz		MICA2 Interface
		32-bit PXA271	32KB Flash	Integrated
	Imote2	Marvell Processor	64KB RAM	802.15.4
		at 13-416MHz
	MICA2/	Atmel ATmega 128L	128KB Flash 2.4 GHz IEEE 802.15.4
	MICAz	with 8 bit Microcontroller	4KB RAM	Compliant Radio
		at 8 MHz		250kbps Data Rate
		TI MSP430	48KB Flash	2.4 GHz IEEE 802.15.4
	TelosB	Processor	10KB RAM	Compliant Radio
		at 8MHz		250kbps Data Rate
		TI MSP430	60KB Flash	2.4 GHz IEEE 802.15.4
	PowWow	and	2KB RAM	Compliant Radio
		Actel IGLOO		250kbps Data Rate

Table 2 .

 2 3: Features of Typical Sensor Network Applications

	Applications	Data Collection	Realtime	Energy
		Scheme	Deadlines Constraints
	Environmental Applications	Time Driven	No	Yes
	Surveillance Applications	Time Driven	No	Yes
	Disaster Management Applications	Time/Event Driven	Yes	Yes
	Industrial and Building Automation Time/Event Driven	Yes	Yes
	Health Care	Time/Event Driven	Yes	Yes
	Mining Applications	Time Driven	Yes	Yes
	Maritimes Applications	Time/Event Driven	Yes	Yes

Table 3 .

 3

	1: Analytical Analysis Parameters
	Parameters	Values
	Cell Size	15m
	Initial Energy	10J
	TX Energy Consumption of Member Node	0.2W
	TX Energy Consumption of Cell Head	0.3W
	(Homogeneous Network)
	TX Energy Consumption of Cell Head	0.3W, 0.375W
	(Heterogeneous Network)	0.45W, 0.525W
	RX Energy Consumption	0.1W
	Data Transfer Rate	1Mbps
	Data Packet Size	50 bytes
	Control Packet Size	25 bytes

Table 3 .

 3

	2: Average Energy Consumption for Heterogeneous Network
		Average Energy Consumption	Maximum Energy
		Cell Head	Member Node	Consumption Difference Between
		(Joules)	(Joules)	Two Cell Heads
	Static Scheme	6.8	0.68	6.8
	Load Balancing	1.427	0.6736	0.0187
	Based Scheme
	Dynamic Scheme	1.5	0.68	1.45
	Table 3.3: Average Energy Consumption for Homogeneous Network
		Average Energy Consumption	Maximum Energy
		Cell Head	Member Node	Consumption Difference Between
		(Joules)	(Joules)	Two Cell Heads
	Static Scheme	6.8	0.68	6.8
	Load Balancing	0.9264	0.6736	0
	Based Scheme
	Dynamic Scheme	0.8	0.68	0
	• Locally Generated Packets

• Packets received from neighboring cells for onward transfer

Table 3 . 4 :

 34 Average Cell Head Energy Consumption for Homogeneous Network

	Data Generation		Average Cell Head
	Timer (sec)		Energy Consumption (Joules)
		Static Scheme Load Balancing Scheme Dynamic Scheme
	0.1	25.6	8.17	8.28
	0.4	6.4	2.11	2.05
	0.7	1	1.19	1.17
	1.0	0.56	0.84	0.82

Table 3 .

 3

	5: Average Cell Head Energy Consumption for Heterogeneous Network
	Data Generation		Average Cell Head
	Timer (sec)		Energy Consumption (Joules)
		Static Scheme Load Balancing Scheme Dynamic Scheme
	0.1	35.2	10.54	10.7
	0.4	8.8	2.6	2.7
	0.7	5.1	1.55	1.58
	1.0	3.6	1.1	1.13
	Table 3.6: Maximum Energy Difference Between Two Cell Heads for Homogeneous
	Network Data Generation		Maximum Energy Difference
	Timer (sec)		Between two Cell Heads(Joules)
		Static Scheme Load Balancing Scheme Dynamic Scheme
	0.1	25.6	3.12	0.1
	0.4	6.4	0.9	0.02
	0.7	1	0.52	0.01
	1.0	0.56	0.36	0.01
	Table 3.7: Maximum Energy Difference Between Two Cell Heads for Heterogeneous
	Network Data Generation		Maximum Energy Difference
	Timer (sec)		Between two Cell Heads(Joules)
		Static Scheme Load Balancing Scheme Dynamic Scheme
	0.1	35.2	0.72	5
	0.4	8.8	0.2	1.2
	0.7	5.1	0.1	0.7
	1.0	3.6	0	0.5
	Table 3.8: Simulation Results for 4 cell Network Average Cell Head Average Delay For a Packet
		Energy Consumption (Joules)	Generated from Cell 2 (sec)
		Homogeneous Heterogeneous Homogeneous Heterogeneous
		Network	Network	Network	Network
	Static Scheme	5.6	7.27	1.011621	1.011621
	Load Balancing	1.58	1.92	1.011331	1.011475
	Based Scheme
	Dynamic Scheme	1.58	1.98	1.013369	1.013367

  Introduction & Related Work . . . . . . . . . . . . . . . . . . 51

	Chapter 4
	QoS Aware Energy Efficient Data
	Dissemination
	Contents
	4.1

4.1.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.2 Routing Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2 Cluster Formation Phase . . . . . . . . . . . . . . . . . . . . . 54 4.3 Inter-cluster Routing . . . . . . . . . . . . . . . . . . . . . . . 54 4.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . 59 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Table 4 .

 4

		1: Analysis Parameters
	Analysis Parameter	Value
	Loss Probability, p	0.03
	Packet Size	100 bytes
	Data Transfer Rate 1Mbps (802.11)
	Packets Sent	50
	Min TX Power	0.25W
	Max TX Power	2W
	Table 4.2: Analysis Results
	No. of	Worst Case	Worst Case
	Fast Paths	Delay on	Energy Consumption
	Traversed	a Node	by a Node
	0 (P ath s )	0.0357	3J
	1 (P ath f s )	0.0284	9J
	2 (P ath f )	0.0116	16J

Table 4 .

 4

	3: Simulation Parameters Simulation Parameters Values
	MAC Protocol	CSMA based
	Buffer Size	150
	Distance between	10m
	Neighboring Nodes

Table 4 .

 4

	4: Maximum Energy Consumption by a Node
	Delay Estimation Period / Energy Consumption
	Data Generation Period	by node 4 (Joules)
	1.8	1481
	18	149.5
	180	16.3
	1800	3.7
	18000	3.3
	180000	3.3

Table 4 .

 4

	5: Average Listening Energy Consumption for a Cluster Member Node
		Minimum Cumulative Minimum Cumulative	QoS Energy
		Energy Routing	Delay Routing	Aware Routing
		(in µJ)	(in µJ)	(in µJ)
	Single channel	62	75.2	71.2
	Design
	Ideal
	Multichannel	17.6	8.8	13.2
	Design

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.1.1 Static Multichannel Allocation . . . . . . . . . . . . . . . . . 68 5.1.2 Dynamic Multichannel Allocation . . . . . . . . . . . . . . . 69 5.2 Centralized Offline Multichannel Design . . . . . . . . . . . 69 5.2.1 Network Configuration . . . . . . . . . . . . . . . . . . . . . . 70 5.2.2 Performance Evaluation of Centralized Channel Allocation . 73 5.3 Distributed Multichannel Design . . . . . . . . . . . . . . . . 80 5.3.1 Introduction to Game Theory . . . . . . . . . . . . . . . . . . 82 5.3.2 Game Theory Based Channel Allocation . . . . . . . . . . . . 83 5.3.3 Performance Evaluation of Distributed Channel Allocation . 85 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

	Chapter 5
	Multichannel Allocation
	Contents
	5.1

Table 5 . 1

 51

	: Simulation Parameters Simulation Parameters Values
	MAC Protocol	CSMA-CA Based Protocol
	Buffer Size	15
	Data Rate	1Mbps
	Distance between	10m
	Neighboring Nodes
	Cluster Head Traffic	0.1 sec
	Generation Period
	Sink Traffic	0.2 sec
	Generation Period
	Initial Energy	3J
	TX Power	0.0744W
	RX Power	0.0648W
	Field Size	50 * 50 m 2
	Number of Clusters	26
	formed using the NS-2 simulator and Cognitive Radio Cognitive Network (CRCN)
	patch

Table 5 .

 5

	2: Comparative Analysis of Multichannel Assignment Schemes
	Centralized	Distributed Tree	Distributed Game
		Based Mechanism Theory Based Technique
	Tree-based	Tree-based	Non-tree
	Design	Design	Based Design
	No Broadcast Periodic Broadcast	Periodic Broadcast
		on one channel	on all channels

Table 5 .

 5

		3: Average Energy Consumption Per Node
	Centralized Distributed Tree	Distributed Game
		Based Mechanism Theory Based Technique
	4.74 J	4.76 J	4.77 J

Table 6 .

 6

	1: Simulation Parameters Simulation Parameters Values
	MAC Protocol	CSMA based
	Buffer Size	150
	Distance between	10m
	Neighboring Nodes
	Traffic Generation Period	5 sec
	Min TX Power	0.1W
	Max TX Power	0.4W
	RX Power	0.05W
	Periodic Broadcast	1800 sec.
	of Configuration Packets
	Simulation Time	20000 sec.

List of Publications

List of Tables