Beydoun Kamal
email: beydoun@lifc.univ-fcomte.fr

Lifc

Violeta Felea
email: felea@lifc.univ-fcomte.fr

Energy-Efficient WSN Infrastructure

Keywords: Wireless Collaboration Systems, WSN, zone partitioning, energy conservation, scalability

Energy conserving communication is one of the main challenges of wireless sensor networks. A number of studies and research are focused on saving energy and on extending the lifetime of these networks. Architectural approaches, like hierarchical structures, tend to organize network nodes in order to save energy. Most of these protocols need background information on the network in order to be efficient. In this paper, we describe a new approach for organizing large sensor networks into zones, based on the number of hops. This network architecture enables a hierarchical network view, with the purpose of offering efficient routing protocols based on zone partitioning. Simulations undertaken demonstrate that our approach is energy-efficient; this is highlighted by the reduction of traffic overhead.

INTRODUCTION

Wireless Sensor Networks (WSNs) are dense wireless networks made up of small, low-cost sensors, which collect and disseminate environmental data. Wireless sensor networks facilitate the monitoring and controlling of physical environments from remote locations with good accuracy. Sensor networks have attracted many research efforts over the past few years due to their challenges like energy efficiency, resource management and scalability. In order to address these issues, most existing research use hierarchical architectures such as cluster-based topologies. Clustering builds up groups of nodes, named clusters, according to some metrics. Each cluster has an elected Cluster Head. Its role is to assure membership management and also routing, by communicating the collected data via nodes to the base station. In spite of the advantages of clustering protocols, most of them require further information on the network (e.g. node energy, connectivity, geographical position). That leads to an overload in the network due to the number of sent packets. Consequently, the energy of the network and its lifetime both decrease. In this paper we propose a new approach of node grouping in zones for large WSNs, where zone construction uses as metric the number of hops. No other information on the network is needed. In cluster based architectures, cluster heads have an important role of managing and routing, and their election generates traffic overhead, and requires a number of pieces of state information available within the network (energy, or localization). The zone topology we propose does not intend to give a management role to specific nodes: the nodes on the zone border will help routing between the zones and all nodes of a zone have the same function inside their zone. Moreover, it does not need prior information on the network.

The remainder of the paper is structured as follows. In Section 2 we analyze the features of WSNs and briefly present a taxonomy of routing protocols before focusing on hierarchical topology control, which states problematic and identify goals. In Section 3, we present our approach of network infrastructure. In Section 4, we describe and discuss the results from our simulations compared to existing work. Finally, we conclude and trends of future work are given.

CONTEXT AND RELATED WORK

Ad hoc and sensor networks

The ad hoc networks are wireless networks able to organize themselves without predefined infrastructure. In their mobile configuration, these networks are known as Mobile Ad hoc NETworks (MANETs) ( [START_REF] Qin | Survey on Mobile Ad Hoc Network Routing Protocols and Cross-Layer Design[END_REF]). Wireless sensor networks are autonomous ad hoc networks designed to monitor tasks, such as battlefield surveillance, equipment supervision, intruder detection, and wildlife observation, among others ( [START_REF] Mainwaring | Wireless Sensor Networks for Habitat Monitoring[END_REF], [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]). Sensor networks are made up of a large number of tiny devices, called sensor nodes, which contain integrated sensor device(s), processors, and radios ( [START_REF] Lewis | Wireless Sensor Networks[END_REF], [START_REF] Schurgers | Optimizing Sensor networks in the Energy-Latency-Density Design Space[END_REF]). In [START_REF] Tilak | A Taxonomy of Wireless Micro-Sensor Network Models[END_REF], the authors use the following terminology:

978-1-4244-2249-4/08/$25.00 ©2008 IEEE 1. Sensor: the transducer responsible of the physical sensing of environmental phenomena and reporting measurements through wireless communication.

2. Observer: the end user concerned with obtaining information disseminated by the sensor network about the phenomenon. The observer may specify queries to the network and receive responses to these queries. Multiple observers may exist in a sensor network.

