ABSTRACT

This paper describes a novel energy-aware multi-hop cluster-based fault-tolerant load balancing hierarchical routing protocol for a self-organizing wireless sensor network (WSN), which takes into account the broadcast nature of radio. The main idea is using hierarchical fuzzy soft clusters enabling non-exclusive overlapping clusters, thus allowing partial multiple membership of a node to more than one cluster, whereby for each cluster the clusterhead (CH) takes in charge intra-cluster issues of aggregating the information from nodes members, and then collaborate and coordinate with its related overlapping area heads (OAHs), which are elected heuristically to ensure inter-clusters communication. This communication is implemented using an extended version of time-division multiple access (TDMA) allowing the allocation of several slots for a given node, and alternating the role of the clusterhead and its associated overlapping area heads. Each cluster head relays information to overlapping area heads which in turn each relays it to other associated cluster heads in related clusters, thus the information propagates gradually until it reaches the sink in a multi-hop fashion.

1. Introduction

The convergence and confluence of the microelectromechanical systems (MEMS), wireless communication and computing has led to the realization of less expensive miniaturized resource-limited tiny chips with sensing (for monitoring temperature, pressure, acoustics etc.), communicating and computing capabilities. Thus, opening the door and paving the way for the development and deployment of wireless sensor networks (WSNs). As a result, WSNs have emerged as an important application of the ad-hoc networks paradigm, and were extensively applied for monitoring physical environment, infrastructure security, structural health monitoring and industrial sensing. The concept of WSNs is based on a simple equation: Sensing + CPU + Radio = Thousands of potential applications. Each element of the network is commonly called a “mote” or smart sensor. Motes are combined into large networks that allow dense and detailed sensing. These networks move beyond the idea of a sensor as a single instrument measuring one thing, to a comprehensive system consisting of many small nodes working cooperatively. In recent years, we have been witnessing the proliferation of WSNs [1-9]. It is easy to predict that in the near future, WSNs will play important roles in our society. Consequently, demands for WSNs with various protocols, architectures and abilities to flexibly run various tasks can be expected to increase significantly. We believe that WSNs is the key enabling technology that will provide the adequate infrastructure to what is called Ambient Intelligence (AmI) [10,11].

In WSNs, sensors can be deployed either randomly or deterministically. A random sensor placement may be suitable for battlefields or hazardous areas while a deterministic sensor placement is feasible in friendly and accessible environments. In general, fewer sensors are required to perform the same task with a deterministic placement. WSNs are typically deployed in hazardous or inaccessible environments and hence the sensor nodes’ energy supply is usually limited and cannot be renewed. Due to these limitations, the nodes’ energy consumption must be minimized, while still maintaining the network’s connectivity to maximize its useful lifetime. The nodes communicate wirelessly and often self-organize after being deployed in an ad-hoc fashion. These self-organizing sensor networks have limitations of system resources like battery power, communication range, memory space and processing capability. Low processing power and wireless connectivity make designing such networks a real challenge. Self-organization can be defined as the process by which systems tend to reach a particular objective with minimal human interference. The mechanisms dictating its behavior are internal to the system. Network self-organization: Given the large number of nodes and their potential placement in hostile locations, it is essential that the network be able to selforganize; manual configuration is not feasible. Moreover, nodes may fail (either from lack of energy or from physical destruction), and new nodes may join the network. Therefore, the network must be able to periodically reconfigure itself so that it can continue to function. Individual nodes may become disconnected from the rest of the network, but a high degree of connectivity must be maintained. Scalability requires that any configuration process be completely distributed and use only local information, which presents the classic problem confronting all self-organized systems: How to obtain global optimality from local adaptation?

WSNs can be divided in to two classes as event driven and continuous dissemination networks according to the periodicity of communication. In event-driven networks, data is sent whenever an event occurs. In continuous dissemination networks, every node periodically sends data to the sink. Routing protocols are usually implemented to support one class of network in order to save energy. Almost all the research involved with routing is related to sending the sensed data to a control center or to a fixed destination called a sink.

