N M Murad

Low Energy Clustering Adaptation Protocol for an Adhoc Wireless Sensor Network

Keywords: Wireless sensor network, low energy consumption, lifetime network, one hop relay, clustering, balanced energy dissipation. I

Energy dissipation in a Wireless Sensor Network is an active research field. Energy dissipation is related to the network topology and protocol used to route data. So, two criteria are proposed to elect a relay. A linear or a random choice from a set of potential nodes to become a relay based on their energy level above a mean threshold energy. These criteria improve the organization of the node communications and the lifetime of the network. The criteria and the protocol called the Self Organization One Hop Low Energy Clustering Adaptation (SOORLECA) are explained. The SOORLECA is designed for environmental and military monitoring with precise requisite measures at each node. No mean data or smoothing data technique is required at the Sink Node (SN). Random topology of the network for 100 nodes over 100m² are simulated to show the protocol performances compared to direct transmission of the node to the SN, short routing path and static clustering protocols. The lifetime and the dissipated energy of the network are our criteria to measure the performance of the WSN. It is shown that the SOORLECA ACMET1 improves 2x the lifetime of network with 61% dissipated energy after 50% of nodes have dead.

INTRODUCTION

Wireless sensor networks (WSN) have been a very active research field in recent years. WSN have numerous advantages. They are easier, faster and cheaper to deploy than wired networks. They have a large coverage area and longer range. They have a higher degree of fault tolerance than other wireless networks. Failure of one or a few nodes affects the monitoring operation of the network. Finally, they are self-configuring and self-organizing. These advantages make them very promising in a wide range of applications, especially in environment and military monitoring. For our case, precise measures are required at each instant.

Many routing protocols have been proposed for sensor networks to make these networks practical and efficient, such as directed diffusion [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF], LEACH [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF], and two-tier data dissemination (TTDD) [START_REF] Ye | A two tier data dissemination model for large-scale wireless sensor networks[END_REF]. These protocols attempt to make the constituents nodes work in unison to achieve specific tasks. Invariably they seek to minimize energy spending and maximize the network lifetime. Some use hierarchical design in their communication model [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF], [START_REF] Lindsey | PEGASIS: Power efficient gathering in sensor information systems[END_REF], [START_REF] Estrin | Next century challenges: Scalable coordination in sensor networks[END_REF], [START_REF] He | Range-free localization schemes for large scale sensor networks[END_REF], [START_REF] Fan | Sequence design for communications applications[END_REF] some such as SPIN and directed diffusion use planar multi-hop design with various optimization techniques such data aggregation and minimal data dissemination [START_REF] Heinzelman | Adaptive Protocols for Information Dissemination in[END_REF], [START_REF] Hall | Mathematical Techniques in Multisensor Data Fusion[END_REF], [START_REF] Klein | Sensor and Data Fusion Concepts and Applications[END_REF]. Moreover, energy efficient data dissemination is among the first set of research issues being addressed. The SPIN is one of the early works that focuses on efficient dissemination of an individual sensor's observation to all the sensors in a network [START_REF] Heinzelman | Adaptive Protocols for Information Dissemination in[END_REF]. However, most routing protocols did not consider the uneven energy consumption problem in sensor networks. In typical sensor networks, the many-to-one traffic pattern is dominant, that is, a large number of sensor nodes send data to the one or a few SN. Sensor nodes near the SN need to relay packets for all other sensors and have much heavier traffic burden. These sensors run out of power much faster than other nodes, and they are referred to as critical nodes. The short lifetime of the critical nodes dramatically reduces the sensor network lifetime. The SOORLECA could be a solution for this kind of problem. Also, the main goal of this paper is to maximize the lifetime of the WSN and to minimize the expenditure of the energy across the network. The extension of this algorithm with a second criterion is used to balance the life of the nodes in each cluster. But the lifetime of the WSN is reduced compared to the first version of the protocol [START_REF] Murad | A Self Organization One hop Relay Low Energy Clustering Adaptation protocol for an adhoc wireless sensor network[END_REF].

Here, the data transmission deadline is not taken into account in the network. Interferences between nodes in the same cluster and interferences between nodes with other clusters are minimized thanks to the TDMA access and the power control at each node. The CSMA MAC and TDMA PHY are used as access protocols in our WSN. There are some constraints about delay processing and delay propagation in the network. But, as the data rate is 2Mbps and the surface S is small, we assume that these points are quite negligible. Any CDMA radio interface could be used. But, the node becomes expensive and the energy consumption is significant, instead the CDMA interface reduces the radio interference.

In this work, we consider a WSN where:

• A one hop transmission is considered. The node sends messages to the sink node (SN) via an only one chosen relay.

• The sink node is fixed and is among the nodes on the playing field S,

• A heterogeneous nodes randomly positioned is grouped in cluster. The size of the cluster is a significant factor that we will see later. Intuitively, it is necessary that the clusters of nodes should be homogeneous. But in real application, the position of the nodes is random.

• We assume that the position of the nodes is known thanks to a GPS or with another algorithm across the network that gives the relative position of the nodes. It is assumed that the energy spent by this algorithm is known and is constant. Because, as the nodes are fixed, it is sufficient to know the position of the nodes once and for all.

• The lifetime of the network is significant. And hence, if any nodes are dead, the network is considered dead. Indeed, the local optimization in each cluster of the energy dissipation allows increasing the lifetime of the network.

• The SN wants exactly the data measured at each node. It means no averaging or smoothing technique at the relay layer is made. Because, when data is aggregated at the relay layer, the size of the message increases. Accordingly, the time to send the data and the dissipated energy increases. In our work, the size of the message is constant. An optimization is done, by using scrambling technique to keep the size of the message constant when the messages are sent across the network.

This paper focuses on the improvement of the SOORLECA proposed protocol in [START_REF] Murad | A Self Organization One hop Relay Low Energy Clustering Adaptation protocol for an adhoc wireless sensor network[END_REF] with balance lifetime performance increase. The details of the communication operations, the data merging at the relay, the scrambling of data measured at node and the criterion decision to choose a relay are explained in section II. Then, a first order radio model and the energy computation are shown in section III. Section IV discusses on the performances and on the operations of the direct transmission, of the minimum transmission and routing energy, of the static cluster, of the LEACH algorithms compared to the SOORLECA one. To finish, a conclusion and some future works are discussed.

II. SOORLECA ALGORITHM

The main characteristic of the SOORLECA algorithm is detailed in this section. We have improved the development of the SOORLECA [START_REF] Murad | A Self Organization One hop Relay Low Energy Clustering Adaptation protocol for an adhoc wireless sensor network[END_REF] in adding a second criterion ACMET2 that balances the life of nodes in each cluster.

A related work as LEACH [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF] works following the mean or smooth of data at the relay, the choice of a number of relays following a probability rule over the network and therefore a variable size of cluster at each communication round.

SOORLECA algorithm is different because five relays are chosen randomly and the algorithm builds five groups of nodes around the five relays. Hence, the number of nodes in each cluster is fixed during the life of the network except if a node is dead. On the other hand, each node in a given cluster becomes by turns a relay following a criterion based on energy level (section C). Also, at the relay layer, all received data of measures from nodes are merged intelligently in using a scrambling sequence. Finally, the SN knows exactly the measures from each node.

A cycle of communication is defined as the quantum time simulation parameter to purchase a measure, to format it in a frame, to send it to the following node and to receive it and to process it.

Section A describes the format of the frame message. The assumptions and the operations at the nodes, at the relay node and at the sink node are explained in the sections B, C and D. To finish, the SOORLECA algorithm is detailed with its initial phase (section E) and its current functioning phase (section F).

A. The frame of messages