3. Phenomenon: the entity of interest to the observer that is being sensed and potentially analyzed/filtered through the sensor network. Multiple phenomena may be under observation simultaneously in the same network.

In most data-gathering applications, there is a node, referred to as base station (BS or sink), to which all data from sensor nodes are directed, on the basis of a multi-hop structure (some nodes act thus as sources as well as routers for other sources).

Mobility is not a predominant feature of WSNs, as it is the case for MANETs. In static sensor networks, there is no motion among communicating sensors, the observer and the phenomenon. However, in dynamic sensor networks, the sensors themselves, the observer, or the phenomenon are mobile ( [START_REF] Tilak | A Taxonomy of Wireless Micro-Sensor Network Models[END_REF]).

Recent researches in Wireless Sensor Networks are focused on increasing the lifetime of the system by decreasing energy consumption of each node in the network ( [START_REF] Willig | A short survey of wireless sensor networks[END_REF], [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF], [START_REF] Tubaishat | Sensor Networks: An Overview[END_REF]). Because of the importance of energy consumption optimization, a particular interest is oriented towards routing protocols.

WSN Routing Protocols

Ad hoc routing protocols (AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], DSR [START_REF] Broch | DSR The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks[END_REF], and DSDV [START_REF] Bhagwat | Highly Dynamic Destination-"Sequenced Distance-Vector Routing (DSDV) for Mobile Computers[END_REF]) may be used as network protocols for sensor networks. However, such approaches will generally not be good candidates for sensor networks because of the main following reasons ( [START_REF] Tilak | A Taxonomy of Wireless Micro-Sensor Network Models[END_REF]): (i) sensors have low battery power and low memory availability; (ii) the routing table size scales with the network size.

According to the structure of the network, the routing protocols in WSN are classified as follows ( [START_REF] Kamal | Routing techniques in wireless sensor networks: a survey[END_REF]): 1. Flat-based routing. In flat networks, each node typically plays the same role and sensor nodes collaborate to communicate the sensed data. Due to the large number of such nodes, it is not feasible to address each node. This consideration has led to data centric routing, where the BS (base station) sends queries to certain regions and waits for the data from the sensors located in the selected regions. Early works on data centric routing, e.g. SPIN [START_REF] Willig | A short survey of wireless sensor networks[END_REF] and directed diffusion [START_REF] Estrin | Directed diffusion: A scalable and robust communication paradigm for sensor networks[END_REF], were shown to save energy through data negotiation and redundant data elimination. 2. Location based routing. In this type of routing, sensor nodes are addressed by means of their locations. The distance between neighboring nodes can be estimated on the basis of incoming signal strengths. Relative coordinates of neighboring nodes can be obtained by exchanging such information between neighbours like in GEAR [START_REF] Yu | Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks[END_REF] and SPAN [START_REF] Chen | An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks[END_REF] protocols. Alternatively, it may be possible to obtain location information using existing infrastructure, such as the satellite-based GPS (Global Positioning System), if nodes are equipped with a low power GPS receiver like in GAF protocol [START_REF] Xu | Geography-informed Energy Conservation for Ad-hoc Routing[END_REF].

3. Hierarchical routing. Hierarchical routing, originally proposed in wired networks, is a well known technique that has advantages related to scalability and efficient communications. The concept of hierarchical network architecture is also used to perform energy-efficient routing in wireless sensor networks. That is because in a hierarchical architecture, higher energy nodes can be used to process and send information while lower energy nodes can be used to perform the sensing in the proximity of the target. A good example of hierarchical routing is the one based on clusters where special routing tasks can be assigned to cluster heads in order to improve system scalability, lifetime, and energy efficiency. LEACH [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF] and HPAR [START_REF] Rus | Hierarchical Power-aware Routing in Sensor Networks[END_REF] are two known hierarchical routing protocols. Hierarchical architectures are efficient ways to lower energy consumption performing data aggregation and fusion in order to decrease the number of transmitted messages to the BS.