WSNs can further be classified into two types with respect to nodes’ transmission radii-homogeneous and heterogeneous networks. Homogeneous networks are the networks where all the sensor nodes have same transmission radius, while hetero-generous networks are those where at least two nodes have different transmission radii. Most of the research on wireless sensor networks is focused on homogeneous networks which can be modeled as undirected graph. These homogeneous networks are usually cost-effective, simple to analyze, and easy to deploy. The base stations are one or more components of the WSN with much more computational, energy and communication resources. They act as a gateway between sensor nodes and the end user as they typically forward data from the WSN on to a server. Other special components in routing based networks are routers, designed to compute, calculate and distribute the routing tables.

The main task of a sensor node in a sensor network is to monitor events, i.e., collect data, perform quick local data aggregation, and then transmit the data. Power consumption can hence be divided into three domains: sensing, aggregation, and communication, of which communication has the lion’s share. This paper proposes a new framework to conserve energy of WSN, thereby the lifetime of the network is increased.

The wireless sensor network consists of different sensor nodes that have very limited battery power, so the main objective is to maximize the lifetime of sensor network. In WSN the energy is basically consumed by data transmission, as approximately 70% of the energy is consumed by data transmission so data transmission should be optimized in wireless sensor network, for maximizing the lifetime of network. Data transmission can be optimized with the help of effective protocol and effective ways of data fusion (aggregation). There is a need to devise protocols, which can reduce the transmission load and enhance the life time of the entire network. Low energy use: Since in many applications the sensor nodes will be placed in a remote area, service of a node may not be possible. In this case, the lifetime of a node may be determined by the battery life, thereby requiring the minimization of energy expenditure.

Many of the design challenges for large scale wireless sensor networks (WSN) are well known, among them: scalability, geographic range, infrastructure, cost, longevity, heterogeneity, and mobility.

Sensor nodes can be thought of as small computers, extremely basic in terms of their interfaces and their components. They usually consist of a processing unit with limited computational power and limited memory, sensors or MEMS (including specific conditioning circuitry), a communication device (usually short range radio transceivers or alternatively optical), and a power source usually in the form of a battery. Other possible inclusions are energy harvesting modules, secondary ASICs, and possibly secondary communication devices (e.g. RS-232 or USB).

A typical wireless sensor network in which the sensor nodes are scattered in a sensor field. Each node has the capability of collecting data and routing it back to the base station. The base station is like a gateway to the wireless sensor network. It connects the complete wireless network with the task manager node via the Internet or satellite. The sensor nodes are also capable of sending information to other sensor nodes in the sensor field.

Due to the limited processing power, and finite power available to each sensor node, regular ad-hoc routing techniques cannot be directly applied to sensor networks domain. Thus, energy-efficient routing algorithms suitable to the inherent characteristics of these types of networks are needed.

LEACH [12] is a cluster-based energy-aware routing protocol which is one-hop protocol where a cluster head is assumed to relay the information directly to the sink in a single hop; however due to range limitations and the higher power node-to-sink direct broadcast; multiple hops through network may be required. As it is the case in common practical applications.

To this goal, fuzzy and soft clustering could provide a novel multi-hops hierarchical cluster based routing energy-aware protocol that prolongs the sensor network lifetime while ensuring robustness and fault-tolerance. The remainder of the paper is organized as follows: Section 2 surveys related literature on WSN protocols; Section 3 describes design issues of the proposed novel protocol and analyses its quality aspects; Section 4 attempts to draw some conclusions and to suggest some research directions.

2. Background and Related Work

2.1. Overview of WSNs Protocols Design

First, a wireless sensor network (WSN) consists of a number of independent nodes that communicate with each other wirelessly over limited frequency and bandwidth. The nodes are equipped with limited capabilities of sensing, computation and communication. Wireless sensor nodes are densely deployed and coordinate with each other to produce high-quality information about the sensing environment. The exact location of a particular sensor is unknown. It means that sensor network protocols and algorithms must provide self-organizing capabilities.

Today, Wireless Sensor Network (WSN) is considered as one of the major research areas in computer network field. One of the many WSN functions is to provide sensing services in an unattended harsh environment. Sensed data need to be delivered to the data collection centre and to cope with the reliable network problem.