The k-bits frame message of 2000 bits is composed by a header and a payload. The length of the header and the payload fields are 464 bits and 1536 bits, respectively. Let us take a particular application like environment monitoring on temperature measurement for understanding. The data of temperature is coded over 12 bits with an Analogic to Digital Converter. Let us note this measure b k as the k-th node data measured. Then a scrambling sequence h k of size L times b k gives the final size of the payload, noted P k . P k will be the payload of the k-th node. Here, L=128. L would be greater than or equal of the number of node N ( L N ≥ ). The scrambling operation is done by each node with its own scrambling sequence. The idea about the scrambling sequence is explained later (see section C).

B. The assumptions on the nodes

Assumptions concerning nodes are made below. The total number of nodes N is known and is dispersed randomly on a surface S. N will be a power of two. An equal energy is distributed initially for each node ( 0.5 / node E J node =

). All nodes have an omnidirectional antenna. Each node k is numbered from 1 to N. The index of the node is the name of the node and the name does not change during the life of the WSN. Each k-th node is associated with the k-th scrambling sequence h k . The scrambling code is built from Hamming sequence [START_REF] Fan | Sequence design for communications applications[END_REF]. The k-th number of Hamming sequence h k related to the k-th node takes easy the sink node to get the desired data measured from the desired node k.

From the radio point of view, the transmission power of each node is supposed to reach all nodes on S. A power control exists in each node. All nodes are not mobile and then the channel propagation variation is quasi-null. But it could have some slow apparent movement of object through the playing field S. The channel transmission is modeled as a path loss channel model (section III). The energy to receive and to process the data is constant and is noted rx E .

C. The relay operations

From [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF], the optimal choice of relay is five for 100 nodes. Five clusters will be built up. Here, node transmission is done with one hop to the SN. So, node information is sent through the relay. A cluster is a group of nodes bound to the relay. The size of the cluster does not change during the life of the WSN except when the node is dead. In a cluster, the re-election of the relay among the nodes is done following the Alive node in Cluster with a Mean Energy Threshold criterion called ACMET. A priori, if the same relay is solicited, its lifetime goes down quickly (section IV.C). Thus, each node within the cluster will become a relay. So, the election relay for the next round is done following the ACMET criterion.

1) The Alive node in a Cluster with a Mean Energy Threshold (ACMET) criterion

Each time that the nodes send data to the relay, they send also their energy level in the header field. Then, the relay records the set of the energy levels and chooses the coming node which will be the future relay following two sub criterions:

ACMET 1: The node getting the greatest energy level among the entire nodes in the cluster is chosen as the future relay.

ACMET 2: A random node is chosen as the future relay among the entire nodes which their energy levels is greater than the mean of all energy levels of nodes in the current cluster.

The relay inserts in the header field the name of the future relay and sends the final message noted P to the SN (see step 7 in section E and step 5' in section F). At the same time, all the nodes are in listen passive mode. Now, they know in the next round who is the next relay and in which order they will send their data.

2) The data processing and the fusion data at the relay node

Let us consider there are Θ nodes in a certain cluster. So at each node k, the data b k is spread by h k and gives P k . P k is sent to the relay. The relay will receive Θ messages of P k . It adds all P k payloads (figure 1). It is our fusion data technique. Finally, only one new payload P from the relay is sent to the SN without increasing the message size.

As an example, figure 1 explains simply the mechanism without taking into account the attenuation of the transmission channel, the errors related to the bit synchronization, the modulation, the demodulation and the decoding technical decision.

Let us take a Hamming matrix H of size 4x4. We extract four sequences of size four, noted h 1 to h 4 in (1). Hamming sequence was chosen because it has particular auto correlation and inter correlation statistical properties [START_REF] Proakis | Digital communications[END_REF], [START_REF] Fan | Sequence design for communications applications[END_REF].

1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 h h H h h                   - -             = =      --                   --         (1)
Four nodes are considered. The size of b k and P k is 3 bits and 4 bits, respectively. One of the four nodes is a relay. We see in figure 1 that the SN could retrieve the initial message b 3 of node 3.

D. The sink node operations

In this section, we explain how the SN works, how measures are collected and how the SN knows passively which node number is in each cluster.

By default the SN knows exactly the number of nodes N over S at the beginning of the life WSN. After receiving five messages from the five relays (step 2), the SN knows the name of each relay. Also, the five P messages received at the SN (step 7) allow a confirmation and an update of the measures database and the state node database. In the step 7, the SN knows the node name within each cluster. Thus, the five conceived clusters do not vary, except when the node relay within the cluster changes and if a node is dead. The size of the cluster does not vary, means that no nodes change cluster during the life of the network.

Finally, the SN knows exactly and passively the state of the WSN. During the life of the network, the SN knows if a node is dead or alive. Because, when the SN descrambles the message with the sequence H k for the k-th node (figure 1) and if the result is quite null, then SN concludes after a certain time that the node is dead.

E. The ininial phase: Operation mechanism

As a preamble, the SN is in or outside the playing field S. Each data from each node must be transmitted without alteration or compression at the relay level. Our algorithm strategy is different from [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF]. The SN will know precisely the data coming from each node.

At the beginning of the life of the network, all nodes are in receipt mode and wait first for the SN message pilot.

Step 1 -The SN sends to all nodes a broadcast message to ask for an election of five relays among N. SN indicates also the length response window noted W.

Step 2 -Election of the five relays following the ACMET criterion. The five relays broadcast a message notifying their names (number of nodes). The sending of the five broadcast messages is done randomly within the W window.

Step 3 -The decisions of the nodes and the SN action.

Step 3.a -Following the strength of the reception power of the five received messages, the node decides which relay it is going to link. Knowing the strength reception power, the node uses power control in order to reduce nodes interferences for future communication. Thus, all nodes shape a cluster around the relay. Finally, there are five created clusters.

Step 3.b -In the same way, the SN obtains the name of the five relays.

Step 4 -Each node nearest a relay informs this relay by a message. The message indicates the name of the node which it binds with the relay by using a CSMA MAC protocol.

Step 5 -During a period of time, the relay counts the number of nodes, noted Θ . A period T is divided in 1 Θ + equal parts. It means that each node will send cyclically all /( 1) T Θ + periods. The relay sends a message that indicates which instant each node of the cluster can send data message to the actual relay following a TDMA access.

Step 6 -Then all nodes send their data to the relay. During the [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF]. /( 1) T Θ -Θ + length, the node goes to sleep mode to save battery energy.

Step 7 -The relay adds all the payload of the nodes, forms a final message noted P and sends it to the SN almost the end of the period T.

We assume that the steps 1 to 5 are done one or several times. Hence, the energy spent is quantifiable and negligible regarding the rate of data transfer in the network.

F. The routine phase: Local cluster reelection relay

The clusters of nodes were created following the initial phase (section E, step 3.a). So, each node of a cluster knows the number of nodes in this cluster and at which instant they have to send their own message (step 5). During the cycle, the nodes send to the actual relay their energy level in the header field and their measures in the payload field. The relay merges the received data (section C-2) and chooses the future relay for the next round thanks to the ACMET criterion (section C-1). So the steps 4 to 7 of initial phase become as below:

Step 4' -Each node in the cluster send to the actual relay their messages (energy level + data measured) at each instant ( 1). /( 1) T Θ -Θ + (old steps 4 to 6). Then, the node goes to sleep mode or listen passive mode to save battery energy.

Step 5' -During a period of time, the relay counts the number of nodes, noted Θ . It could be that some nodes are dead in the cluster during the life of the WSN and the value of Θ decreases. A new period T is divided in 1 Θ + equal parts.

It means that each node will send cyclically all /( 1) T Θ + in the next cycle. Finally, the relay sends to the SN a message P containing three information essentials (old step 7):

• The measures from all nodes in the cluster which are merged in the final message P,

• The name of the future relay for the next cycle,