WSN Clustering

The lifetime of a network is a crucial feature in WSN applications. Another main feature is reducing the size of the routing table in each node of the network. Most of the techniques proposed for prolonging a sensor network lifetime and reducing the routing table size are based on hierarchical architectures or clustering techniques. As shown in figure 1, nodes are gathered in several groups, generally disjointed, which are named clusters. Each cluster has a Cluster Head (CH). The sensors collect data and send it to the CH. CHs can communicate with the Base Station (BS) directly or via other CHs. In some networks, the CHs, referred to as gateways, will perform data aggregation, and send only relevant information through long haul radio communication to the BS. For that purpose, CHs will have specialized processing and telecommunication capabilities, and fewer energy constraints. If the CH is elected only once, we describe these networks as "static" in terms of change of CHs ( [START_REF] Hebden | Pearce Distributed Asynchronous Clustering for Self-Organisation of Wireless Sensor Networks[END_REF], [START_REF] Niu | Sub Cluster Aided Data Collection in Multihop Wireless Sensor Networks[END_REF]).

Figure 1. Clustering In Wireless Sensor Networks

On the contrary, in "dynamic" networks, nodes exchange the role of CH (re-election) according to several metrics like remaining energy, connectivity with other nodes ([8], [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF], [START_REF] Boutaba | Clustering in WSN with Latency and Energy Consumption Constraints[END_REF]). The authors in [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF] propose a clustering-based protocol that uses random rotation of the CHs to evenly distribute the energy load among the sensors in the network. In [START_REF] Fahmy | Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach[END_REF], the authors present a protocol that periodically elects CHs according to a hybrid metric between the node's residual energy and a secondary parameter, such as node proximity to its neighbors or node degree (number of neighbors). In [START_REF] Boutaba | Clustering in WSN with Latency and Energy Consumption Constraints[END_REF], the approach identifies a polynomial time algorithm consisting of recursively computing minimum weighted dominating sets, while respecting latency and energy consumption constraints. In [START_REF] Lin | A clustering technique" for large multihop mobile wireless networks[END_REF], the authors propose a clustering technique for large multi-hop mobile wireless networks. The cluster structure is controlled by the hop distance while the cluster heads are defined by the election algorithm. The distances between a cluster head and each of the members of the cluster are within a predetermined maximum number of hops which can be one or more hops. We will compare our proposed partitioning algorithm with this technique as they are both based on the number of hops to construct zones.

Problematic

As mentioned above, WSN nodes are highly energy constrained due to the limitation of the batteries. Longer lifetimes for WSN are desired, generally because of infeasibility of constant replacement of batteries. Thus, one primary goal is to design energy efficient protocols, our focus being the routing protocol. Performances of routing algorithms are tightly related to the network size and topology. Energy saving in routing protocols over large sensor networks can be achieved either through minimum hop transmissions either trough zone routing which diminishes the routing information management inside zones and enables switching off particular sensors (which are not concerned with the current routing). Communication between standard designed sensors costs energy, independently of the distance between them, and energy consumption is proportional to the number of transmissions. The former is due to the diversity provided by the fact that wireless transmissions are broadcast to multiple nodes. For example, in a 2-hop transmission, C receives a packet from A successfully only if both A to B and B to C transmissions are successful. With relay diversity, the transmission may also be successful if the A to B transmission is overheard by C (see figure 2). In this case, the one hop transmission is preferred because of global energy savings.

In order to exploit distributed architectures and reduce traffic overhead, non uniform routing protocols are proposed. In most cases, non-uniform routing approaches are related to hierarchical networks architectures, which may be cluster based or zone based. In cluster-based routing, the cluster heads are responsible for membership management and carry out the routing function.

