Mobile Sensor Networks

FAULT TOLERANT SECURE ROUTING IN CLUSTER BASED MOBILE SENSOR NETWORKS

Abstract

Networks of low power wireless devices have introduced novel routing issues. These devices, such as sensors, smart objects, and actuators have different limitations, such as limited memory, little processing power, and extensive sleep periods. The fact that these devices are battery-powered makes the energy efficiency a critically imperative factor. This requires the protocols to make responsive decisions but with minimum topology changes and energy costs. In most of the cases their deployment is in hostile areas, which raises various security concerns. Mobile Sensor Networks (MSNs), a special class of sensor networks, inherit the properties and constraints of Mobile Adhoc Networks (MANETs), with the added limitations of resources. These constraints along with the operational characteristics of MSNs place special requirements on routing algorithms. In this research, a secure zone based routing protocol for MSN is developed. A novel zone-based protocol has been developed that divides the network into square zones. The zone head is responsible for finding route to the Base Station keeping into account the factor of mobility across every path. Path repair mechanism has been designed in order to prevent the error messages from spreading across the whole network. The network always converges to an error free state in case of broken links, due to the immediate selection of new zone head. NS-2 simulator has been used to simulate the proposed solution. It has been tested for various application environments of WSNs. The suitability of the FTSR protocol against different attacks has been analyzed. Energy consumption, scalability and throughput in static as well as mobile environments have been shown in the form of output graphs.

List of Abbreviations

WSN Wireless Sensor Network MSN Mobile Sensor Network MANET Mobile Adhoc Network ZH Zone Head BS Base Station AODV Adhoc On demand Distance Vector FTSR Fault Tolerant Secure Routing TDMA Time Division Multiple Access TTL Time To Live MAC Media Access Layer IETF Internet Engineering Task Force RREQ Route Request RREP Route Reply RERR Route Error MF Mobility Factor OTcl Object Tool Command Language

Chapter 1 1 Introduction 1.1 Background

Wireless Sensor Networks abbreviated as WSNs belongs to a class of Low power and Lossy Networks (LLNs). As the name suggests, WSNs use tightly resource constrained tiny sensing nodes that are self organizing in nature with little or no infrastructure. WSNs are gaining momentum as they have great potential for both research and commercial applications. The sensor network nodes themselves are low-priced, very small devices. Typical functions in a WSN include sensing and collecting data, processing and transmitting sensed data, possibly storing data for some time, and routing processed data as information to a base station. Deployment of WSNs in unattended hostile environment needs securing all those functions. Mobile Sensor Networks (MSNs) are composed of sensor nodes that can move under their own control or under the control of the environment. Mobile networked systems combine the most advanced concepts in perception, communication, and control to create computational systems capable of interacting in meaningful ways with the physical environment, thus extending the individual capabilities of each network component and network user to encompass a much wider area and range of data. A key difference between a mobile sensor network and a static sensor network is how information is received or delivered to or from the node. Keeping in view all the considerations of Mobile WSNs or mobility within WSN, new concerns have come to surface which has increased the complexity of network. Therefore it is required to restructure the proposed approaches in existing literature or to develop new schemes capable of handling mobility issues.

1.2 Statement of Problem

Besides all the efforts and research carried out in the field of Mobile WSNs, we still are lacking a standardized, efficient and secure routing algorithms that address the problems regarding efficient path finding, route creation, route preservation and route recreation with an added capability of avoiding impulsive degradation. The algorithm must also cater for security concerns raised by mobility and their deployment in hostile environment, with maximum fault tolerance while utilizing a minimum amount of resources.

1.3 Research Question

This thesis will attempt to answer the question, “How the routing protocols designed for Mobile Adhoc Networks (MANETs) can be altered for implementation on resource constrained MSNs, instead of designing a whole new protocol, keeping in view that the protocol is energy efficient, reliable and secure in various proposed threat models”.

1.4 Research Purpose

The background of this research has identified some key issues related to routing in MSNs. Similarities in MSNs and MANETs infer that the routing protocols designed for MANETs are strong candidates to be implemented on MSNs with such modifications that let them operate in resource constrained environment. Therefore the purpose of this research is to develop a secure and efficient, fault tolerant routing algorithm that is effective in case of mobile nodes where topology changes are more often than static nodes.

1.5 Research Methodology

The first step involves extensive literature study which will be used to lay the foundation for routing protocols in wireless ad hoc networks. The next step will use the established principles of secure routing protocols in both MANETs and static sensor networks for their analysis. This will help to identify the limitations of MANET routing protocols, and the answer to how they can be implemented on Sensor Networks specifically mobile sensor networks. Third step involves both the development of a routing protocol that is suitable for MSNs and verifying the proposed protocol in performance test simulator under various test environments.

1.6 Research Scope

The scope of this research is limited to zone based routing in mobile sensor networks where each zone consists of a zone head and a finite number of member nodes. All nodes possess same capabilities and constraints with the ability to move either at free will or depending on the application. Each node in the zone reports the sensed data to the zone head which is responsible for aggregating and routing the aggregated information to the base station. Member nodes in each zone are not aware of routing decisions and hence do not participate in routing except for special cases.

1.7 Document Organization

This thesis has been organized in chapters. Chapter 2 provides an overview of sensor networks, their characteristics, limitations, already proposed routing algorithms and their level of contribution to security and fault tolerance, emphasizing on Mobile Sensor Networks. This chapter also discusses various secure routing protocols, their effectiveness in case of mobile networks, various types of attacks, their attributes, and their effects on routing protocols for sensor networks, thus concluding the literature review. Chapter 3 proposes a more versatile secure zone based modified AODV protocol called as Fault Tolerant Secure Routing (FTSR) for Mobile Sensor Networks. This protocol has been designed keeping in view the aspect of fault tolerance and security. This chapter describes operation, path setup, path maintenance link breakage, local connectivity management and fail-safe mode of operation for our FTSR protocol. Analysis of FTSR protocol with respect to security and level of fault tolerance has been covered in chapter 4. Chapter 5 provides information on simulation methodology of FTSR and describes simulation and the results achieved. Chapter 6 concludes the whole research, and wraps up talking about the goals and objectives achieved and a way forward for new areas of research.

Chapter 2 2 Literature Review 2.1 Introduction

This chapter introduces wireless sensor networks, categorized by their types and applications. Special emphasis has been made on Mobile Sensor Networks, their existing routing protocols and their contribution to security and fault tolerance. Characteristics and requirements of secure routing protocol in sensor networks are also elaborated to provide guideline for research work. In the last section a thorough analysis of secure routing protocols has been provided.

2.2 Mobile Sensor Networks

Mobile Sensor Network (MSN) is a wireless network consisting of spatially distributed autonomous mobile devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. In addition to one or more sensors, each node in a sensor network is typically equipped with a radio transceiver or other wireless communications device, a small microcontroller, a mobilizer and an energy source, usually a battery. The envisaged size of a single sensor node can vary from shoebox-sized nodes down to devices the size of grain of dust, although functioning 'motes' of genuine microscopic dimensions have yet to be created. The cost of sensor nodes is similarly variable, ranging from hundreds of pounds to a few pence, depending on the size of the sensor network and the complexity required of individual sensor nodes. Size and cost constraints on sensor nodes result in corresponding constraints on resources such as energy, memory, computational speed and bandwidth.[1].

2.3 Applications

The applications for WSNs are many and varied, but typically involve some kind of monitoring, tracking, and controlling. Specific applications for WSNs include habitat monitoring, object tracking, nuclear reactor control, fire detection, and traffic monitoring. In a typical application, a WSN is spread over a region where it is meant to collect data through its sensor nodes.

2.3.1 Area monitoring

Area monitoring is a general application of WSNs, in which the nodes are extensively deployed over a region where some phenomenon like traffic or enemy movement etc is to be observed. Typically this type of network is composed of static sensors.

2.3.2 Environmental Monitoring

A number of WSN deployments have been done in the past in the context of environmental monitoring [2]. The environment monitoring networks are usually composite of static and mobile nodes.

2.3.3 Target Tracking

Typical network comprise of mobile node. These are mainly used for target tracking applications. These types of networks require fine grained and reliable solutions in every concerned domain ranging from application design, physical and electrical characteristics to the domains like media access, routing and data delivery with minimum latency. We are mainly concerned with this type of sensor network in our proposed research.

2.4 Routing Protocols