• At which instant each node of the cluster can send its own message to the future relay following a TDMA access,

As each node is in listen mode, they receive passively the message P for the next cycle of communication.

III. A FIRST ORDER RADIO MODEL AND ENERGY

COMPUTATION

The same radio model discussed in [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF] is applied. To run the node communication in radio high frequency and base band processing, the electronic transmitter (or the receiver) circuitry and the electronic of the digital signal processing dissipate elec E =50nJ/bit . The transmitter amplifier dissipates 2 amp E =100pJ/bit/m . The nodes have power control and can expend the minimum required energy to reach the intended following node or sink node. The node can be turned to sleep mode in order to economize battery.

The transmitting and receiving energy are related to the kbits message and the d distance between two nodes.

( , )

. . .

( ) .

Tx elec amp

Rx elec

E k d k E k E d E k k E  = +      =    (2)
A d² energy loss is used due to the path loss channel model [START_REF] Rappaport | Wireless Communications[END_REF], [START_REF] Proakis | Digital communications[END_REF]. The radio channel is assumed symmetric between two nodes. So, the energy dissipated to transmit messages from the node A to the node B is equal in the opposite way. A data packet of length k-bits=2000 bits is transmitted. When d²=500m², note that the energy dissipated in the amplifier RF circuitry equals the energy dissipated in the base band circuitry and consequently, the cost to transmit a message will be twice the cost to receive it.

IV. SIMULATIONS AND ANALYSES

All curves of performance measure are averaging because a hundred of different topologies of network are simulated. It means that the N nodes do not have the same position at each beginning of the simulation. But they have same position during the simulation. The percentage of live nodes (lifetime of the WSN) and the dissipated energy in the network will be our main criterion to comment the performance of the algorithms.

We remind here that a cycle is the quantum time simulation parameter to purchase a measure, to format it in a frame, to send it to the following node and to receive it and to process it. An event is a measure. And so if an event appears, the measure is processed and sent instantaneously. At the beginning of the simulation, 50J is distributed equitably over the N nodes. All subsections below describe succinctly the mechanism of the algorithms. Then some comments are done over the obtained curves of results.

A. The Direct Transmission protocol

In this protocol, all nodes send directly their messages to the sink node. The events (like measures) occur cyclically and arranged at the node. It means that the nodes send directly to the SN following a cyclic sequence {1, 2, …, N, 1, 2, ...}, called cyclic event. Another manner to transmit directly is that the events occur in following a uniform distribution in [1, N], called uniform event.

When events appear uniformely, the lifetime of the network and the dissipated energy are greater than those of the nodes with the cyclic events (figures 2 and 3). Let note that for a cyclic transmission of data, the lifetime of the network is constant during the first 5000 cycles. Then, the performance decreases quickly compared to the lifetime of network with a uniform distribution transmission data.

B. The Minimum Transmission and Routing Energy (MTRE)

The MTRE consists in searching the relay node nearest from the sink node with one hop transmission. Then, all nodes send their messages to the same relay until it is dead. So, another relay nearest the SN is elected to be the new relay, and so on, until to find a possible relay node eligible in a threshold distance d t from the SN. As in the previous section, the events occur cyclically or uniformly.

The energy dissipated in the network with MTRE is greater than the direct transmission (figure 2). Figure 3 shows that the lifetime network performance with the MTRE algorithm is poor compared to the direct transmission. It is obvious. Because instead to get only one link transmission, we have two links communications. Also, the energy is much used to reprocess the data of each node at the relay layer. This work is made for each node which sends its messages to the SN. So the relay with MTRE works hard compare to the SOORLECA algorithm where, the relay waits to receive all data from nodes, merges data and sends the final message P to the SN only one times.

C. The Static Cluster

Five relays are randomly chosen among the N nodes over S. So, the five clusters of nodes are built around the five relays. The name of the relays and the size of the clusters do not change during the simulation, except if a node is dead in the current cluster. All nodes in the current cluster send their messages to the relay. The relay merges all data and sends to the SN. Hundreds of different topologies of networks are simulated and we average the results (table II). The simulation over one network topology is stoped when the five relays are dead. It is normal, because as the relay is fixed all data go through the relay. And if the relay is dead, no data from nodes could be sent to the SN.

In table II, the first column indicates the number of the network topology. The next five columns indicate the number of nodes in the cluster at the beginning of the life of network. The next five columns indicate the lifetime of each cluster in cycle. And finally, the last column shows the total energy dissipated in the network.

With an onset energy at 50J uniformly distributed over the 100 nodes, only 6% of energy is dissipated in the network when the five relays are dead. If the number of nodes is distributed equally in each cluster, the lifetime of each cluster will be homogeneous. However, the lifetime of this network will be weaker than the lifetime of network with a disproportionate size of cluster. To conclude, if the same node relay is used for each cluster, the relay works hard and dies quickly.

D. A variant of LEACH

The Low Energy Adaptive Clustering Hierarchy (LEACH) algorithm [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF] is simulated. At each cycle, the five relays are randomly chosen among the N nodes. So, the five clusters of nodes are rebuilt around the five relays at each cycle. The simulation is stopped when 50% of the nodes are dead. The performances of the LEACH are shown in table I. As the size of the cluster of nodes and the relay node change at each cycle, it is impossible to display the same result as table II.

E. The SOORLECA protocol

Five relays are randomly chosen in the network. So, the five clusters of nodes are built around the five relays (initial phase). The relay node changes within the cluster all the cycle following the ACMET criterion. The simulation is stopped when 50% of the nodes are dead.

In table III, the first column indicates the number of the network topology. The next five columns indicate the number of nodes in the cluster at the beginning of the life of the network. The five next columns indicate the lifetime of each cluster in cycle. And finally, the last column shows the total energy dissipated in the network. Also, for a number of network topology the first row gives the number of nodes in each cluster at the beginning life of the network. The following second row shows the nodes still alive.

From the table III, when the number of nodes per cluster is balanced, the lifetime of each cluster is moderately the same. So, the lifetime of the network is grandly improved. But, if the number of nodes per cluster is unbalanced, the lifetime of each cluster is slightly unbalanced. But, if we compare to the lifetime of each cluster for the static cluster algorithm, we show that SOORLECA improves the mean lifetime per cluster. Finally, the lifetime of the network with the SOORLECA is more efficient than the static cluster algorithm.

In table I, a synthesis performances of each algorithm is shown. By comparing the SOORLECA protocol to the others, it is shown that the lifetime of the network is larger than the other algorithms with a mean dissipated energy of 62%. That is to say that the 50% of nodes have spent the half of the initial energy network. One could think that the 16% remaining energy comes from the initial phase. So the dissipated energy is smaller than the other algorithms. It is about 31.33 J.

To conclude, the lifetime of the WSN with SOORLECA -ACMET 1 protocol is 2 times higher than the LEACH, 6 times higher than Static Cluster, 3.8 times higher than the MTRE and 2.5 times higher than the direct transmission. Besides, the SOORLECA -ACMET 2 dissipates a little more energy than the ACMET1, but it is less efficient than the LEACH for the lifetime of the WSN. In this paper, we describe the SOORLECA protocol with the ACMET criteria based on the mean energy level in the cluster. SOORLECA is a clustering based routing protocol that minimizes global energy usage by distributing the load to all the nodes in the network and by distributing the load of the relay work to all the nodes in a cluster at different points in time.

The choice of the energy criterion is significant. A linear choice of potential relay is better than a random in regarding their energy level following a mean energy threshold.

The SOORLECA is completely distributed. It requires no control information from the sink node or from the relays. Also, the nodes do not require knowledge of the global network. But, they only require a local knowledge onto the current cluster. This knowledge is the future relay node for the next cycle of communication.