Although there are numerous advantages of clustering protocols, most of them are based on information on the network in order to form the clusters. As an example, some protocols [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF] are based on the energy of each node in the network. Other protocols [START_REF] Fahmy | Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach[END_REF] are based on the connectivity of a node with its neighbours. A third type [START_REF] Estrin | Topology Control Protocols to Conserve Energy inWireless Ad Hoc Networks[END_REF] is based on geographical positions (sometimes, this requiring more equipment/hardware). That leads to overload in the network because of control packets, sent to guarantee the delivery of the required information. Consequently, the energy of nodes is decreasing especially in large networks.

In zone routing, where nodes are divided into nonoverlapping or overlapping zones, nodes may reach each other into a same zone with smaller costs compared to maintaining routing information for all nodes in the whole network. Exploiting zone division effectively reduces the overhead generated by the routing information maintenance (because of reduced communications).

Energy may consequently be saved by groups division, but clustering techniques are too expensive in terms of control packets exchanged for the cluster head election. Moreover, cluster heads have the forwarding role in the network, collect and aggregate data. This hierarchy makes an intensive use of cluster heads. In order to preserve them from failure and for load balancing reasons, cluster heads are rotated periodically. This mechanism is energy consuming.

In this paper, we propose a new approach of node grouping into zones in large WSNs. This approach is based on the number of hops needed to create the zones, justified by the previous presented wireless characteristics. We do not need Nodes are allotted to a certain zone of the network. We are not interested in the election of a CH, because this approach is dedicated to a routing protocol inside a zone (inter-zone) and between zones (intra-zone) without need of CHs. Our approach consumes less energy because no packet is exchanged to get information on network, no election or re-election of CHs is necessary.

For our zone routing protocol, we need information concerning the nodes at the borders of the zones. Therefore, our approach of grouping does not belong to clustering techniques because CH election in not an objective in this case. The relevance of our approach of network infrastructure will be evaluated from the energy consumption point of view. Energy consumption is estimated by the number of sent packets, based on the fact that each sent packet consumes energy. This estimation is significant enough, more than an energy consumption indicator, which is difficult to obtain in a real test-bed WSN platform or unrealistic in simulation environments.

OUR APPROACH

In this section we will detail the new approach for sensor grouping in multiple zones. Firstly, we will globally describe the objectives. As illustrated in Figure 3, nodes are grouped in disjoint zones. The nodes of a zone can communicate between each other within one or more hops. If such information must be exchanged between a zone and another, it should pass by the nodes at the border with the other zone (dashed arrows). Our algorithm virtually constructs the zones with the necessary routing information. The border nodes will have a list of the border nodes of the other adjoining zones.

In the suggested approach, the sensors are deployed randomly. We suppose that each node has a global ID.

Information concerning nodes (such as energy, link states, geographic positions, etc...) is not required. This algorithm tends to divide a wireless sensor network in several zones and to provide useful information for the routing. There are some randomly selected nodes named inviting nodes, which launch the algorithm.

Figure 3. Wireless Sensor Network Zone Infrastructure

Zones are determined depending on the zone radius. The zone radius is the maximum number of hops between the inviting node and the invited nodes to its zone. The number of zones and the zone radius are algorithmic parameters that can be modified. The number of inviting nodes equals the number of zones.

Algorithm Parameters

We will precise some used parameters: 1. R (the radius of a zone): the maximum distance, in terms of number of hops, between the inviting node and the invited node. Therefore, each node that has a distance to the inviting node smaller than R, could be in its zone. 2. N: number of nodes in the network. 3. zN: required number of zones. Each node computes during the algorithm the following values:

1. ZID: the identification of the zone to which the node belongs. At first, this variable is initialized by "ZONE_ID" for the inviting node. 2. Type: the type of the node can be NORMAL or BORDER. All nodes have initially the NORMAL type. 3. Tab: the table in which the node, especially the border node, saves information about the border nodes of the neighboring zones. Figure 4 shows the fields of a packet exchanged between the nodes in the network. Transmitter is the global node identification of the node that sends the packet. Destination is the global node identification of the destination node. The TTL is the Time To Live of a packet. Subj is the subject of a packet. Three packet subjects are used in our algorithm:

1. INVITATION: an invitation packet for a zone. This packet is sent by the inviting node with a packet TTL equal to R. It is broadcasted by the nodes that join this zone. 2. DISAGREEMENT: packet used when a node, already allotted to a zone, receives an invitation packet from another zone. The node answers with this DISAGREEMENT packet. 3. BORDER: packet used, typically by a border node, to inform its neighbors that it is a border node.

Transmitter Destination ZID Subj Type TTL

Algorithm Description

Initially, the zones are formed of the inviting nodes (one node per zone). Each inviting node sends an INVITATION packet to its neighbours to join its zone. The nodes receiving this packet will treat it according to their situation. Figure 5 shows, in a flow chart, the behavior of a node when it receives an INVITATION packet. If the node is not allotted to any zone, it will join the same zone from which it receives the packet. Then it will broadcast the packet to its neighboring nodes if TTL 0. If TTL = 0, the node will be a border node. It changes its Type to BORDER, and then it sends a BORDER packet to its neighbours. If the node is already allotted to another zone, it will answer by a DISAGREEMENT packet after modifying its Type to BORDER, and then it inserts into its own table Tab the ID of the Transmitter node and its zone identification, ZID.

As shown in Figure 6, when a node receives a DISAGREEMENT/BORDER packet from another node that does not belong to its zone, it modifies its Type to BORDER, and then it sends a BORDER packet to inform its neighboring nodes of its new type. Then, the node inserts the ID of the Transmitter node and its zone ZID into its own table Tab.

EXPERIMENTAL RESULTS

Experiments were built upon the J-Sim simulator [START_REF][END_REF] dedicated to WSN simulations. It is a component-based simulation environment, using the notion of autonomous component programming model. J-Sim is developed entirely in Java.

Before comparing our approach with another technique, we will show the error ratio (the percentage of nodes not allotted to any zone) depending on the two algorithmic parameters: the zone radius (R) and the number of zones (zN). The simulations were performed on an area of 800x800 and a node communication radius set to 30. The network is made of 300 nodes (low density network). Each simulation result is the average of seven executions.

Figure 7 shows that the error decreases when the zone radius or the number of the zones (number of inviting nodes) increases. In the following simulations, we will demonstrate the effectiveness of our approach in terms of scalability (high node number in the network).

In order to show the performance and the effectiveness of our algorithm, we compared it to another similar group division technique based on the number of hops, that of Lin and Chu [START_REF] Lin | A clustering technique" for large multihop mobile wireless networks[END_REF]. They proposed a clustering algorithm that organizes nodes in clusters based on the number of hops. Each cluster has a cluster head and nodes of a cluster are within a given maximum number of hops R from the cluster head. Clusters may be dismissed and new clusters may be formed. A cluster is dismissed when two cluster heads are within a distance smaller than a predetermined number of hops D (D<=R), called cluster dismiss distance. In this case, each node of the dismissed cluster will try to join a new cluster. If a node cannot find a cluster head within R hops it becomes the cluster head of a new cluster.

In order to make the clustering, each node has a 4-tuple information (i,C i ,D i ,N i ) including:

1. the ID of the node, supposed unique and represented as a positive number, 2. the cluster head ID of the cluster to which the node belongs to, 3. the number of hops from the node to its cluster head, and 4. the ID of the node along the path from the node to its cluster head. The simulations were performed on an area of 800x800 and a node communication radius set to 30. The first simulations (Table 1) were performed with a zone radius equal to 15 and we have varied the number of nodes.

Figure 8 shows the average of the sent packets per node. Our approach decreases in a remarkable way this number which does not exceed 2 for 600 nodes. On the contrary, the algorithm proposed by Lin sends at least three times more packets, due to the necessary messages exchanged to detect distances between cluster heads smaller than the predetermined number of hops, situation which requires cluster merge and consequently node reassignment (generating transmissions). Figure 9 shows that the average of received packets per node increases proportionally with the density of the network. In our approach, it increases more quickly. But this is not a disadvantage because sending a packet costs twice more than receiving one [START_REF] Mainwaring | Wireless Sensor Networks for Habitat Monitoring[END_REF]. Other simulations (Table 2) have been performed with a zone radius equal to 25. The results presented in Figures 10 and11 (for the radius equal to 25) confirm the previous conclusion (the behavior is similar).