The topology of the WSNs can vary from a simple star network to an advanced multi-hop wireless mesh network. The propagation technique between the hops of the network can be routing or flooding.

Routing protocols in sensor networks from network structure point of view can be divided into two main categories: flat and hierarchical. In flat routing protocols the concept of leader node (or a cluster head) does not exists and all nodes are at the same level of importance. In hierarchical routing protocols the act of clustering and classification of nodes are done and some nodes are considered as leaders (or a cluster heads). From this group of protocols we can name LEACH. Indeed there are other categories of protocols like data centric, location based, energy aware. In a way that each routing protocol can belong to one or several of mentioned groups.

Networks can be broadly classified into two types depending on the way they transmit data, namely, point-topoint networks or broadcast networks. In the case of point to-point networks, a separate channel exists between two separate nodes. In contrast, in the case of a broadcast network, there is only one channel available which is shared by all nodes on the network. Media access control (MAC) protocols control access to this shared channel.

2.2. Flooding, Gossiping and Clustering

In flooding, each sensor node receiving a data or a control packet repeats it by broadcasting, flooding has several shortcomings such as implosion (duplicated messages are sent to the same node), overlap (neighbor nodes receive duplicated messages) and resource blindness (does not take into account the energy resources, it is not energy aware). In gossiping, nodes do not broadcast but send the incoming messages to a randomly selected neighbors. A sensor node randomly select s one of its neighbors to send the data. Once the neighbor node receive the data, it randomly selects another sensor node. Gossiping avoids the implosion problem but still is not energy aware, and it takes a long time to propagate the message to reach the sink.

One way to support efficient communication between sensors is to organize the network into several groups, called clusters, with each cluster electing one node as the cluster head (CH). Conventionally, nodes are often grouped into disjoint and mostly non-overlapping clusters. Many literatures are concentrated on finding solution at various levels of the communication protocol, including being extremely energy efficient. Energy efficiency is often gained by accepting a reduction in network performance. Low-energy adaptive clustering hierarchy (LEACH) is a new communication protocol that tries to distribute the energy load evenly among the network nodes by randomly rotating the cluster head among the sensors.

2.3. Overview and Description of LEACH

Efficient routing in a wireless sensor network requires that the routing protocol must minimize energy dissipation (maximize energy conservation) and maximize network life time.

LEACH is a cluster-based energy-aware routing protocol which is one-hop protocol where a cluster head (which contain a longer range radio) is assumed to relay the information directly to the sink in a single hop; however due to range limitations and the higher power nodeto-sink direct broadcast; multiple hops through network may be required in some practical situations. The cluster head may be selected in a randomized manner. Such a randomized selection of the cluster head, combined with rotating the cluster head position, can effectively avoid the early drain of the energy of a particular node.

LEACH is a cluster-based protocol that uses time-division multiple access (TDMA) for intra-cluster communication between the sensors and the cluster-head. When clusters are formed, the cluster-head node creates a schedule that gives each sensor in the cluster a time slot in which to transmit its data, allowing the sensors to sleep for all other time slots. LEACH includes mechanisms to allow the high energy position of cluster-head to be rotated among the nodes to evenly distribute the energy load. Clusters are adapted based on the cluster-head nodes for each round, and new TDMA schedules are created based on the new clusters. LEACH has been shown to achieve good energy-efficiency and hence long network lifetime when sensors always have data to send and when sensors are static. However, if sensors enter or leave the cluster area or change their data rate due to detection of phenomena while the cluster is fixed, LEACH cannot adapt.

In common applications, a typical network configuration consists of sensors working unattended and transmitting their observation values to some processing or control center, the so-called sink node, which serves as a user interface. Due to the limited transmission range, sensors that are far away from the sink deliver their data through multihop communications, i.e., using intermediate nodes as relays.

This paper deals about the framework for energy conservation of a Wireless sensor network. The framework is developed such a way that the nodes are allowed to be clustered in overlapping clusters, electing the cluster head, electing the overlapping head, performing intracluster transmission, inter-cluster transmission and from the cluster head, through the overlapping head, to the neighbor cluster head the information is transmitted or rather propagated progressively until it reaches the base station (or sink) in a multi-hop way.