With an initial uniform distribution of the energy over the network, our simulations show that:

• SOORLECA balances the lifetime of nodes in each cluster even if the number of nodes on the cluster is unbalanced.

• SOORLECA increases significantly the lifetime of the network, 2 times more than the LEACH.

• SOORLECA spends less energy than the MTRE and the LEACH. Only, 61% of the energy of the network is dissipated when 50% of nodes are dead.

Also, it appears that a trade-off has to be done with the topology of the network, the energy dissipation by node and also the number of nodes in the cluster.

To confirm our assumptions performances on SOORLECA, we are going to implement the protocol with the OMNET++ platform simulation [START_REF]Omnet++ plateform simulation[END_REF], [START_REF] Hill | System architecture directions for networked sensor[END_REF] and MICA2 wireless measurement system [17].

Based on our MATLAB simulations describe above, we are confident that SOORLECA will outperform conventional communication protocols in terms of energy dissipation and lifetime of the network.

Figure 1 .

 1 Figure 1. Fusion data with a scrambling operation.

Figure 2 .

 2 Figure 2. Total adhoc wireless sensor energy dissipated using direct transmission and MTRE with cyclic or uniform events.

Figure 3 .

 3 Figure 3. Adhoc wireless sensor network lifetime using direct transmission and MTRE with cyclic or uniform event.

TABLE I .

 I SYNTHESIS OF THE PERFORMANCES OF EACH ALGORITHM.

	Algorithms	Dissipated energy (J)

and (%) Mean lifetime of the WSN (cycle)

	Direct transmission Cyclic event	42.66 -85.32%	9830
	Direct transmission Uniform event	34.55 -69.1%	12410
	MTRE Cyclic event	41.77 -83.55%	6245
	MTRE Uniform event	35.76 -71.52%	7693
	Static Cluster	2.83 -6%	4775
	LEACH variant	41,36 -82.72%	14900
	SOORLECA -ACMET 1	31.33 -62.66%	29721
	SOORLECA -ACMET 2	35.42 -70.83%	7804
	V. CONCLUSIONS AND FUTUR WORKS

TABLE II .

 II PERFORMANCE OF THE STATIC CLUSTER

	n°	Cluster	Cluster	Cluster	Cluster	Cluster	Time dead	Time dead	Time dead	Time dead	Time dead	Dissipated
	network	1		2		3		4		5			C1	C2	C3	C4	C5	energy (J)
	1	4		4		27		10		50			229	241	7	43	2	2.90
	2	20		39		11		19		6			12	4	36	13	115	2.81
	3	28		15		16		16		20			7	20	18	18	12	2.73
	4	16		10		34		30		5			17	44	4	5	154	2.92
	…	…		…		…		…		…			…	…	…	…	…	…
	17	20		14		24		16		21			11	23	8	18	11	2.79
	18	13		33		22		17		10			26	5	10	16	42	2.82
	19	9		18		23		11		34			52	14	9	35	4	2.80
	20	9		11		2		8		65			53	34	802	65	2	2.97
	…	…		…		…		…		…			…	…	…	…	…	…
	47	24		19		25		15		12			9	13	8	20	31	2.77
	…	…		…		…		…		…			…	…	…	…	…	…
	89	20		28		7		21		19			12	6	75	11	13	2.80
	90	26		21		8		26		14			7	11	61	7	23	2.81
	…	…		…		…		…		…			…	…	…	…	…	…
	98	53		30		6		4		2			2	5	116	238	827	3.00
	99	13		13		18		37		14			26	26	14	4	22	2.81
	100	5		9		45		14		22			161	47	3	23	10	2.87
	Mean	18.92 21.72 18.11 18.10 18.15		42	44	55	35	62	2.83
						TABLE III.	PERFORMANCE OF THE SOORLECA PROTOCOL
	n°	Cluster	Cluster	Cluster	Cluster	Cluster	Time dead	Time dead	Time dead	Time dead	Time dead	Dissipated
	network	1		2		3		4		5			C1	C2	C3	C4	C5	energy (J)
	1	25		28		17		20		10			-	-	-	-	-	-
	1	12		13		8		9		4			205	201	280	286	635	29.86
	2	16		19		23		31		11			-	-	-	-	-	-
	2	7		9		11		15		5			336	262	227	169	463	29.50
	…	…		…		…		…		…			…	…	…	…	…	…
	50	62		32		15		13		29			-	-	-	-	-	-
	50	30		15		7		6		14			52	160	315	338	167	31.21
	51	21		31		38		23		9			-	-	-	-	-	-
	51	10		15		18		11		4			241	164	133	89	583	30.48
	…	…		…		…		…		…			…	…	…	…	…	…
	97	26		22		9		98		14			-	-	-	-	-	-
	97	12		10		4		47		6			192	235	525	61	424	35.38
	98	32		99		11		3		31			-	-	-	-	-	-
	98	15		49		5		1		15			157	62	443	1967	98	31.68
	99	27		38		30		30		80			-	-	-	-	-	-
	99	13		17		13		14		39			189	57	63	150	52	33.00
	100	26		15		29		24		68			-	-	-	-	-	-
	100	12		7		14		11		33			113	290	165	207	59	32.33
										Mean			276	265	303	343	297	31.33


Somasekhar Kandukuri
email: somasekhar.kandukuri@univ-reunion.fr

Nour Murad

Richard Lorion

A Single-hop Clustering and Energy Efficient Protocol for Wireless Sensor Networks

Energy efficiency is an active research area in WSNs technology. There is an extensive research work going towards this direction and existing mechanisms fail to address the problem completely due to its limited specificity. This work focuses on the idea of enhancing the network lifetime on the basis of clusterheads (CHs) remaining energy levels. Thus, instead of changing CHs at every round for dynamic clustering, we propose two sorts of CH threshold function as energy threshold function and optimal CH range threshold function for maximizing the network lifetime. Simulation results show that our protocol maximizes the network lifetime and captures the data three times more than the other known energy-efficient protocols in the literature.

I. INTRODUCTION

In sensor networks, clustering protocols have the higher network performances in terms of network lifetime, less transmissions and low latencies than the traditional communication methods. In Wireless Sensor Networks (WSNs), there has been a great deal of research conducted on energy efficient clustering protocols, and several well-known works have also been studied in the literature, such as [START_REF] Younis | HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF], [START_REF] Heinzelman | Energyefficient communication protocol for wireless microsensor networks[END_REF], [START_REF]Stochastic analysis, control, optimization and applications: a volume in honor of W. H. Fleming. Systems & control[END_REF], [START_REF] Lindsey | PEGASIS: Power-efficient gathering in sensor information systems[END_REF], [START_REF] Loscri | A two-levels hierarchy for lowenergy adaptive clustering hierarchy (TL-LEACH)[END_REF], [START_REF] Lotf | Hierarchical routing in wireless sensor networks: a survey[END_REF], [START_REF] Ibrahim | An Energy-Efficient and Load-Balancing Cluster-Based Routing Algorithm for CSMA-Based Wireless Sensor Networks[END_REF], [START_REF] Qing | Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[END_REF] and [START_REF] Elbhiri | Developed Distributed Energy-Efficient Clustering (DDEEC) for heterogeneous wireless sensor networks[END_REF]. This paper presents a Single-hop Clustering and Energy-Efficient Protocol (SCEEP) for prolonging the network lifetime based on Cluster-Heads remaining energy and optimal CH range levels. It is mainly considered to reduce the communication over-heads and unnecessary cluster-head changes at every round.

The organization of this paper is as follows. Section II describes the proposed SCEEP algorithm and features of the work are presented. Simulation results and comparisons are discussed in section III. Final section concludes the paper and suggestions for future work are given.

II. SCEEP ALGORITHM