Mobile Sensor Networks have possessed the constraints and limitations of Wireless Sensor Networks; however their mobility pattern is some what close to Mobile Adhoc Networks. We can safely assume MSNs as an advanced representation of low powered Mobile Adhoc networks that are able to sense, predict, decide and move at their own will or on the command of their controller node. Mobility within sensor networks, that are already constrained in nature, imposes special requirements to be considered when either designing new protocols, or implementing the presently designed. Routing protocols already developed for sensor networks consider static nodes, as this assumption facilitates the design. Routes once established are never to be changed except in the case of node failure or link failure that is obvious but less frequent. Therefore very less overhead is incurred upon the network. Routing protocols for Mobile Adhoc Networks are strong candidates for routing in MSNs as they cater for mobility of the participating nodes. However, they have been designed for MANETs that are, in fact battery powered, but still not that much resource constrained as MSNs. Therefore they can not be implemented to MSNs without modification in their architecture and operation. Besides all the efforts to propose a routing protocol, it must also be considered that sensor networks are deployed in unattended and hostile environments and are much more prone to attacks resulting in the compromise of information and/or operation failure. Security measures, however stringent they are, may fall for some highly advanced and unforeseen circumstances that may halt operation in some area of network. Otherwise, whatever issue the network is facing in terms of a network segment failure, our aim is to provide a mechanism that the network failure in one segment does not spread across the entire network. The network must have the capacity to endure path failures due to network segment faults. A reliable mechanism of information flow must always be there with minimum overhead, i.e. over head of route discovery. Following is the brief description of the currently proposed routing protocols for sensor networks. The performance analysis metrics consist of the level of security, fault tolerance, mobility, scalability, power awareness and estimated overhead.

2.4.1 TinyOS Beaconing

The TinyOS beaconing protocol is a simple recursive routing protocol which relies on the spanning tree algorithm. It creates a breadth first spanning tree with the sink as a root. 2-2 depicts the tree like structure of TinyOS beaconing protocol. The sink broadcast a route update after specific intervals of time and all nodes that receive the update marks the sink as its parent. The broadcast is relayed by each node across the network. This process continues with each node marking the first sender node as its parent. All packets sent or received by a node are handed over to the parent node which in turn forward them to its parent until they reaches the sink.

2.4.2 Directed Diffusion

Directed diffusion [4] uses a data centric approach to fetch information from the network. Base station disseminates the inquiry packet across the network and is called as ‘interest'. This interest is flooded across the network which in turn creates the path towards the base station to fetch the data. This path is called the ‘gradient' for the reason that the data flows through this path. All those nodes that satisfy the interest route the information via the reverse path. The protocol supports multipath propagation as the nodes receiving the same interest from multiple neighbors can use the multiple links to route the data to the base station. An interesting feature of this protocol is the support for variable data rates. The base station can instruct the neighboring nodes for higher or low event reporting data rate which in turn disseminate the enforced data rate towards the reporting nodes, The multipath version of directed diffusion can also be employed by using the same enforcement method with first creating the primary data flow, subsequently followed by the alternate routes. These alternate routes are established with maximal disjointedness.

2.4.3 Geographic Routing

Geographic and Energy Aware Routing (GEAR) and Greedy Perimeter Stateless Routing (GPSR) assume that the nodes are aware of their geographic position in the network. The packets produced across the network are also location aware of their destination in terms geographic position. GPSR forwards each packet to the neighbor close to the destination and hence it calls it greedy forwarding. To overcome empty portions of network GPSR creates routes around the perimeter of the empty portion of the network. Uneven energy consumption within the network is the major drawback for this routing protocol as it always uses the same nodes along the path for a single flow of data. This problem is remediated in GEAR, as it gives the choice of selecting the next hop by calculating the cost of routing in terms of remaining energy and the distance of node form the target. This helps in distributed energy consumption across the entire network between the source and the base station.

2.4.4 Minimum Cost Forwarding

Minimum Cost forwarding algorithm is stateless protocol which does not require nodes to maintain explicit information regarding paths or nodes identifiers. It is an efficient algorithm that works by constructing a cost field that starts at the base station with base station having the cost zero. The minimum cost to reach the base station is calculated at each hop. This cost can represent any metric depending on the application type, that is, energy, packet loss, hop count etc. Each node in the network except base station is assigned a cost and is initialized as infinity. Cost values are flooded across the network in the form of a beacon that is initiated by the base station. A node M broadcasts it cost which is received by N, a neighboring node. N has now got the information regarding path cost CM + LNM. The node N compares its current cost CN with received cost. If the received cost is smaller than CN then the node assigns the CN = CM + LN.M and rebroadcast the advertisement with this new cost. An optimized approach is also presented by the authors. They recommend a method to reduce the number of messages sent across the network to establish minimum cost field. As the node cost is updated, it delays the rebroadcast advertisement containing its new cost for the time proportional to the link cost in the received advertisement. The source node calculates the link cost budget which is equal to the minimum cost calculated for the path between the source and the destination and put it in the message initiated. The link cost of the hop is subtracted from the budget at each hop and the message is broadcasted. A node receiving the broadcast forwards the message only in the case if the remaining budget is equal to that node's own minimum cost. A multipath version also exits that is known as credit-based mesh forwarding [6]. This approach uses the concept of “credit” which is given to the message beyond the minimum cost of the source, which results in multiple nodes to forward the packet.

2.4.5 LEACH: Low-Energy Adaptive Clustering Hierarchy

LEACH protocol [7] uses the concept of clustering to disseminate queries across the network and gather the sensed data from all nodes in the network. LEACH works by setting up the nodes into clusters with one node acting as cluster head. Nodes first send the sensed data to their respective cluster heads, which in turn aggregates the data from it “children” nodes for transmission to the base station. If the protocol is using static cluster head selection mechanism, the node selected as the cluster head soon runs out of energy and die. LEACH uses random selection of nodes as cluster head so that energy remains distributed within the network. The whole operation is divided into rounds, with each round having a set-up phase and a steady state phase. At the start of setup phase, each node decides whether or not to be the cluster head, based on the probabilistic analysis of it remaining energy and the globally known desired percentage of cluster heads. The node willing to become a cluster head broadcast an advertisement message to announce itself as the cluster head. Other nodes that receive the broadcast, which may be more than one from several cluster heads, join the cluster head on the basis of largest received signal strength. Nodes send a joining request to the cluster head, which in turn sends back a TDMA schedule for sending data. In the steady state phase the cluster head listens to the child nodes for incoming data within their clusters and aggregates and send the data to the base station.

2.4.6 Rumor Routing

Rumor routing protocol[8] works on the basis of probabilistic matching of queries with data events. Gossiping and flooding [9] of events and queries across the entire network are the two possible method for doing this, but both have high energy cost associated with them. Rumor routing has an alternate energy efficient mechanism which can be used when the high cost of flooding is unable to be justified. It recommends the dissemination of query on a very small group of nodes, which in turn result in limited event reporting. The rumor routing protocol is agent based, which is sent across the network by the source of the data packet as soon as it sense an event. Agent carries a lot of useful information such as a list of events, a time to live field, list and count of hops towards those events. For straight paths and avoiding loops, the agent also carries the information regarding previously visited nodes and their neighbors. Every node that is visited by the agent is informed of the events that agent is carrying and the next hop towards those events. The node in turn responds to the agent with the list of events that the agent is possibly missing. If the TTL value in the agent has not expired the node chooses the next hop for the agent form its neighbor list excluding the one previously visited. The same procedure is adopted by the base station. It disseminates an agent which propagates across the entire network carrying the query by the base station.

2.4.7 GAF: Geographic Adaptive Fidelity

GAF [11] works by placing the nodes into square grids according to their geographic location and radio range. Nodes in adjacent grids are able to communicate with each other. Three states are observed by each node in the network, sleeping, discovery and active. Nodes participating in the routing are marked as active nodes while nodes in discovery mode probe the network to determine whether their presence is needed or not. Nodes use the discovery messages to exchange state information within each grid. Ultimately GAF reaches a state in which each grid has only one active node.

2.4.8 SPAN

SPAN [12] uses the concept of coordinator nodes that form the backbone within the network. Other nodes act in either of the two states, that is, to sleep or to join the backbone. The coordinator nodes continuously stay awake during their life time, while other nodes remain in power saving mode and send and receive HELLO messages to determine if they are required to act as coordinator. The coordinator nodes are responsible for path discovery and data delivery to the base station

2.5 Network Assumptions for Security

Sensor networks bear some intrinsic characteristics and a few assumptions regarding the network setup are to be derived before suggesting any security architecture or trust requirements. As the sensor networks use wireless communication which is insecure, they are susceptible to eavesdropping The physical and MAC layers are also susceptible to direct attack. The attacker can jam the signals by transmitting high frequency signals. For MAC layer an adversary can send Clear to Send (CTS) frames with long duration fields, which may result in choking the channel.

2.6 Trust Requirements for Secure Routing

Base stations are used to provide connectivity of a sensor network to the outside world. A base station is usually a powerful node with high capabilities than normal sensor nodes. For this reason it is assumed that the base stations are trustworthy and behaves correctly. Aggregation points present in the network, if different from normal nodes, may be worth trusting in certain protocols. In these protocols the nodes rely on aggregation points for transferring data and assume that the information will be accurately combined with other information before forwarded to the base station. Aggregation points may not be trust worthy in case they are ordinary nodes.