3. A Novel Multi-Hop, Fault-Tolerant and Load Balancing Hierarchical Protocol

3.1. Motivations and Protocol Design Challenges

Different routing protocols have been developed to deal with this problem. It is still a great challenge of the hierarchical routing protocol to operate efficiently in the presence of node failure. Therefore, a novel hierarchical routing protocol that addresses network survivability and redundancy issues is needed. Fault-resilient protocol require the possibility to reach the sink using multiple paths. The goal is to devise a high capacity WSN that degrades softly under attack, while always providing a critical level of service.

We have the following goals for designing Multi-hop, Fault-tolerant and Load Balancing Hierarchical Protocol. 1) Localized algorithms. It should only use localized algorithms and not depend on global state information for data delivery. 2) Energy efficiency. The data delivery scheme should be energy efficient as sensor nodes are resource constrained. 3) Scalability. The scheme should be scalable to large and dense sensor networks that consist of thousands of nodes. 4) Fault-tolerance to node failure or death.

3.2. Benefits of Multi-Hop Hierarchical Clustering

Use The clustering approach has proved to be one of the most effective mechanisms to improve energy efficiency in wireless sensor networks (see, e.g., [2-7]). In a cluster-based sensor network, sensor nodes are organized into groups, each with a cluster head (CH). Traditionally, sensor nodes in a cluster send their data to the corresponding cluster head, and the cluster head forwards the data to the neighboring cluster along the route or to the sink directly. Building on the cluster based model, we propose an overlapping-cluster network structure, where overlapping areas heads (OAH) sensor nodes can carry out inter-cluster cooperative data transmissions. This structure is motivated by the two key features of wireless sensor networks: node cooperation and data correlation, which differentiate wireless sensor networks from conventional wireless networks. The way of operating of the algorithm is similar but different from the conventional hierarchical cluster-based schemes.

There are two types of wireless cluster-based protocol WSN: Single hop in which nodes belonging to a given cluster transmit to the cluster head and in its turn can transmit or communicate directly with the Sink. All the nodes use the same channel to communicate, and the message broadcast by one of the stations on the common channel is simultaneously heard by all other stations. In the multi-hop wireless networks intermediate nodes are used to route message from the source to the Sink. There is a strong need for development of routing techniques which work considerably across wide range of applications. In this paper only multi-hop wireless networks are considered.

During the steady phase data packet sent by a sensor (sender) reaches all its cluster member nodes within the transmission range of the sender; sensors far from the data sink have to use intermediate nodes to relay data transmission to reach the sink.

3.3. Protocol Design Description

The proposed solution is appropriate for random deployment and suitable for different sizes of target areas. This protocol forms clusters in which each cluster member is at one hop distance from the cluster head. This protocol ensures the participation of all the cluster heads in hierarchical topology formation. The proposed protocol is also capable of handling dynamic nature of the wireless sensor networks. It is a multi-path routing scheme which is more robust than a single-path scheme. Three kinds of sensor nodes are involved, cluster member (CM), clusterhead (CH) and overlapping area head (OAH).

In particular, the cluster head (CH) carries out data aggregation and coordinates the overlapping areas heads (OAHs) sensor nodes but not necessarily transmits the data itself to the Sink, whereas in a traditional cluster the cluster head performs the bulk of the communication tasks.

3.3.1. Design Tradeoffs

We are interested at devising a multi-hop, multi-path fault-resilient and load balancing hierarchical protocol. A CH need to relay his data to the sink through a multi-hop chain.

A CH has the possibility to relay his data through OAHs and other CHs to the sink through multi-path. The goal is to develop a cross layer architecture that provides energy preservation, resilience and scalability for WSNs. The resulting architecture will be able to adaptively provide the appropriate trade-offs between performance, and fault-resilience (or fault-tolerance). Resilience could be achieved through a multi-path topology of the WSN (Self-healing). Energy-preservation through cluster-based hierarchical routing protocol. Scalability through self-organizing distributed routing protocol.

3.3.2. Hierarchical Fuzzy Soft Clustering