In SCEEP, we consider a homogeneous sensor network model with an initial amount of energy for sensor nodes. We used first order energy model [START_REF] Heinzelman | Energyefficient communication protocol for wireless microsensor networks[END_REF] to design this work. Our approach mainly targets to reduce the communication overheads and unnecessary cluster-head (CH) changes at every round. In this proposal, we have been followed two kinds of clustering principle to elect the cluster-heads. The first principle follows LEACH algorithm of Eq.(1) to initialize the random sensor network at time interval t, and the mathematical expression of the CH probability threshold function is given as

P i (t) = K N -K(R mod N/K) C i (t) = 1 0 C i (t) = 0 (1)
Where K denotes the initial amount of optimal cluster head range, N is the total number of nodes in the network, R is the current round and, C i (t) = 1 if the node i has not been already a cluster head in the last N/K rounds at given time instances t, otherwise C i (t) = 0. According to Eq. ( 1), nodes always have the equal chances to become a cluster head for every round, regardless how much high or little amount of residual energy in the nodes have had. In this scenario, cluster topology or CH changes occur every round without considering the remaining energy levels of the nodes, which may lead to earlier nodes death and communication overheads or degrading the network lifetime. For avoiding the communication overheads and maximizing the network lifetime, we propose the second principle of clustering threshold function, which has been designed based on CHs remaining energy and fixed optimal cluster-head ranges at every round. However, the recent literature works have presented some advanced energyefficient protocols in [START_REF] Ibrahim | An Energy-Efficient and Load-Balancing Cluster-Based Routing Algorithm for CSMA-Based Wireless Sensor Networks[END_REF], [START_REF] Qing | Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[END_REF] and [START_REF] Elbhiri | Developed Distributed Energy-Efficient Clustering (DDEEC) for heterogeneous wireless sensor networks[END_REF], based on nodes residual energy of the network or using different sorts of nodes in the cluster-topology like a heterogeneous model, in which they still failed to reduce the communication and computational costs completely. In our approach, CHs check their energy status and optimal CHs range through the Algorithm 1 before calling for new cluster-heads request, as we can see it below.

The proposed significant features of SCEEP protocol are the following 1) Initial set-up phase of the network, we use LEACH cluster-head selection algorithm to elect the CHs during its first round. 2) After completion of the network first round (in seconds) simulations, current CHs check their energy levels E CHi(t) to continue their intra-cluster communications with the nodes or not, by using energy threshold function E T h . According to the network setup, the energy threshold value can vary based on the given initial energy levels of the nodes. If the current CH energy levels is greater than or equal to the energy threshold level, it continues its intracluster activities to receive the data among the cluster member nodes, otherwise CH destroys the current cluster and calls for the new cluster formation. 3) In this case, we fixed an optimal CHs threshold function PT h , if the CHs optimum level P is lower than the optimal threshold range, then it goes back to the Cluster-head election mechanism for electing new cluster-heads. In this regard, we fixed the optimal threshold range at 3. 4) If current CHs are higher than or equal to the minimum required CHs range, then it continues receiving the data from their corresponding member nodes.

Algorithm 1 Cluster-Head threshold functions Return to the network initialization P i (t)

10: end if 11: else if E CHi(t) < E T h AN D P < PT h then 12:
Send CH_candidates_clear()

Send Clusters_Clear() to destroy 14:

Return to the network initialization P i (

end if 16: end procedure

III. SIMULATION RESULTS

In this simulation, SCEEP sensor network has been placed with 101 static sensor nodes, which are randomly distributed in a field of 400m × 400m. The initial energy of the node is 0.5 J and each data transmission size is equal to 4 kb.

The results of SCEEP simulations are shown in Fig. 1 and2. We presented some measurement metric analysis through both figures. According to the fig. 1, the packet reception rate is between SCEEP and DEEC, DDEEC 3 times more. In Fig. 2 SCEEP, where the First Node Dies (FND) metric shows at round 172 while other protocols FND are at round 28 and 36 respectively. When comparing with Half of the Nodes Alive (HNA) metric, we can clearly observe the differences, where the pointed line indicates in Fig. 2 at 50 nodes alive, SCEEP extends the network lifetime 500 rounds ahead than the other protocols. From the above analysis and proofs, SCEEP indeed have outperforming results than the other protocols. In fact, DEEC and DDEEC are developed with powerful nodes consideration of heterogeneous network model, such as normal and advanced nodes, even though SCEEP extends the network lifetime better than the other protocols.

IV. CONCLUSION

We proposed SCEEP distributed clustering protocol. The experimental results showed that the SCEEP have better performances than the other known protocols. FND and HNA metrics demonstrate that SCEEP maximizes the network lifetime and captures 3 times more data than the other protocols. Additionally, we are working on to develop an advanced CH threshold function for initialization of the network or set-up phase clustering for multi-tier multi-hop heterogeneous model for large scale sensor networks. Furthermore, we are also interested to develop SCEEP on TelosB sensor Network setup for measuring the system efficiency and throughput.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Number of data bits received to the CH over time.


E Graux

Nour Murad

David Carsenat

Bernard Jecko

Signal processing

come

INTRODUCTION

MULTIPLE-INPUT MULTIPLE-OUTPUT

 (MIMO)wireless channels are known to offer better data rate and capacity by employing multiple antennas at both ends of the link [START_REF] Telatar | Capacity of multi-antenna Gaussian Channel[END_REF]. An approach that benefits from the MIMO channel is the use of transmit diversity with space-time block-coding (STBC). Also, the use of multiple antennas at both ends of a wireless link has recently been shown to have the potential to drastically increase spectral efficiency through a technique known as spatial multiplexing (SM) [START_REF] Foschini | On limits of wireless communications in a fading environment when using multiple antennas[END_REF][START_REF] Svantesson | A physical MIMO radio channel model for multi-element multi-polarized antenna systems[END_REF][START_REF] Kyritsi | Effect of element polarization on the capacity of a MIMO system[END_REF][START_REF] Baum | Measurement and characterization of broadband MIMO fixed wireless channels at 2.5 GHz[END_REF][START_REF] Nabar | Performance of multiantenna signaling techniques in the presence of polarization diversity[END_REF]. In signal processing, the electromagnetic phenomena between two near antennas is seldom taken into account. Thus, in this paper, the study of phenomena is also undertaken, when the coherence length isn't respected. Those electromagnetic phenomena are called coupling, and their impact on the signal transmission are investigated here. Different estimations are studied too.

The outline of the paper is as follow: first, the electromagnetic phenomenon coupling with its notations is explained in section 2. In our model, analytical equations describe the system with Alamouti Technique [START_REF] Degen | Performance evaluation of MIMO systems using dual-polarized antennas[END_REF] (section 3) for one particular symbols estimation, while the same study will be made in section 4 for another symbols estimation. Performance results are shown by simulations (section 5). To finish, analyses and conclusion are made in sections 6 and 7.

COUPLING MODEL AND NOTATIONS

Since this coupling's phenomenon is seldom taken into account in the studies, a 2x2 MIMO system with Alamouti Technique is considered with coupling's phenomena between antennas at the transmitter and at the receiver sides. The coupling is defined as a part of one antenna's power which radiates on the other antenna [START_REF] Carr | Practical Antenna Handbook[END_REF]. In fact, a part of the energy over the first antenna is radiated on the second near antenna and vice versa.

Configurations between the transmit antennas and the receive antennas are different. In a wireless communication, the antennas at the Base Station (BS) and at the Mobile Station (MS) can't have the same configurations. This kind of link is used for fairly high flows (near 2Mbit/s). In this article, a 2x2 MIMO system with Alamouti Technique is studied over a worst Rayleigh's fading channel.

In order to normalize the transmitted and received energy at antennas (Fig. 1), α shows the part of energy which remains from transmit antenna Tx 0 to itself and from transmit antenna Tx 1 to itself. Also, 1 α is the part of energy which is radiated from transmit antenna Tx 0 to transmit antenna Tx 1 and which is reradiated by transmit antenna Tx 1 and symmetrically from transmit antenna Tx 1 to transmit antenna Tx 0 . The same model is made for the receiver part with β . In a realistic wireless communication system, it's not very probable to have exactly the same antennas at the emission and the reception parts. Moreover, antennas at the Base Station and at the Mobile Station (or a laptop) have different configurations and diverse geometrical designs, sensibility, directivity, gain, pattern radiations… Let's note ( ) , α β ∈ ℂ the couple of couplings coefficients respectively at the emission and at the reception. Also, These following notations are used along this paper:

ij ij h t h t T = + .
The impulse response of the channel is normalized as

2 1 T n ij T j h n = = ∑
with , i j ∈ ℕ , n T the number of transmit antennas and n R the number of receive antennas [START_REF] Vucetic | Space-Time Coding[END_REF], here n T =n R =2. • i r is the received symbols sequence on the i th receive antenna, • ' i r is the received symbols sequence on the i th receive antenna after coupling,

• i n is Additive White Gaussian Noise (AWGN).
In this model, the Rayleigh channel and the couplings at each side correspond to the channel of this new model. Two different estimations models are studied in this paper to equalize the received signal. The first one takes into account the totality of the received signal whereas the second one uses only one definite part of the received signal in order to reduce the quantity of noise. Even if the share of the used signal also decreases, the goal was to try to find a compromise.

COUPLING ANALYSIS FOR ONE PARTICULAR SYMBOLS ESTIMATION MODEL

In this section, analytical equations are written and describe precisely the couplings. The performance gains are analyzed. The symbols estimation model used in this section is the estimation with all terms (see eq. ( 7) for example). Alamouti Technique [START_REF] Alamouti | A Simple Transmit Diversity Technique for Wireless Communications[END_REF] consists in transmitting coded symbols over the two transmit antennas. If the initial sequence of symbols is like than 0 1 , ,..., ,...

i s s s     , then * * * 0 0 1 2 3 2 2 1
, , , ,..., , ,...

i i e s s s s s s +   = - -   and * * * 1 1 0 3 2 2 1 2
, , , ,..., , ,...

) ( ) ' 0 0 0 1 ' 1 0 1 0 1 1  = + -   = + -   e t s s e t s s α α α α (1) ( ) (
)