2.7 Security Goals of Routing Protocol

The security goals like confidentiality, integrity, authenticity, and availability of all messages in a network are the intended achievements for a security framework. Every message produced in the network must reach the eligible receiver. Message integrity and sender's identity verification must be performed and no node in the network other than those intended can be able to infer the contents of the message even if are the participant in the delivery of the message. However which of these goals are to be addressed by a routing protocol and which ones are the responsibility of other layers is a question that need to be addressed. The foremost security goal of routing protocol in conventional network is the reliable delivery of messages. Message authentication, integrity and confidentiality are the security goals of upper layers. The reason for this grading is because of the fact that intermediate nodes in the path are not eligible for viewing information beyond the headers required for their working i.e. routing headers. The same is not the case for sensor networks as in most of the cases the flow of information can be regarded as many to one with many sensors sending their sensed data to a single base station. Processing of this information such as aggregation or data compression in side the network is necessary for energy efficiency. This kind of information processing requires the intermediate nodes to access and modify the data, so upper layer or end-to-end security mechanisms are not a viable solution within such networks. Link layer security mechanisms, if applied, can be effective in case of outside attackers, because they prevent the adversary form joining the network. However, an inside attacker have much more capability to modify or suppress the contents of the message. Therefore, the link layer security mechanism is not a viable solution for securing the routing protocols and there is a need for integrating security parameters in the design of a routing protocol. In the presence of inside adversary, there is likely a case that not all of these goals are fully attainable. However, instead of a fully comprised network, we must look forward for a graceful degradation. The effectiveness of a routing protocol can be measured in terms of the rate of degradation in the network services and that must be proportional to the ratio of the compromised nodes in the network [4]. One thing that must not be the goal of secure routing protocol in any case is the replay of data packets. Application layer is best responsible for providing such functionality instead of routing layer.

2.8 Attacks on Sensor Network Routing

Sensor network routing protocols are inherently simple and a often susceptible to attacks. Network layer attacks against sensor network can be broadly categorized into one of the following categories [4]. * Spoofed, modified, or retransmitted routing information, * Selective forwarding, * Sinkhole attacks, * Sybil attacks, * Wormholes, * HELLO flood attacks, * Acknowledgement Spoofing. These categories are discussed in detail in the further subsections.

2.8.1 Spoofed, Modified, or Retransmitted Routing Information

The most lucrative attack to be mounted by an adversary is against the routing information exchanged within the network. Possible ways may be to spoof, modify or replay the routing information. As a result the adversary is able to create routing loops, generate false errors in the network, disturbs the routes or may increase end-to-end delay.

2.8.2 Selective Forwarding

In selective forwarding attack, the malicious nodes may either refuse to forward certain messages and drop them or entirely attract the traffic towards itself. A simplest form is the “Black Hole” attack in which the node refuses to forward the packets. Such attack loses its significance if the neighboring nodes seek some other route for data transmission, as it often happen in adhoc networks. Selective forwarding attack is possible when the malicious node is included in the path of data flow. The selective forwarding attack is complimented by sink hole attack and sybil attack, both of which are discussed in further sections.

2.8.3 Sinkhole Attacks

In the sink hole attack the adversary attract nearly all traffic from a targeted area with the help of a compromised node. The theme is to create a sinkhole with the adversary at the center. The compromised node appears attractive to the surrounding nodes for routing data. This compromised node can completely drop the traffic, selectively forward a few as in selective forwarding or just replay all with more or less modification.

2.8.4 The Sybil Attack

In a Sybil attack [27], a single node appears to other nodes in the network as having multiple identities. The Sybil attack effectively reduces the performance of fault-tolerant protocols such as distributed storage [28], multipath or geographic routing [30], and topology maintenance [11]-[12]. Routes believed to be using disjoint nodes or disjoint paths could actually be using the same malicious node that is presenting itself as multiple nodes.

2.8.5 Wormholes

In the wormhole attack [31], the adversary creates a tunnel between two distant locations and captures messages from one part of the network and replays them over a low-latency link in the far end of the network. This can be done by capturing two nodes in the network and make them collude to act as a tunnel. Wormholes can also be used to convince two distant nodes that they are close to each other by transferring packets between them with low latency. Wormhole attacks are more likely to be effective when used in combination with eaves-dropping or selective forwarding. 2-3 above shows an example of a wormhole being used to create a sinkhole.

2.8.6 HELLO Flood Attack

HELLO packets are exchanged between two nodes to announce their presence to each other in most of the routing protocols. These packets make the receiving nodes to assume that it is within the neighborhood of sender. This may lead to a misconception and the adversary is able to convince multiple nodes that it is their neighbor with actually being at a distant location.

2.9 Analysis of Routing Protocols

The recent research results on data routing in sensor networks has been summarized in the table 2-1 shown below. The table shows how different routing protocols fit under different category and also compare different routing techniques according to many metrics. From the table 2-1, it can be concluded that none of the protocols so far developed for sensor networks are safe from attacks and neither has they provided a way to recover from attacks.

Table 2?1 Summary of Routing Protocols

Protocol Classification Mobility Data Aggregation Fault tolerance Scalability Possible Attacks TinyOS Beaconing Flat Limited Yes No Limited Wormhole/sinkhole, selective forwarding, HELLO Flood. Directed Diffusion Flat Limited Yes No Limited Selective forwarding, Data Cloning, Sybil. GEAR Location Limited No No Limited Sybil, selective forwarding GPSR Location No No Yes Good Sybil, Routing loops MCFA Flat No No No Good Sinkhole, HELLO flood LEACH Hierarchal No Yes No Good HELLO Flood, Selective forwarding Rumor Routing Flat Very limited Yes No Good Sinkhole, wormhole, selective forwarding GAF Location Limited No No Good Sinkhole, HELLO flood SPAN Location Limited No No Limited Network partitioning, selective forwarding For those protocols that support mobility is by the virtue of their operation, and not that they are specifically designed keeping in view the problems created due to mobility. To cater for mobility specific fabrication is necessary at design time to maximize the efficiency of the routing protocol. IETF [3] has presented a draft document for routing protocols in low power networks, including sensor network. It recommends that instead of designing a whole new protocol for low power networks, its best to implement a low cost version of MANET protocols. It has evaluated certain MANET routing protocols and their feasibility of implementation on sensor networks with or without modification. The metric consist of route table scalability, loss response, control traffic, link and node cost of transferring data. The most studied of all protocols is the Adhoc On demand Distant Vector (AODV) [33] Routing Protocol. In terms of control traffic, AODV does not generate any traffic until data is sent, and as control traffic is correlated with the data, there is always less control traffic. AODV table size expands with increase in number of communicating nodes, which are always two in case of sensor networks by the virtue of operations. However in case of loss response, the RERR message is generated to all nodes that are currently in the precursor list, which may reach those nodes that are not currently using the route to send data. In case of link cost hop count is the only metric and for node cost AODV has no mechanism to ensure node's willingness or ability to send data [3].

Chapter 3 3 Fault Tolerant Secure Routing in Mobile Sensor Networks 3.1 Introduction

Mobility in sensor networks has not only expanded the role of sensor networks but has also given a whole new dimension to all research. Extra vigilance and unique approaches are required to address the concerns raised due to mobility. Therefore, we present a novel Fault Tolerant Secure Routing (FTSR) protocol that is not only efficient in securing routing information in hostile environment but also capable of reducing network segment errors, such that routing information is always available in the underlying network. In this research we have modified the AODV for mobile sensor networks such that the zone heads are responsible for routing and route error response is confined to active sender zone heads only. In case of link cost the metrics consist of hop count and accumulated mobility factor along the path, and in case of node cost the zone head responsible for routing data is the one that is less mobile of all nodes in the zone and hence it has more energy left with it. Both of these factors ensure that the path selected for routing data will be available for longer duration. The operation of FTSR is divided into three phases. First is the zone creation and zone head election. Second phase includes path discovery and maintenance mechanism to provide maximum reliability. The third phase is the fail-safe mode of operation that is only activated in case of severe network failures.

3.2 Initial Network Setup

A typical sensor network is randomly distributed nodes, across the phenomena with one or more base stations outside the phenomena. Due to the unattended operational nature of the network, it is never feasible to arrange the nodes in fix topology before hand. However, for reducing operational complexity we can have them arranged in such a manner that produce less overhead and is able to simply utilize information available within the node about its location, instead of complex computation. The FTSR protocol make use of the fact that the nodes in the network are aware of their location in the form of (x, y) coordinates. The entire sensor field is divided into M × N square zones, where M and N are integer values. The zone size ‘SZ' is broadcasted by base station and all nodes adhere to the value of ‘SZ' while computing their membership for specific zone. Being mobile it is customary for each node to keep a record of its movements, location, and destination. In our protocol we have used this fact to facilitate the prediction of movement of the nodes in terms of a factor of mobility and remaining energy named as Mobility Factor (MF). It has been thoroughly explained in section (3.2.2) as it plays a pivotal role throughout the network operation.