We have devised an energy-aware multi-hop clusterbased fault-tolerant load balancing hierarchical routing protocol for a self-organizing wireless sensor network (WSN), which takes into account the broadcast nature of radio. As illustrated in Figure 1, the main idea is using fuzzy soft clustering enabling non exclusive overlapping clusters, thus allowing partial multiple membership of a node to more than one cluster and nested clusters, whereby for each cluster the cluster head (CH) aggregate the information from nodes members, and then collaborate and coordinate with its overlapping area heads (OAHs) to ensure inter-cluster communication. This communication is implemented using an extended version of TDMA allowing the allocation of several slots for a given node, and alternating the role of the cluster head and its associated overlapping area heads. This protocol forms clusters in which each cluster member is at one hop distance from the cluster head. Each cluster head relay information to

all of its overlapping areas heads which in turns each relay it to its associated cluster head, the information propagate gradually until it reaches the sink. The algorithm distributes the energy load evenly among the network nodes by randomly rotating the cluster head among the sensors at the cluster level as well the overlapping area heads at the overlapping zones levels. The proposed protocol is also capable of handling dynamic nature of the wireless sensor networks such as links change, nodes enter (new nodes) and leave (dead nodes).

The algorithm is composed of a set up phase followed by steady state phase: The set up phase is made up of three main steps; the first stage is to partition the network into k overlapping clusters and determine a CH for each cluster, the second stage is to find out OAHs in-between clusters and determine an OAH for each pair of two neighboring clusters, the third stage is to partition the CHs nodes around related OAHs, whereby an OAH play the role of a CH in respect to the CHs with which it is related.

1) The set up phase:

The set up phase is made up of three successive stepsprocedure, A., B., and C. as follows:

Step A. Identification of cluster heads (CHs) is similar to LEACH, a sensor node chooses a random number in the range [0, 1]. If this random number is less than the threshold T(n), the sensor node is a clusterhead (CH). T(n) is computed as

(1)

where P is the desired percentage to become a clusterhead, r is the current round, and G is the set of nodes that have not being elected as a clusterhead in the last 1/P rounds.

Basically, first a cluster head ensures intra-cluster aggregation and communication within its cluster among the cluster members to which it belongs. Then coordinate the transmission to overlapping area heads (which are shared with other neighboring clusters).

Step B. Identification of clusters is similar to LEACH except the possibility for a node to belong to several clusters simultaneously, and reflects situations when the received signal strength (RSS) by the node (from distinct cluster heads) during set up is either equal or close to some extent or greater than a threshold value. The disjointness restriction between clusters is unnecessary herein.

After the clusterheads are elected, the clusterheads advertise to all sensor nodes in the network that they are the new clusterheads. Once the sensor nodes receive the advertisement, they determine the clusters they want to belong based on the received signal strength of the advertisement. Each sensor node has the possibility to join more than one cluster, and inform the appropriate clusterheads it will be member of the cluster.

Afterward, the clusterheads assign the time on which the sensor nodes can send data to the clusterheads based on TDMA approach.

Step C. Identification of overlapping area heads (OAHs)

Every node, which is belonging to more than a cluster is a potential candidate overlapping area head (OAH), thus it must inform the corresponding cluster head of every cluster to which it belongs to. Preference should be given to those candidates which are associated with the maximum number of clusters. Once a candidate is elected it becomes an overlapping area head (OAH), typically a CH may have several OCHs associated with it. Ideally one cluster should have a common overlapping area head with each of the neighboring clusters. However, this is not required as it seems that it is not always the case in practice due to the random deployment of sensors over the field area. Basically, an overlapping area head ensures inter-cluster communication between the associated pairs of clusters to which it belongs.

2) The steady phase:

The steady phase is executed in several iterations. Role of the clusterhead (CH): firstly using TDMA the CH (of each cluster) aggregate data from all of its cluster members, then broadcast it to every overlapping area head (OAH) belonging to its cluster in one-hop. As illustrated in Figure 2 every OAH in turn using an extended version of time-division multiple access (TDMA) relay data the other associated CHs in other related clusters in one-hop, i.e., the OAH play the role of a CH in the newly formed cluster containing related CHs. Then again the CHs broadcast aggregated data (already obtained from all

of its related OAHs) to OAHs using extended TDMA. The algorithm proceeds iteratively in a similar way, while the data propagates progressively until reaching the sink. More specifically, this communication scheme is implemented using an extended version of time-division multiple access (TDMA) allowing the allocation of several slots for a given node, and alternating the role of the clusterhead and its associated overlapping area heads.