' * * 0 0 1 0 ' * * 1 0 0 1 1 1 e t T s s e t T s s α α α α  + = - + -   + = --   (2)
Next, before coupling the received signals are

( ) ( ) ( ) ( ) (
) ( )

0 0 0 00 10 1 00 10 0 1 0 0 01 11 1 01 11 1 1 1 1 1  = + -+ -+ +   = + -+ -+ +   r t s h h s h h n r t s h h s h h n α α α α α α α α (3) ( ) ( ) ( ) ( ) ( ) ( )
 + = -+ - + - +   + = -+ - + - +   r t T s h h s h h n r t T s h h s h h n α α α α α α α α (4)
Afterward, the received signals after coupling are written as (1

( ) ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )
1- 1-1- 1 1 1 1 1 (1 ) 1 (1 ) 1 (1 ) 1 (1 )
h αβ h β α r t s h α β h α β h α β h αβ s βn βn h α β h α β h α β h α β r t s h αβ h β α h α β h α β s h   + +   =   +     - + +   + + + -   - -+ -     -+ - -+   =   + -   - -+ -+ + ( ) 1 0 01 11 1 1 βn βn β α h αβ     + + -   -+   (5) ( )( ) ( ) ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( ) ( )( ) (
) ( ) 1 1 1 1 1 1 1 1 1 1 1 ( ) 1 1 1 1 1   -+ +   + =   - - + -     + - +   - + + -   - + - -     - - + -   + =   + - +     - + - -  - + + -   h h r t T s h h h h s n n h h h h r t T s h h h h s h h β α αβ α β α β αβ β α β β α β α β α β α β β α αβ α β α β αβ β α 1 0 1  + + -  n n β β (6)
Finally, the symbols are estimated thanks to the symbols estimation model where all the terms using ( ) , α β are taken into account:

( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 s h h h h r t h h h h r t h h h h r t T h h h h r t T s αβ α β β α α β α β αβ α β β α β α α β αβ α β α β β α α β αβ β   = + - + - + - - +     - + + - - + - +     - + - - + + - + +     - - + - + - + +   = - ɶ ɶ ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( )
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 h h h h r t h h h h r t h h h h r t T h h h h r t T α α β αβ α β α β β α α β αβ αβ α β β α α β α β αβ α β β α                + - - + + - +     - - + - + - + -     + - + - + - - + -     - + + - - + - +             (7)
To study the behaviour of the diversity technique, we estimate the received SNR in computing the mean and the variance of the expression [START_REF] Degen | Performance evaluation of MIMO systems using dual-polarized antennas[END_REF].

0 1 [ ] 0 [ ] 0 E s E s = = ɶ ɶ (8) ( ) ( ) ( ) ( ) (
)

2 2 2 0 0 0 2 2 2 2 0 [ ] [ ] [ ] 3 2 4 4 1 2 2 9 4 1 1 2 2 8 (1 ) 8
4 3 1 3 1 2 2 s E s E s E s E N σ α β β σ α β β β β α β β = = -   - - +     = - + + -     - +   + + + - ɶ ɶ ɶ (9)
The expression of the received SNR for the symbols is given by ( 10):

( ) ( ) ( ) ( ) 0
E SNR N α β β α β β β α β β =   - -+ - + + - -+   + + -     (10)
The expression in square brackets in eq. ( 10) corresponds to the channel gain in this particular diversity technique.

Thanks to Eq. ( 10) it's easy to say that the received SNR (noted SNR) depends on three parameters: α , β and 0 s E N , which is the transmitted SNR. The study of Eq. [START_REF] Alamouti | A Simple Transmit Diversity Technique for Wireless Communications[END_REF] gives some parametric curves. The parametric curves have been plotted for values of α which varies from 0 to 1 by step 0.1.

The more relevant curves are showed here. The optimal couple of couplings is ( ) ( ) , 0.5,1 opt opt α β = (in module, the phase is equal to zero). So, to have the best performances, the power transmission must be shared in two equal parts on the two transmit antennas.

But for 1 β = and an unspecified value of α and 0 s E N , the SNR doesn't enormously vary, so with numerical simulations, the performances of the system will be closed whatever the value of α . Here, with numerical values, it's easy to say that a particular values of α or β will give the best performances, but with numerical simulations, the difference will not be also obvious.

COUPLING ANALYSIS FOR ANOTHER SYMBOLS ESTIMATION MODEL

In this part, the estimation of symbols is different from the one used in section 3. The goal was to find a new estimation of the symbols which allows reducing the noise quantity. In this section, the estimation will take into account only the terms which contain β . By the means of this new symbols estimation model, the loss of signal is compensated by the reduction in the quantity of noise. The equations which describe the studies system are the same that in section 3, but the estimation of the symbols is different. In eq. ( 7), only the terms which contains β are preserved. So, in this section, the symbols are estimated thanks to eq. ( 11):

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (
    = + - + + - +         - + + + - + +         = - + + - + -       + - + -   ɶ ɶ ( ) ( ) ' * 11 1 0 1 h r t T β α              + - +     (11)
And so, the expression of the SNR becomes:

( ) ( ) ( ) ( ) 2 0 23 1 1 3 2 * 4 20.5 6.5 15 1 s E SNR N α α α α β β α α   -- - + +   =   - + +   (12)
As in the last sub-section, it will be possible to study the behavior of this SNR with the three parameters: α , β and

α α α α β β α α   -- - + +     - + +  
represents the channel gain.

Thanks to eq. ( 12), it's easy to say that the received SNR again depends on three parameters: α , β and 0 s E N .

The study of eq. ( 12) allows plotting the following curves: . The results are very closed, so it's undeniable that 1 opt β = is the optimal value, but for α it's not also obvious. Here, the optimal values found show that the best performances will be obtained for a system with no coupling effect at each side of the transmission system.

NUMERICAL SIMULATION RESULTS

In this section, realistic simulations are made for the two estimated models in a numerical wireless communication chain.

First symbols estimation model

Thanks to a simulation plan, the optimal values of the couplings for the studied system have been found. The coupling coefficients are complex numbers written as:

≃

. The profit is near 40dB to reach the same quality of service.

Second symbols estimation model

In this part, a second estimation model is studied. For the three techniques described in the first section, some numerical simulations made it possible to find the optimal coupling coefficients. The best performances are obtained when the coupling coefficients are equal to: The results show that for this particular estimation model, the best performance will be obtained when there're no couplings at each part of the communication link.

For this second symbols estimation model, the optimal results are generally obtained for 1 opt α = or 1 opt β = , this means that the best results are for an uncoupled antennas system. The curves can also give to the users the behaviour of the communication link if the coupling coefficients change and deviate from their optimal value. For the studied system, to obtain a BER of

ANALYTICAL AND NUMERICAL SIMULATION COMPARISON

Initially, a comparison between the performances with optimal couplings for the two diverse symbols estimations can be made (Fig. 18). Then, an analysis is carried on to release the similarities between the analytical expressions and the results of numerical simulations. In fact, when the transmit SNR increases, the performances are better, so the BER decreases and vice versa. The analysis of the SNR expressions enables us to understand the behaviour of the studied system according to the various parameters: α , β and according to the parameters α and β , the analysis shows that the analytical study and the numerical simulations coincide for the two symbols estimation models.

CONCLUSION

Between theoretical curves (obtained thanks to the study of eqs. [START_REF] Alamouti | A Simple Transmit Diversity Technique for Wireless Communications[END_REF] and ( 12)) and optimal couplings coefficients ( ) , opt opt α β found with the numerical simulations, the results are closed. The optimal couplings are often equal to one (in module).

This corresponds in fact to no coupling between the antennas. So, the coupling between antennas often degrades the performances of the connection link. According to the studied technique, the two diverse estimations don't give the same results and offer solutions to equalize the received signal with the a priori knowledge of the coupling coefficients. The analytical study permits to know how the diversity system will behave according to the various parameters. With the numerical simulations, it's easy to know if a value of coupling will considerably degrade the performance of the system or if the degradation will tiny. In this study, the antennas at the transmit or receive sides are much closed, so the channels will be correlated.

Figure 1 .

 1 Figure 1. Coupling model.

  that the antennas at the transmitter or at the receiver are coupled. In the other way

2 1β

 2 = mean that the antennas at each part of the communication link are uncoupled.



  with i ∈ ℕ . The Alamouti's coder works on two consecutive symbol times. Then, the transmitted signals after coupling are

(

Figure 2 .Figure 3 .Figure 4 .

 234 Figure 2. Analytic expressions' analysis for Alamouti Technique (first symbols estimation model), α = 0. alpha (module) = 0,5

SNRFigure 5 .Figure 6 .Figure 7 .

 567 Figure 5. Analytic expressions' analysis for Alamouti Technique (second symbols estimation model), α = 0.

6 10

 6 that it's more judicious to have signals in phase. For analysis, to obtain a BER of

6 10 -

 10 , the required SNR at the emission part

  studied case, the expression of the SNR can be studied for one parameter by fixing the other parameters. If the function is studied with the parameter 0 more the received SNR is elevated. If the expression is now studied

Table 1 .

 1 Comparison (first symbols estimation model).

	Es/N0 (dB)
	0 2 4 6 8 1012 14 1618 2022 2426 2830 32 3436 3840 4244 46 4850 5254 5658 60
	1,E+00
		No diversity
	1,E-01
		Alamouti, first estimation
	1,E-02	Alamouti, second estimation
	1,E-03
	BER
	1,E-04
	1,E-05
	1,E-06
	1,E-07
	Figure 8. Comparison of the results for each symbols
	estimation model.
	Figure 8 shows that performances vary according to the

Table 2 .

 2 Comparison (second symbols estimation model).


Theory and Applications of Bidimensionality

Dimitrios M. Thilikos 1 AlGCo project-team, CNRS, LIRMM Department of Mathematics, National and Kapodistrian University of Athens Bidimensionality Theory is a meta-algorithmic theory whose main ingredients are the Grid Exclusion Theorem of the Graph Minors series of Robertson and Seymour and the celebrated Courcelle's Theorem. The grid exclusion theorem states that if a graph excludes a bidimensional grid as a minor (a graph H is a minor of a graph G if H can be obtained by some subgraph of G by contracting edges) then its structure topologically resembles the structure of a tree (in technical terms, it has small treewidth). Intuitively, this result says that the absence of the bidimensional structure of a grid implies that a graph has the "mono-dimensional" structure of a tree. On the other side, Courcelle's theorem states that if a problem on graphs is expressible in Monadic Second Order Logic (MSOL), then it is possible to solve it in linear time when the treewidth of their input graphs is fixed. Intuitively, this theorem expresses the fact that the monodimensional structure of a tree (i.e., small treewidth) makes it possible to treat a graph as the input string of a finite-state tree automaton, where the finiteness of its states is guaranteed by the MSOL-expressibility of the problem. Combining these two results together, we derive that the absence of the bidimensional structure of a grid, enables the applicability of the "divide-and-conquer" technique for problems of certain descriptive complexity. It appears that for many graph theoretic problems the existence of a grid-minor (or other bidimensional strucures) on the input graph provides a certificate for an immediate negative (or positive) answer and, for the remaining instances, a dynamic programming approach on graphs of bounded treewidth may give an answer to the problem. This phenomenon reveals fruitful interleave between graph structure and logic in graph algorithms. Bidimensionality Theory aims at systematizing this idea and extending its applicability in diverse paradigms of algorithm design.

The notion of problem bidimensionality was proposed for the first time in [?]. Given some graph invariant p, we denote by Π p the problem of asking, for some pair (G, k), whether p(G) ≤ k and we say that Π p is minor bidimensional if

i) p is minor closed, i.e. if G 1 is a minor of G 2 , then p(G 1 ) ≤ p(G 2 ). ii) for every k, p(L k ) = Ω(k 2 ) (here, L k is the (k × k)-grid).
Some of the main meta-algorithmic results of Bidimensionality Theory can be summarized as follows: Let Π p be a minor bidimensional problem and let G be a class of graphs where

∀ G∈G treewidth(G) = O(max{k | L k is a minor of G}). (1)
Let Π G p be the restriction of Π p to the graphs in G. Then the following hold: 1. If p(G) can be computed in 2 O(treewidth(G)) • n O(1) steps, then there exists an algorithm that decides, given a graph G in G as input, whether All above results concern only minor-closed parameters. The counterpart of the above theory for contraction-closed parameters is based on the notion of contraction bidimensionality, uses slightly different versions of Conditions i, ii, and (??), and its algorithmic potential is investigated in [?]. Currently the combinatorial challenge of Bidimensionality Theory is to broaden its applicability by detecting graph classes where (??) holds or to suitable adapt/extend/modify Conditions i, ii, and (??) so that similar results can be derived for wider families of graph theoretic problems.

p(G) ≤ k, in 2 O( √ k) • n O(

  1) steps (see [?]). 2. If p satisfies some separability property (see [?, ?] for the definition) and p(G) ≤ k ⇐⇒ ∃S ⊆ V (G) : |S| ≤ k and (G, S) |= ψ where ψ is a MSOL sentence, then the problem Π p admits a linear kernel, i.e., there exists a polynomial algorithm reducing every instance (G, k) of Π p to an equivalence instance (G , k ) where |V (G )| = O(k) and k ≤ k (see [?]). 3. If p satisfies some separability property and is reducible (in the sense these notions are defined in [?]), then there is an EPTAS for computing p(G) on the graphs in G (see [?, ?]). According to [?], every graph class excluding some fixed graph as a minor satisfies (??). Further extensions of the applicability of the above theory on geometric graphs have been given in [?] and [?].

This work was co-financed by the European Union (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: "Thales. Investing in knowledge society through the European Social Fund.


Comment on "The Quadruple Bonding in C 2 Reproduces the Properties of the Molecule" Gernot Frenking *[a] and Markus Hermann [a] Keywords: C 2 , Bonding analysis, Multiple bonding, Bond strength, Electronic state, σ bonding The title publication by Shaik et al. [1] on the chemical bonding in C 2 is an important contribution to understand the origin of the conflicting views about the strength of the interatomic interactions in dicarbon which are presented in their paper and in the publications of other groups using a variety of methods. [2,3] The original claim of a quadruple bond in C 2 possessing two σ bonds which are stronger than the single σ bond in acetylene [4] is now substantiated with a calculated intrinsic ("in-situ") bond strength of 156.6 kcal/mol for the total σ bonding in dicarbon and 138.7 kcal/mol for the σ bond in HC≡CH. The results come from valence bond (VB) calculations, which give bond dissociation energies and bond lengths that are in good agreement with experimental data and with the results of the other methods.

We want to point out that the core of the controversy is not the number of bonds but the strength of the total σ bonding in C 2 , which is suggested by several groups to be much weaker than in acetylene. [2] We studied the paper in order to understand how the value of 156.6 kcal/mol for the σ bonding in C 2 was calculated. There are contradicting statements and missing information which make the numerical result and the conclusion questionable. The authors determine their value for the in-situ bond strength for the σ binding by comparing the spin-coupled structure Ψ 2σ which has two σ bonds with a quasiclassical state Ψ QC where the two σ bonds (σ in and σ out ) are decoupled. They calculate the in-situ strength of the σ bonding D 2σ in-situ from the energy difference between Ψ 2σ and Ψ QC . This is shown in Figure 1 which is adopted from [a] Dr. M. Hermann, Prof. G. Frenking, Fachbereich Chemie, Philipps-Universität Marburg, 35032, Marburg, Germany.

Email: frenking@chemie.uni-marburg.de state exhibits a smooth curve toward carbon atoms in the 3 P ground state [START_REF] Boschen | [END_REF] . The analysis of the full-valence CASSCF calculation of C 2 shows that the contribution of the configuration which has a genuine (electron-sharing) quadruple bond between carbon atoms in the 5 S state to the total wave function is only 13.7%. [2b] The weight of the configuration which comes from the interaction between carbon atoms in the 3 P state is 71.0%. This makes us wonder about the choice of averaged energies of Ψ QC(1) (Det1) and Ψ QC(2) (Det2) for estimating the strength of the σ bonds in the VB calculations of Shaik et al. [1] It would be helpful to know the individual values of D 2σ in-situ ( 1) and D 2σ in-situ (2) with respect to Ψ QC(1) (Det1) and Ψ QC(2) (Det2) as reference states. The authors should also inform the general community of chemists, who are less familiar with VB calculations than with MO methods, about the reason why averaged values of the two reference states, which are vastly different in energy, were used. They should also elucidate why carbon atoms with a 3 P state are shown for the quasiclassical reference state in Scheme 4, when the 5 S state was earlier proposed as reference. There is no 1:1 connection between VB and MO terms but the interpretation of the numerical data that are provided by the two methods, which give both correct values for bond dissociation energies and bond lengths, must not lead to fundamentally opposite conclusions concerning the nature of the bonding. Breaking rules is fun, but only when it comes from traceable procedures. [8] We also want to comment on the very small overlap population of the antibonding 2σ u MO of C 2 that may even become positive, which is suggested by the authors as evidence that the orbital "be only weakly antibonding, if not bonding". [9] The small overlap population comes from the antisymmetry constraint of the orbitals due to the Pauli principle. The enforcement of orthogonality to the orbitals of C 2 , which removes electronic charge from the overlapping region of the 2σ u MO, is associated with an energy change (Pauli repulsion) in the order of 250 kcal/mol. [10] The small negative or even positive values for the overlap population are the final result but not the driving force of the electronic interactions that are subject to the Pauli principle. It is therefore misleading to use small overlap populations as indicator of weak or even absence of antibonding forces.

Figure 1 .

 1 Figure 1. Determining in-situ singlet-coupling interaction energies for the σ bonds in C 2 as described by Shaik et al. in reference 1. Part 1a shows the 3 P state of carbon as reference state Ψ QC(1) as adapted from their Scheme 4. Part 1b shows the 5 S state of carbon as reference state Ψ QC(2) which is depicted in their Supporting Information. The energies of Ψ QC(1) and Ψ QC(2) differ by 192.8 kcal/mol.

Acknowledgement. This work was supported by the Deutsche Forschungsgemeinschaft.

Scheme 4 of Shaik et al. [1] The left part 1a shows the quasiclassical state Ψ QC (1) that is depicted as Ψ QC in their scheme 4. The two electrons at each carbon have opposite spin which means that the carbon atoms have a 3 P state, because the p(π) electrons that are not shown have identical spin. This contradicts the statement of the authors: "If, however, the molecule is indeed quadruple bonded, then each carbon atom must have four singly occupied orbitals in the molecule. In such a case, the legitimate reference state is 5 S." [5] It is puzzling that the authors refer to the 5 S of carbon as reference in the text, but then they sketch the 3 P state for the quasiclassical reference state Ψ QC .

Figure 1 Decoupling the two σ bonds in C 2 actually leads to two quasiclassical states, the second of which Ψ QC( 2) is shown on the right hand side in Figure 1a. The latter state Ψ QC(2) has two carbon atoms in the 5 S state. The two reference states Ψ QC (1) and Ψ QC(2) are very different in energy, because the 5 S state of carbon atom is 96.4 kcal/mol above the 3 P ground state. [START_REF] Moore | Atomic Energy Levels[END_REF] Thus, the energy difference between Ψ QC(1) and Ψ QC(2) is 192.8 kcal/mol. Estimating the insitu σ bond strength in C 2 strongly depends on the choice of the quasiclassical reference state.

The authors mention the existence of a second quasiclassical reference state in the caption of Scheme 4 saying that they took "the average of the two" with further reference to the Supporting Information. On page S23 of the Supporting Information [1] one finds a sketch of the two determinants Det1 and Det2 that describe the coupling between two carbon atoms in the 3 P state (Det1) and the 5 S state (Det2), which agrees with our descriptions of Ψ QC (1) and 1. It is important to recognize that both reference states Ψ QC(1) and Ψ QC(2) are associated with four bonding components in C 2 , albeit with drastically different σ bond strengths.

The crucial question concerns the two determinants Det1 and Det2 and their use to determine the numerical value of 156.6 kcal/mol for the in-situ σ bond strength D 2σ in-situ in C 2 .

The authors are saying in the Supporting Information that "their averaged energies were used as the reference state". This is in conflict with their own statement that the 5 S state should be used as reference. There is equal spin distribution between the carbon atoms in C 2 , but that does not mean that Ψ QC(1) (Det1) and Ψ QC(2) (Det2) are equally valid reference states, because they differ in energy by 192.8 kcal/mol. The calculated dissociation of C 2 in the X 1 Σ g + ground