3.2.1 Zone Creation

At the time of network setup, base station announces its own location and the value of ‘SZ' to the entire network. Each node, knowing its location within the sensor field calculates the zone identifier IDZ of its respective zone. For example a node having location {27, 19} in a sensor field of 100 square meters with a zone size 10 square meters will have a IDZ of {2,1}. As soon as the nodes finish calculating their respective zones, there is an immediate need for zone head.

3.2.2 Mobility Factor and Zone Head Selection

At time of initial network setup, all nodes are equal in their status in the network, that is, they have the same startup energy, they are all static and they have not been assigned any task, for example, monitoring or sensing . The first step is to calculate the mobility factor of each node. For this a node computes the number of moves made in time ‘t' seconds. Here a move is considered as the change in location of a node without a pause, irrespective of the distance, destination and direction. Mtotal is the total number of moves and CZone is the total number of zone changes that the node has made during its life time. MF is given as Where e' is the remaining energy of the node at the specific time ‘t' seconds. Smaller value of MF depicts less mobility of the node and makes it a potential candidate for zone head. The larger value of MF declares that the node is highly mobile and must not be relied as the zone head because it will soon move to another zone possibly causing a disruption in routed traffic. At the time of network setup, however, all nodes may possess the same MF, so a random number is chosen as MF to avoid initial perplexity. As the node ‘A' calculates the MF, it broadcast the information along with its IDZ. This information is heard by all other nodes within the broadcast range. Nodes having the different IDZ immediately drop the broadcast. All other nodes within the same zone accepts this broadcast if and only if the received MF is less than their own MF or less than some previously received MF from any other node within their zone. If any node ‘H' listens to the broadcast from nodes ‘A', ‘B', ‘C' and ‘D' in time ‘tA', tB, tC, tD respectively and finds that its own MF i.e. MF(H) is less than all of the broadcasts received, the node H declares itself as the zone head (ZH). Subsequently at its respective time ‘tH' the node broadcasts its own MF(H). All other nodes receiving the broadcast adhere to the same comparison rule. On finding MF(H) as the least mobility factor received within time 't' seconds, the nodes declare H as their zone head. This procedure is adhered by all nodes and a random delay DRAND is added for each broadcast to avoid collision.

3.2.3 Key Exchange

After the zone head election procedure every zone ends up having a zone head recognized as ZHZID. The zone head shares a group secret key with its neighbor zones i.e. not more than eight in any case as shown in 3-2. A pair-wise key is exchanged between each zone head and the base station. An efficient and scalable group key management protocol for cluster based mobile sensor networks proposed in [32]. The protocol presents a viable key distribution and revocation scheme for sensor networks with mobile nodes. The scheme is efficient in case of nodes leaving or joining the zone.

3.2.4 Local Information and Connectivity

Each node in the zone maintains the information about zone identifier as IDZ and its respect zone head identifier as IDZH. Zone head bears additional information about its neighbors and routes in the routing table. For the sake of neighborhood knowledge each zone head keep a record of its connectivity to active (i.e. data sending) next hops as well as those neighbor zone heads that have transmitted signed Hello messages during the last (ALLOWED_HELLO_LOSS) × (HELLO_INTERVAL) seconds. HELLO messages are signed by computing MAC with the group key it shares with its neighbors. MAC can be calculated using keyed hash functions [35]. ZHA à *: {IDA, IDZ, nonceA} || MAC {IDA, IDZ, nonceA}KG Where nonce is a random number generated by ZHA in this case. Each neighbor generates a reply to this HELLO message, including the nonceA, and computing MAC with the group key it shares with ZHA. This offers a confirmation that the link is bidirectional and prevents ZHA from accepting false HELLO replies that it has not generated. The HELLO reply message format from ZHB, a neighbor of ZHA, is given as ZHB à ZHA: {IDB, IDZ, nonceA} || MAC {IDB, IDZ, nonceA}KG

3.3 Protocol Operation

The sensor nodes deployed within the phenomena are required to report the event as soon as any activity is observed in the respective region. The data flow depends on the specification of application being used. It can be broadly divided into three categories, when a node is i. Static ii. Static and at times it becomes mobile. iii. Fully mobile (in case of target tracking application) Whatever the case may be, the member nodes transmit data to their respective zone head, which is always one hop neighbor of all member nodes. Zone head can perform the aggregation depending on the type of application and transmit the aggregated or individual data to the base station. Route discovery, maintenance and consistent availability of route for reliable data delivery are the core responsibility of the zone head. Whenever there is a need to transmit information to the base station the respective zone head generates the route request, which in turn is distributed across the network via our proposed routing algorithm until it reaches the base station. The base station upon receiving the request generates a reply across the desired path and hence the route is established. In our research, we have proposed a modified and secure version of Adhoc On-Demand Distance Vector (AODV) routing protocol. This modified version will function as the underlying routing protocol in our proposed zone based network architecture. AODV have some core functions like RREQ, RREP and RERR for route discovery and maintenance. In the remaining of this section, first we have presented the packet formats used by FTSR protocol. Later the protocol operation is described in terms of - RREQ generation and its processing at intermediate nodes - RREP generation and its processing at intermediate nodes - RERR generation and dissemination Next we have explained the phenomena of Fail-safe mode of operation in case of severe network segment faults in section (3.4).

3.3.1 Route Request

The format for Route Request (RREQ) message for FTSR is as under. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | F | RREQ ID | Hop Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Node Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Zone Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Node Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Authentication Code | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The illustration of the fields in the proposed RREQ is given in table below.

Table 3?1 RREQ field Description

Field Name Description Type 1 F A Flag value depicting fail-safe mode of operation RREQ ID A number that uniquely identifies the specific RREQ when taken in combination with the source node's ID. Hop Count The total number of hops from the source to the node handling the request. Reserved Reserved field for fail-safe mode of operation. Destination Node Identifier The address for which a route is required. i.e. base station Destination Sequence Number The latest sequence number received by the source corresponding to the particular destination. Originator Zone Identifier Zone Identifier from which the node requested the route. Originator Node Identifier Identity of the source which generated the packet. Originator Sequence Number The current sequence number of the source to be used for corresponding request. Message Authentication Code Keyed Hash Message Authentication Code of all non-mutable fields of RREQ.

3.3.2 Route Reply

The format for Route Reply (RREP) message for FTSR is as under +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Hop Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Node identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Zone Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Node Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Authentication Code | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Table 3?2 RREP field description

Field Name Description Type 2 Reserved Sent as void. Used in fail-safe mode of operation. Hop Count The total number of hops from the source to the destination Destination Node Identifier The address for which a route is required. i.e. base station Destination Sequence Number The destination sequence number associated to the route. Originator Node Identifier Address of the originator of the RREQ, the one for which the route is supplied. Originator Zone Identifier Zone identifier from which the route request was originated. Lifetime Time in milliseconds for which the route is considered to be valid. Message Authentication Code Keyed Hash Message Authentication Code of all non-mutable fields of RREP.