Put it simply, an OAH play the role of a cluster head of the cluster formed by the CHs associated with the clusters to which it belongs. MRL denotes the maximal number of the radio links that an OAH might have to establish with CHs. We used the following heuristic: for each OAH and for each two associated clusters, we elect the OAH with the maximum MRL.

After a certain period of time spent on the steady phase, the network goes into the set up phase again enter another round of electing clusterheads and overlapping area heads.

It is worth mentioning that while CHs are elected randomly, OAHs are selected heuristically. Errors caused by failing hardware or drained batteries are the norm rather than the exception in WSN. Robustness is ensured through the possibility of multiple paths to convey data to the Sink. Scalability in such a protocol scheme is ensured and in fact built-in due to the local decision nature of the algorithm used to implement the protocol.

Note that during this steady phase regular nodes which are neither CHs nor OAHs are not any more involved in the process thereby reducing significantly the number of nodes, which enter in play in propagating data to the sink. By exploiting the synergy among the available data, we can reduce the amount of data traffic, filter noisy measurements, and make predictions and inferences about a monitored entity.

3.3.3. Assumptions, Constraints and Requirements

Without any lose of generality and for the sake of practicality we made the following assumptions:

• Each node has to belong to at least one cluster to ensure the recovering of all nodes in the sensor field. A cluster may or may not be dense or sparse depending on the random deployment in the sensor field.

• A cluster should contain at least two nodes (one will be its CH and the other will be its OAH).

• Each CH belongs to only one cluster (by construction).

• Each cluster has at least one OAH, i.e. it overlaps with a least another neighbor cluster.

• Each OAH head is shared by at most k clusters, where k is a certain fraction of c the number of clusters. It is not necessary that clusters have an equal number of OAH, and depending on the random deployment of sensor in the field will likely have a different number.

• The sink is assumed to be reachable at least through either one CH node or one OAH node, which means that the sink might be thought of as a member of at least one cluster. The sink will be clustered automatically during the set up phase.

The number of sensor nodes involved in this protocol is less than the one involved in a flat multi-hop scheme. It has the advantages and features of multi-level hierarchical cluster-based scheme while it can accommodate built-in multi-path routing by design and construction. More over in a hierarchical scheme only cluster heads (CHs) are involved. Obviously, this protocol acts better than those protocols in terms of optimizing cluster heads as well as overlapping area heads (OAHs) energy consumption, amount of data gathered, and extending network lifetime. This protocol exhibits inherent fault tolerance and provides the possibility to save energy within the network.

4. Concluding Remarks and Future Work

We have described a novel multi-hop hierarchical cluster-based multi-path routing energy-aware protocol that prolongs the sensor network lifetime while ensuring robustness and fault-tolerance. It takes into account the broadcast nature of radio. Moreover, this protocol is scalable to large and dense sensor networks that consist of thousands of nodes.

We plan to conduct simulation and experiments, implement and deploy this protocol (in term of a middleware layer) and compare its performance with other protocols in real world applications. Of particular interest to us is studying design tradeoffs between performance, survivability and scalability of WSNs. Survivability is the degree to which essential functions of the WSN are still available even though some part of the system is down. The goal of this investigation is a high capacity WSN that degrades softly under attack, while always providing a critical level of service.

An important part of our effort will be devoted to build case studies and especially to explore the applications of WSNs for health care monitoring as well as for a certain class of military applications.

Realizing the potential of large, distributed WSNs requires major advances in the theory, fundamental understanding and practice of distributed signal processing, self-organized communications, and conjointly low level as well as high level information fusion [13-16] in highly uncertain environments using sensing nodes that are severely constrained in power, computation and communication capabilities, and more importantly their seamless integration in a unified coherent framework. It is hoped that the paper will stimulate further work in a field whose importance will increasingly be recognized.

REFERENCES