Another advantage of our approach is that we can define, in advance, the required number of zones (zN=15 in these simulations) which is not the case in Lin's algorithm where the number of zones may be very important. Therefore, Lin's algorithm creates small zones (several zones contain one/two nodes). Moreover, the number of zones in Lin's algorithm can be neither bounded nor pre-defined. Tables 3 and4 compare the number of zones generated by both algorithms.

The error ratio, in our approach, is the percentage of the unallotted nodes to any zone (these are alone). We can see clearly that even if some nodes remain unallotted in our approach, their number progressively decreases when the number of nodes increases (Tables 3,4). That shows clearly the scalability of the approach. In Lin's algorithm, we have calculated the error as the percentage of the nodes that are alone in their zones. As shown in Tables 3 and4, the error is important and increases when the number of nodes increases. Furthermore, Lin's algorithm generates a considerable number of zones. Each zone has few nodes (in average 2 nodes per zone). Unlike this behavior, in our approach, the number of zones is predefined and the average number of nodes per zone is 26.

These experiments show that our zone division approach based on the number of hops, compared to similar techniques, generates fewer sent messages and the generated zoned can be exploited (few unallotted nodes and enough nodes to make intra-zone routing). Some nodes remain unallotted because the radius is not large enough to reach them.

CONCLUSION AND FUTURE WORK

In this paper, we have proposed a new approach of node grouping in zones in large WSNs. We are interested neither in clustering techniques nor in the election of cluster heads because our approach does not need a traditional clustering.

We do not require any information from neighboring nodes like energy or position, like in clustering protocols. It can be applied for Ad hoc networks as well. This approach relies solely on the use of the number of hops to create the zones. We can determine, in advance, the number of zones. A node assigns itself to the first zone that it receives an invitation from, subject to the radius limit of announcements as they are flooded through the network.

We have demonstrated that our approach is energyefficient because the number of sending packets is reduced dramatically. We have also demonstrated the scalability of our approach by increasing the number of nodes in the network. This approach is meant to help routing inside a zone (inter-zone) and between zones (intra-zone), where there is no need either for CH or for information on the network.

In the future work, our research will be focused on the WSN routing protocols based on this network infrastructure.

  Figure 2. A 2-Hop Transmission

Figure 4 .

 4 Figure 4. Packet Fields

Figure 5 .

 5 Figure 5. An INVITATION Packet Receipt

Figure 6 .

 6 Figure 6. A BORDER/DISAGREEMENT Packet Receipt

Figure 7 .

 7 Figure 7. Error Ratio

Figure 8 .Figure 9 .

 89 Figure 8. Average Of The Sent Packets For R = 15

Figure 10 .

 10 Figure 10. Average Of The Sent Packets For R = 25

Figure 11 .

 11 Figure 11. Average Of The Received Packets For R = 25

Table 1 . Experimental Setup For The Number Of Nodes With R = 15

 1

	Simulation Radius	# nodes
	S1	15	300
	S2	15	400
	S3	15	600

Table 2 . Experimental Setup For The Number of Nodes With R = 25

 2

	Simulation	Radius	# nodes
	S4	25	300
	S5	25	400
	S6	25	600

Table 3 : Error Rate And Number Of Zones For R = 15

 3

	# nodes	Our approach	Lin's algorithm
		Error	zN	Error	zN
	300	26%	15	33,3%	161
	400	10%	15	41%	230
	600	1%	15	43,1%	350

Table 4 : Error Rate And Number Of Zones For R = 25 # nodes Our approach Lin's algorithm

 4

		Error	zN	Error	zN
	300	24%	15	38,3%	164
	400	8%	15	34,2%	210
	600	0.7%	15	46,1%	325