3.3.3 Route Error (RERR) Message Format

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | N | RERR Originator ID | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination Identifier (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination Sequence Number (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The Route Error message format is illustrated above. The description of the fields is given in table below

Table 3?3 RERR field description

Field Name Description Type 3 N No delete; A flag that is set when a node has carried out a local repair of a link, and data sending nodes should not discard the route. Reserved Sent as 0 and ignored by the receiving node. DestCount The number of destinations that became unreachable. Must be at least 1. Unreachable Destination ID The ID of the unreachable destination (i.e. base station) Unreachable Destination Sequence Number The sequence number related to Unreachable Destination ID field.

3.3.4 Generation of Route Requests

A zone head broadcasts RREQ when it needs a route to the base station and does not find one available in its route cache. This happens in the case when the base station is unknown to the zone head, or if a formerly valid route to the base station has expired or is marked invalid. The Destination Sequence Number field is the last known destination sequence number for the base station and is initialized to zero if no sequence number is known. The Originator Sequence Number is the zone heads' sequence number, which is incremented before inserting it into RREQ. The Originator Zone Identifier (IDZ) is the zone in which the originator of the RREQ exists. The advantage of using the IDZ has been further described in section (4.2). The RREQ ID field is increased by one from the last RREQ ID used by the current zone head. Each zone head keeps only one RREQ ID. The Hop Count field is initialized to zero. A Message Authentication Code (MAC) is calculated over all non-mutable fields of RREQ using the unique key the zone head shares with the base station. A keyed hash function can be used to calculate the MAC. 1. Before broadcasting the RREQ, the originating zone head buffers the RREQ ID and the Originator NODE_ID (its own address), Originator IDZ (of its own zone) and MAC of the RREQ for PATH_DISCOVERY_TIME. This helps the node to identify if it receives the same packet again and avoid reprocessing and re-forwarding it. 2. A node can not originate more than RREQ_RATELIMIT request messages per second. 3. After broadcasting a RREQ, the zone head waits for a RREP (or other control message) with up to date information for the route. 4. If no route is received for a specified time limit, the zone head tries again to discover a route. It does so by broadcasting another RREQ, up to a maximum limit of RREQ_RETRIES times. The Originator zone head increments the RREQ ID for each new RREQ it generates. The method of sending RREQ retries is comprehensively modified from the normal AODV operation. Therefore it makes up the major component of FTSR Fail-safe mode of operation and is fully elaborated in section (3.4).

3.3.5 Processing and Forwarding Route Requests

When a RREQ reaches an intermediate zone head, it first verifies the sender and creates a reverse route to the previous hop. Afterwards it verifies whether it has received a RREQ with the similar Originator Node Identifier and RREQ ID within a specified time limit. If a similar RREQ has already been received, the zone head rejects the newly received RREQ. The remaining part of this subsection explains the actions taken for RREQs that are not rejected. First, it increments the hop count in the RREQ by one. Then the zone head creates or updates the reverse route towards the originator by using the Originator Sequence Number from the RREQ in its own routing table. This route will be used to forward a RREP back to the source zone head. Along with this, the following actions are also carried out, The Originator Sequence Number is matched to the related destination sequence number in its route table entry and updated if greater than the existing value present. The valid sequence number field is made true. The sender zone head and its respective zone from which the RREQ was received (may not be equal to the Originator Node Identifier or Originator IDZ field in the RREQ message) is maintained as the next hop. The hop count becomes the Hop Count in the received RREQ. Whenever a RREQ message is received, the Lifetime of the reverse route entry for the originator node is set to be the maximum of (ExistingLifetime, MinimalLifetime), where MinimalLifetime = (current time + 2 × NET_TRAVERSAL_TIME - 2 × HopCount × NODE_TRAVERSAL_TIME) as described in original AODV protocol [33] . If the TTL value in the incoming packet is larger than 1, the node updates and replays the RREQ. To update the RREQ, the TTL value in the outgoing packet is decremented by one. Also the Hop Count field is increased by one, to account for the new hop through the intermediate zone head. At last, the Destination Sequence Number for the base station is set to the maximum of either the one that is received, or the other which the zone head currently maintains for the bas station.

3.3.6 Generating Route Replies

Contrary to the normal operation of AODV, the FTSR protocol modifies the generation of RREP as intermediate zone heads are not allowed to generate RREP in any case. The advantage of forcing this restriction is described in section (4.3). When the RREQ reaches the base station, the base station verifies the sender from its neighbor list and establishes a reverse route with the sender. Afterwards it computes MAC over the non-mutable fields of RREQ with the key it shares with the Originator zone head and compares it with the MAC received within the RREQ. In case of any discrepancy the RREQ is immediately discarded. Otherwise, upon successful comparison the base station gets ready to generate the RREP. When generating a RREP message, the base station copies the Destination Node Identifier (its own ID as received in RREQ) and the Originator Sequence Number from the RREQ message into the corresponding fields in the RREP message. The base station places its sequence number into the Destination Sequence Number field of the RREP, Hop Count field of the RREP is set to zero and the value of route Lifetime field is set for the current RREP. After all this, the base station computes the MAC over the non-mutable fields of RREP, using the key it shares with the Originator and concatenate it with the RREP. The RREP is then unicast to the next hop toward the source of the RREQ. The Hop Count field is increased by one at each hop as the RREP is sent back towards the zone head which created the RREQ message. When this RREP reaches the originator, this Hop Count represents the total number of hops, to the destination from the originator.

3.3.7 Receiving and Forwarding Route Replies

When an intermediate node receives a RREP message, it verifies the sender by its neighbor list. Upon knowing that the sender is a verified neighbor and the intermediate node maintains a secure local connectivity with it, the node start processing the RREP. If required, a route is formed for the previous hop. Next, the node increases the hop-count value in the RREP by one, which is referred as "New Hop Count". The forward route for the base station is then formed if it does not already exist. Else, the node compares the Destination Sequence Number in the message with the stored destination sequence number for the originator of the RREP. When compared, the existing entry is updated in the following conditions: 1- The sequence number is set to invalid in the route table entry. 2- The Destination Sequence Number in the received RREP is greater than the one with the node and the known value is valid, or 3- The sequence numbers are identical, but the route has been inactive, or 4- The sequence numbers are same, but the New Hop Count is lesser than the hop count in its stored route table entry. If the entry in the route table is created or updated for the destination, the following actions happen: - The route is set active. - The destination sequence number is set valid. - The next hop in the route cache becomes the node which sent the RREP, - The hop count changes to the New Hop Count, - Lifetime parameter in the RREP message adds up to the current time to become the expiry time, - The destination sequence number is the same as in the RREP message. The current zone head can then employ the same route to forward data to the base station. If the current zone head is not the destination of the RREP then it forwards the RREP towards the destination which is actually the originator of RREQ, using the information in its route table entry.

3.3.8 Route Error (RERR) Messages

In general, a route error and link breakage mechanism requires the following steps: - Marking the existing routes as invalid. - Determining the neighbors which may be affected. - Sending a RERR message to the affected neighbors. In sensor networks, links usually flap more frequently due to being close to the SNR threshold. In case of MSN topology changes are more frequent. It is important that link flapping not trigger needless responses from the routing protocol. The need is to localize the responses to link failures without setting off network wide re-optimization, whether for reducing network traffic or for maintaining low route convergence times. The routing requirements draft [3] states that protocols must be able to "recompute paths based on underlying link characteristics which may change dynamically". The protocol should also "always be in the process of optimizing the system in response to changing link statistics." Protocols with these properties should take care not to require global updates. Although, AODV has been developed for Mobile Adhoc Networks, however it performs best when the nodes are static or mobile to a limited extent. There are intense performance issues with AODV when it comes to loss response and error reporting. When routes break due to topology changes, AODV floods error messages and issues a new request because AODV is an on-demand routing protocol and it only maintains routes for active nodes. When a link breaks, AODV generates a Route Error (RERR) and a new RREQ, with a higher sequence number. It prevents the nodes from responding out of their route caches. These packets can flood the entire network, giving loss response a fail and hence can not be implemented in sensor networks without modification [3]. In FTSR, we have anticipated a finer version of loss response and error reporting mechanism. Thus, reducing the overall cost of error, and restricting the propagation of error message across the entire network. The zone head starts processing a RERR message in the following three situations: 1- If while transmitting data, a link break occurs for the next hop and if it has waited (MAX_HELLO_LOSS × HELLO_INTERVAL) (and a route repair if not successful) or 2- If a data packet is received for a node which it does not know or don't have a route or else it is also not in the process of repairing, or 3- If a RERR is received from a neighboring zone head for at least one active route. Suppose that ZHS is using a link disjoint path to deliver data to BS. ZHS à ZHA à ZHB à ZHC à ZHDà ZHE à BS Link break occurred at this path between ZHB à ZHC. There are two possible causes 1- ZHC is dead, possible reason being battery starvation. - Immediate local repair MUST occur at Zone level. The member nodes upon receiving link layer error message for their connectivity loss to the zone head initiate the zone head election procedure as described in section (3.2.2) always followed by key exchange as in section (3.2.3). The new zone head will immediately broadcast HELLO packet to inform its availability. - Meanwhile, ZHB buffers the incoming packets, unicast RERR destined for Originator(s) with ‘Route in Repair' Flag set to its previous hop(s) towards the Originator(s) currently using the route to send data, so that they can stop transmitting the data. In our example case this is ZHA which first receives the error message. - The maximum time for selecting a new zone head in zone ‘C' MUST NOT exceeds (MAX_HELLO_LOSS) × (HELLO_INTERVAL). - Link restoration leads to route update at ZHB. Buffered packets will be sent to the base station. ZHB unicast RERR with ‘Route Restored' flag to Originator(s) via reverse path to restore data transmission. - In case the path is not repaired within (MAX_HELLO_LOSS x HELLO_INTERVAL), the route will be marked as invalid and ZHB will initiate path discovery. 2- ZHC has moved out of range from ZHB but is still in range with its member nodes. In this case there will be no initiation of zone head election procedure. - ZHB buffers the incoming packets, unicast RERR destined to Originator(s) with ‘Route in Repair' Flag set to its previous hop(s) towards the Originator(s) currently using the route to send data, so that they can stop transmitting the data. In our example case this is ZHA which first receives the error message. - In case the path is not repaired i.e. the ZHC does not come back in range within (MAX_HELLO_LOSS × HELLO_INTERVAL) time, route request is issued by ZHB that is the intermediate node towards the Originator. Path is updated at ZHB as the link is restored. Link restoration leads to route update at both ZHB and ZHD. Buffered packets will be sent to the base station and ZHB unicast RERR with ‘Route Restored' flag to Originator(s) via reverse path to restore data transmission.

3.4 Fail-safe Mode of Operation

Data transmission in sensor networks only happens whenever an activity is detected within a region or for reporting results for a task disseminated by the sink. The flow of this data transmission is always unidirectional i.e. from nodes towards the base station. Sensor networks, being low on resources, avoid using costly acknowledgements for any kind of packet transmission. This section explains the Fail-safe mode of FTSR protocol. This mode is defined to overcome the effect of severe network segment errors and to ensure reliable data delivery path even in the case of network faults. This mode augments the zone based fault tolerance functionality of FTSR protocol. In the case of mobile nodes, the nodes move frequently resulting in topology changes. Although the zoning mechanism reduces the effects of mobility by containing the topology changes with respect to zone heads only. However there might be a chance in a less denser network that a zone head is unable to communicate with its neighbors due to empty zones or just in case that a zone head goes out of range with its only neighbor. So the zone head might fail, either to transmit its own data or be a part of its neighbor's route to which it is the only serving zone head in the path. So, it is possible that a RREQ transmission never reaches the base station. Normal AODV uses the method of “expanding ring search” [33] in which it increases the TTL value and the node density parameters for repeat RREQs. This mechanism can not be utilized in our zone based mobile network, because our protocol does not depend on network density. Instead we mainly focus on non-empty zones with nodes as least as one.

3.4.1 Generating RREQ in Fail-safe Mode

If the originator of the RREQ does not receive a RREP from the same route discovery attempt, the originator reattempts route discovery after a timeout (description in section 3.3.4). However, this process might be repeated without any progress, and no route is found even after many retries. This can happen for an infinite number of times and may leave the network in a perplexed state. Our zone based approach uses a fail-safe mode of operation, in case when a zone head is unable to receive a RREP. The originator keeps track of the number of times the RREQ is generated and is depicted a ‘k'. Maximum value of k is 4 after which the originator gives up retrying. For k > 1 generating an RREQ is somewhat different from that of k=1 and hence the processing at intermediate nodes also varies. Before generating the RREQ retry, i.e. k > 1, the sequence number and RREQ_ID is updated as described in section (3.3.1). Flag ‘F' is set to on, depicting the operation over fail-safe mode. The originator zone head fills the reserved field with its own calculated mobility factor. Originator IDZ, Originator Node Identifier, Originator Sequence Number, Destination ID, Destination Sequence Number and Hop Count are filled the same way as in normal operating condition. Message authentication code is calculated the same way without including the ‘Reserved' field, as it contains mutable value, which is going to change at every hop. The RREQ is then broadcasted by the originator. Each intermediate node, whether, member or zone head processes the RREQ with F flag set to on.

3.4.2 Processing RREQ at Intermediate Nodes

When a node receives a RREQ retry, it first find out whether an RREQ retry with the same Originator ID and RREQ ID within a specified time limit has been received or not. If received, the node compares the received mobility factor in the current RREQ with the one already stored against the same RREQ ID and Originator Node Identifier. Regardless of the hop count, as in normal mode, if the mobility factor is the greater than the one, if present already in the route table the RREQ is discarded silently. This subsection further discusses the actions taken for the RREQs that are accepted by the node. If, however the node has received the only RREQ retry or the RREQ retry is with lesser mobility factor than the one already present in the reverse routing table, it creates or updates a reverse route to the previous hop, respectively. It now process the RREQ and increments the hop count field in the RREQ by one. Adds up the MF value in received RREQ with its own mobility factor and replaces it in the RREQ, such that the MF field in the RREQ now contains the sum of both the received MF and its own MF. The rest of the operation related to life timer, sequence number and TTL values is the same as in normal mode and the RREQ is then broadcasted with its F flag set to on.

3.4.3 Generating Route Replies

When the RREQ reaches the destination, it contains the mobility factor accumulated across the entire path. This factor is copied to the routing table of destination, but only if the RREQ is accepted based on the fulfillment of the criteria. The criteria and procedure for generating route replies in fail-safe mode is the same as in normal mode of operation described in section (3.3.6). However, the routing table for the destination now contains another field containing the value of the accumulated mobility factor across the entire path. The base station generates the RREP the same way as normal mode defined in section (3.3.6), except the fact that the ‘F' flag is set to on and the reserved field is filled with the mobility factor of the destination. RREP is then unicast to the next hop towards the source of the RREQ.

3.4.4 Receiving and Forwarding Route Replies

When an intermediate node receives an RREP with ‘F' flag set to on, it adhere to the same procedure of processing RREPs as described in section (3.3.6). However, with one exception that the mobility factor is accumulated on each hop. So, when the RREP makes up to the originator of RREQ, it contains the value of accumulated mobility factor across the entire path. The Originator node copies the same to its routing table along with other information for the base station. The rest of the procedure is adhered without any change and thus the node ends up with a route towards the base station that has the least mobility factor among all the possible routes. The detailed impact of including mobility factor and depending solely on it for generating RREP in fail-safe mode is discussed further in section 4.2. However, briefly it can be said that the lesser mobility factor guarantees the involvement of more zone heads across the path, which in turn means that the path will be stable for longer duration of time. Route error and route maintenance follow the same procedure as described for the normal mode of operation.

Chapter 4 4 Security and Fault Tolerance Analysis 4.1 Introduction

We analyze the performance of FTSR protocol with respect to the diversity of features it offers. First we look at the fault tolerant aspect, secondly an analysis of fail-safe mode of operation and at last a detailed overview of the security features it offers.

4.2 Fault Tolerance

The zone based approach used over the under lying routing protocol and the error control and repair mechanism adds a multi dimensional fault tolerant aspect to our proposed solution. Mobile networks undergo far more frequent link breaks than normal static networks. Movement of any node, whether it is the Originator of data or a node serving as intermediate node in the route to base station result in tremendous amount of control traffic for finding the new route to the base station. Our aim is to manage mobility in such a way that it effects the routing information present in the network to the smallest extent. Also, network performance can be improved if somehow we manage to integrate the cost of our route to the base station with the mobility and remaining energy. In FTSR, zone head is responsible for aggregating and routing data to base station. All nodes present in a specific zone reports their sensed data to the zone head. The election criteria suggest that the zone head must be the one with least zone changes and maximum remaining energy at time ‘t' seconds. This predicts that the node elected as the zone head will be serving the respective zone for more time than other nodes in the zone. Once elected, the zone head is the one that is responsible for handling all the control information to and from other zones and member nodes don't participate in path finding algorithm, except in fail-safe mode of operation. Movement of member nodes inside the entire network, which ever zone they belong to, does not in any case affect the routes to the base station. The only concern they raise is their securely leaving and joining the zones, whether reporting data or merely sensing it. A change in zone always results in an inquiry by the member node for the new zone head. As the member node is always reporting its zone head, so a change in zone head is sufficient to conclude that now the sensed data will be directed to the new one. Member nodes have no concern how their data reaches the base station and are neither concerned nor involved how others are sending their data. Therefore we can safely conclude that movement of member nodes does not, in any case, affects the routes in the network. Zone head movement, however is likely to affect the under lying routes as they are the mainstay of our entire network. However, this problem is somewhat limited by choosing the least mobile node as the zone head. Secondly FTSR protocol is zone based instead of node based. That is, all control information and data is intended for the zone and not any specific node and zone head is the one responsible for responding and/or replaying that information. So it does not concern our information which node is serving as the zone head, as long as there is one in the zone. Incase of zone head movement that results in a zone change; the zone head send a BYE message informing its member nodes about its departure. This message is an indication that the sender zone head is no longer available to serve as an aggregator, and router in case, for the respective zone. The member nodes upon receiving the message initiate zone head discovery and a new zone head is elected by the procedure defined in section (3.2.2) .The previous zone head, which has now joined a new zone and is now considered as a member node, broadcast an inquiry packet with its new zone identifier. The zone head of the respective zone, upon receipt of this inquiry informs the node about its id and other necessary information which may be required for zone membership. Cryptographic key revocation and exchange for this entire procedure takes place as described in [32]. In any circumstances, else than the one that it is the only node in the zone, the new entering zone can not be the zone head at this time how ever less mobility factor it own. This has strong implications on security as we will see in the next section. This procedure explicitly indicates that as long as the zone contains at least one node, the zone can be a part of routing protocol.

4.3 Security Analysis

In this section we analyze the performance of FTSR protocol in terms of reliability and security and show that FTSR protocol is fully reliable, with lowest possible overhead.

4.3.1 Spoofed Modified or Retransmitted Routing Information

The most basic form of attack is expected by spoofing, altering, or replaying routing information, so that the malicious nodes is able to create routing loops, draw or repel network traffic, generate false error messages etc. However, monotonically increasing sequence number system and its inclusion in the calculating MAC in FTSR does not allow the adversary to hold the control packet, change the sequence number and make false use of it after a while.

4.3.2 HELLO Flood Attack

Hello flood attack is mounted by an adversary with powerful transmission capabilities. It broadcasts false HELLO packets in the network and hence convinces the nodes that the adversary is its neighbor. Hello flood attacks can be defended by verifying the bi-directionality of the link before taking any action on the received message [4]. FTSR uses a random value noncei in HELLO messages and confirm the bi-directionality of the link by only accepting those replies that include the random number previously sent, otherwise the message is discarded and no action taken.

4.3.3 Sink Hole Attack

Malicious nodes lure traffic by advertising that it has a high quality route towards the base station. Combined with selective forwarding attack it can be successful and undetectable [4]. However the FTSR protocol offers a complete defense against sinkhole attack, by the fact that a RREP is never generated by the intermediate node. The source node will verify the RREP by calculating the MAC on immutable fields with the key that it shares with the base station and in case of any discrepancy, immediately discards the packet.

4.3.4 Sybil Attack

In a Sybil attack, a single node presents multiple identities to other nodes in the network. The Sybil attack can significantly reduce the effectiveness of multi-path routing, or routes believed to be using disjoint nodes could in actuality be using a single adversary presenting multiple identities [4]. FTSR makes use of the fact that each node shares a unique key with the base station and a group key shared among its neighbors. The square zone based structure restricts any cluster head to accept pairing requests after a maximum neighborhood limit is achieved that is eight. Thus the Sybil attack is infeasible and difficult to mount against our FTSR protocol.

Chapter 5 5 Implementation and Results 5.1 Introduction

This chapter provides a brief description of the working of the simulator tool (NS-2) used to simulate the FTSR protocol. The protocol is tested for various network scenarios and results are verified and compared to normal AODV in the end. We have graphically shown that FTSR is much more efficient than normal AODV operation despite of overhead caused due to zoning and security features.

5.2 Simulator (Network Simulator-2)

Simulator is an important tool in the development of network algorithms. It provides an excellent environment to experiment and verify routing protocol correctness. However, simulation does not guarantee that the protocol works up in practice to that extent projected in simulation. However the main objective of any simulation is to study and analyze new ideas in detail before implementation. The NS-2 network simulator is a powerful tool. It is a discrete event network simulator. It is popular in academia for its extendibility as it is an open source model. Another advantage for using this simulator is the online availability of its manual and documentation along side a plenty of support forums. NS supports an array of popular network protocols, offering its simulation results for wired and wireless network models. NS-2 is the second major iteration of a discrete-event simulation platform programmed in C++ and Object Tcl (OTcl). NS-2 was first released in 1996, and derives from the earlier work on the REAL and NS-1 simulator. The simulator structure uses two languages: OTcl scripting at the front end and C++ on the back end. OTcl scripting is used to make a simulation scenario, which may include network components like nodes, router and link bandwidth. C++ is used in the back end, for instance, for conducting AODV routing simulation, the relevant AODV C++ files (i.e. aodv.cc, aodv.h, etc) has to be enabled in OTcl code. The OTcl code links to C++ files, so when the OTcl code runs, it calls the relevant C++ code to execute a particular task.

5.2.1 NS-2 Compatibility

The software has been designed to work under Linux environment but it can be made to run on Windows XP by using Linux emulator tool specifically Cygwin. There are no strict hardware requirements, using a high end platform will result in faster processing. We have used ns-2.33 with Cygwin on top of windows XP, for the ease of usability.

5.2.2 Trace Files

Results of ns-2 simulation are shown in a tabular form called trace file. One line in trace file is produced for each packet that travel from the initiating node to the terminating node and the trace file record every parameter of the transmitted data packet, including the size, start time, type, time to live, starting node, and end node. It is also noted that the packet is unicast or multicast. NS-2 generates huge trace files which could be as big as 100 MB and showing results of simulation of just few minute. This gives the major disadvantage of using NS-2 as it does not provide any tools for getting results. It simply simulates a network, and provides a trace file of all the events that occur in sequential order. Therefore to get required output, separate tools are required to parse through trace file, commonly Pearl and AWK commands are used.

5.2.3 The Network Animator

NAM is a Tcl/TK based animation tool for viewing network simulation trace and real world packet traces. It is mainly intended as a companion animator to the NS simulator. It supports topology layout, packet level animation and various data inspection tools. Since ns-2 provides limited ability to view the animation after the simulation, a separate program Network Animator (NAM) makes it possible. NAM also can record the animation in the form of graphics as the simulation progress. These graphics can then be converted to GIF or AVI format for later viewing.

5.3 Simulated Network Scenario

The FTSR protocol is tested for different scenarios with different network settings. As the sensor network is typically composed of sensor nodes scattered in a region and a base station one end of the field the base station is supposed to be static and the nodes possess both fixed and random mobility pattern. The region used in our simulation is 100 x 100 and 200 x 200 with varying node density from 100 to 300 nodes. Out of these nodes data sending nodes are 1, 10, 20, and 50 for all network scenarios. Each node possesses 2 joules of initial energy and the radio transmission range of each node is 20 meters. The protocol is both tested for static and mobile network. The proposed algorithm is tested for zone size of 10m x 10m and 20m x 20m against the normal AODV routing protocol using various mobility patterns. The mobility in each scenario is considered to be no more than 40 percent of the network population with nodes moving at the speed of 10 km/h sending data at the rate of 1.280 kbps. We have simulated a real time scenario in which the target is observed in an area and all nodes in the radius of 5m of this target follow the target across the entire field. The object's location and movement information is needed to be delivered to the base station continuously and reliably. The scope of this simulation is limited to zoning, reliable path creation, maintenance and assurance of path availability in worst case scenario for FTSR protocol. It has not included the information that node has to send inside a data packet to the base station. The comparison between AODV and FTSR in terms of number of RREQs generated across the static network of 100, 200 and 300 nodes has been shown in 5-1 to 5-3. The number of data sending nodes has taken to be 1, 10, 25 and 50 in each network with an exception of skipping data nodes in 100 nodes network. The graphs has clearly elaborated that FTSR has generated less number of route request across the entire network. Also it is obvious from the graphs that FTSR is scalable in terms of node density and has performed well in dense environments. The simulated results for a network of mobile nodes have been shown in the 5-7 to 5-9. The graphs have been drawn for total number of route requests generated in case of 100, 200 and 300 nodes with 40% nodes being mobile. The graphs show a comparison of AODV, FTSR with normal zone size of 10m and FTSR in case of increased zone size equal to the normal radio range of a node that is 20m so that the zone head are unable to communicate directly to the neighboring zone head and therefore have to activate the fail-safe mode of FTSR. The comparison of energy consumption for AODV, FTSR and FTSR with fail-safe mode has been shown in 5-9 to 5-11. The graph elaborates that FTSR is efficient in terms of energy consumption even in the case of severe network segment fault making the network fall back to fail-safe mode of operation. The above shown s from 5-13 to 5-15 shows the comparison of throughput for mobile networks of 100, 200, and 300 nodes in case of AODV and FTSR protocol.

Chapter 6 6 Conclusion 6.1 Overview

The infrastructure free and tiny node size of sensors makes them more versatile but their constraints and limitations demand for more ingenious developments. Mobility introduces more serious constraints on these networks as movement within network directly affects the topology and protocols like aggregation, key exchange, routing etc. AODV routing protocol, primarily designed for MANETs is considered suitable for implementation in sensor networks but with little modification [3] . In this thesis we have proposed the modification in AODV routing protocol as one of the three major objectives of this research. Securing the routing information in network due to their deployment in hostile areas and recovering from network failures are the two other concerns focused in this research. This thesis introduces the concept of zones in the sensor network. The zoning algorithm improves the efficiency of the underlying routing protocol as is evident from the analysis. Also it helps to cater mobility as member nodes leaving or joining the zone never affects the routing table. The error reporting mechanism is defined as to stop the error messages from spreading across the entire network and making global changes. The control messages are attached with hashed message authentication code that proves vital in the security specifically availability of the routing information in the under lying network. This research work is an endeavor to make the AODV protocol more adaptable and effiecient in sensor network environment where nodes behaviour is unpredictable due to mobility. The proposed solution has been analyzed for its practicability. The effectiveness of the solution has also been verified through simulation carried out on NS-2. The proposed solution does not require any additional hardware and can be equally implemented in both the source and intermediate nodes. The solution is most effective in dense environments where node population is congested. We have seen in the simulated results that performance of FTSR is not a factor of node density; instead it is dependant on zone size and number of zones within the network.

6.2 Achievements

The research objectives set forth during the initial phases have been accomplished. The desired modifications and enhancement in the protocol to fit the needs of mobile sensor networks has been made and desired outcome has been received. A detailed analysis of proposed protocol has been carried out that can serve as the starting point for finding more solutions to the problem.

6.3 Limitations

Verification through simulation is an important step during research and development, which has been achieved. But there is no substitute to live testing that can only be carried out with actual sensor nodes. The solution proposes enhancement of firmware implemented protocol; as a major part of research, therefore actual implementation cannot be done without vendor support.

6.4 Future Work

This thesis has presented enhancement for AODV only. However the strategy of partitioning our network of mobile nodes into zones is independent of underlying protocol. Fail-safe mode can also be made efficient in terms of energy consumption.

Bibliography

[1] “Wireless sensor networks” https://en.wikipedia.org/wiki/Sensor_network. [2] J.K. Hart, K. Martinez, “Environmental Sensor Networks: A revolution in the earth system science”, Earth-Science Reviews, 78. pp. 177-191.2006. [3] P. Levis, A, Tavakoli, “Overview of Existing Routing Protocols for Low Power and Lossy Networks”. Draft-ietf-roll-protocols-survey-02.txt (2008). [4] C. Karlof, D.Wagner, “Secure routing in wireless sensor networks: attacks and countermeasures,” Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications, pp. 113-127, May 2003. [5] F. Ye, A. Chen, S. Lu, L. Zhang, “A scalable solution to minimum cost forwarding in large sensor networks,” in Tenth International Conference on Computer Communications and Networks, 2001, pp. 304-309. [6] F. Ye, S. Lu, L. Zhang, “GRAdient broadcast: a robust, long-live large sensor network,” Tech. Rep., Computer Science Department, University of California at Los Angeles, 2001. [7] W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan, “Energy-efficient communication protocol for wireless micro-sensor networks,” in: 33rd Annual Hawaii International Conference on System Sciences, 2000, pp. 3005-3014. [8] D. Braginsky, D. Estrin, “Rumor routing algorithm for sensor networks,” in First ACM International Workshop on Wireless Sensor Networks and Applications, 2002. [9] L. Li, J. Halpern, Z. Haas, “Gossip-based ad hoc routing,” in: IEEE Infocom 2002, 2002 [10] C. Intanagonwiwat, R. Govindan, D. Estrin, “Directed diffusion: a scalable and robust communication paradigm for sensor networks,” in Proceedings of the sixth Annual International Conference on Mobile Computing and Networks (Mobi-COM ‘00), 2000. [11] Y. Xu, J. Heidemann, D. Estrin, Geography-informed energy conservation for ad hoc routing, in: Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking, 2001. [12] B. Chen, K. Jamieson, H. Balakrishnan, R. Morris, “Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks,” ACM Wireless Networks Journal 8 (5) (2002) 481-494. [13] L. Zhou, Z. Haas, Securing ad hoc networks, IEEE Network Magazine 13 (6) (1999) 24-30. [14] J. Hubaux, L. Buttyan, S. Capkun, The quest for security in mobile ad hoc networks, in: Proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC 2001), 2001. [15] J. Kong, P. Zerfos, H. Luo, S. Lu, L. Zhang, Providing robust and ubiquitous security support for mobile ad-hoc networks, in: ICNP, 2001, pp. 251-260. [16] Y.-C. Hu, D.B. Johnson, A. Perrig, "SEAD: secure efficient distance vector routing for mobile wireless ad hoc networks," in: Proceedings of the 4th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 2002), 2002, pp. 3-13. [17] Y.-C. Hu, A. Perrig, D.B. Johnson, Ariadne: a secure on-demand routing protocol for ad hoc networks, in: MOBICOM, 2002. [18] S. Basagni, K. Herrin, E. Rosti, D. Bruschi, Secure pebblenets, in: ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2001), 2001, pp. 156-163. [19] P. Papadimitratos, Z. Haas, Secure routing for mobile ad hoc networks, in: SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), 2002. [20] S. Marti, T.J. Giuli, K. Lai, M. Baker, Mitigating routing misbehavior in mobile ad hoc networks, in: Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking, 2000, pp. 255-265. [21] S. Buchegger, J.-Y.L. Boudec, Nodes bearing grudges towards routing security, fairness, and robustness in mobile ad hoc networks, in: Proceedings of the Tenth Euromicro Workshop on Parallel, Distributed and Network based Processing, IEEE Computer Society, Canary Islands, Spain, 2002, pp. 403-410. [22] A. Perrig, R. Szewczyk, V. Wen, D. Culler, J. Tygar, SPINS: security protocols for sensor networks, in: Proceedings of Mobile Networking and Computing 2001, 2001. [23] A. Demers, S. Shenker, V. Bhargavan, L. Zhang,Macaw: a media access protocol for wireless lans, in: ACM SigComm ‘94, 1994. [24] R.L. Pickholtz, D.L. Schilling, L.B. Milstein, Theory of spread spectrum communications--a tutorial, IEEE Transactions on Communications 20 (5) (1982) 855-884. [25] N. Abramson, The ALOHA system--another alternative for computer communications, in: Proceedings of the Fall 1970 AFIPS Computer Conference, 1970, pp. 281-285. [26] M. Blum, S. Micali, A simple unpredictable pseudo-random number generator, SIAM Journal of Computing 15 (2) (1986) 364-383. [27] J.R. Douceur, “The Sybil attack,” in: 1st International Workshop on Peer-to-Peer Systems (IPTPS ‘02), 2002. [28] M. Castro, B. Liskov, Practical byzantine fault tolerance, in: OSDI: Symposium on Operating Systems Design and Implementation, USENIX Association, Co-sponsored by IEEE TCOS and ACM SIGOPS, 1999. [29] A. Banerjea, A taxonomy of dispersity routing schemes for fault tolerant real-time channels, in: Proceedings of EC-MAST, vol. 26, 1996, pp. 129-148. [30] K. Ishida, Y. Kakuda, T. Kikuno, A routing protocol for finding two node-disjoint paths in computer networks, in: International Conference on Network Protocols, 1992, pp. 340-347. [31] Y.-C. Hu, A. Perrig, D.B. Johnson, Packet leashes: a defense against wormhole attacks in wireless networks, in: IEEE Infocom, 2003. [32] Sultana, N., Choi, K.M., Huh, E.N.: Application Driven Cluster Based Group Key Management with Identifier in Mobile Wireless Sensor Network. In: Future generation communication and networking (fgcn 2007), vol.1, no., pp.362-367, 6-8 Dec. 2007. [33] Perkins, C., Belding-Royer, E., Das, S.R.: Ad hoc On-Demand Distance Vector (AODV) routing. rfc3561.txt (2003). [34] Niculescu, D., Nathi, B.: Ad hoc Positioning System (APS). IEEE INFOCOM 2003. San Francisco, CA. 2003. [35] Krawczyk, H., Bellare, M., Canetti, R.: HMAC: Keyed-Hashing for Message Authentication. rfc2104.txt (1997)

Appendix A

AODV Configuration Parameters

Parameter Name Value ACTIVE_ROUTE_TIMEOUT 3,000 Milliseconds ALLOWED_HELLO_LOSS 2 BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME DELETE_PERIOD see note (1) below HELLO_INTERVAL 1,000 Milliseconds LOCAL_ADD_TTL 2 MAX_REPAIR_TTL 0.3 * NET_DIAMETER MIN_REPAIR_TTL see note (2) below MY_ROUTE_TIMEOUT 2 * ACTIVE_ROUTE_TIMEOUT NET_DIAMETER 35 NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER NEXT_HOP_WAIT NODE_TRAVERSAL_TIME + 10 NODE_TRAVERSAL_TIME 40 milliseconds PATH_DISCOVERY_TIME 2 * NET_TRAVERSAL_TIME RERR_RATELIMIT 10 RING_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * (TTL_VALUE + TIMEOUT_BUFFER) RREQ_RETRIES 2 RREQ_RATELIMIT 10 TIMEOUT_BUFFER 2 TTL_START 1 TTL_INCREMENT 2 TTL_THRESHOLD 7 TTL_VALUE see note (3) below

Note:-

1- DELETE_PERIOD is intended to provide an upper bound on the time for which an upstream node A can have a neighbor B as an active next hop for destination D, while B has invalidated the route to D. Beyond this time B can delete the (already invalidated) route to D. 2- The MIN_REPAIR_TTL should be the last known hop count to the destination. 3- TTL_VALUE is the value of the TTL field in the IP header while the expanding ring search is being performed.

Cite this page