Nadine Boudargham
email: nboudargham@ndu.edu.lb

Jacques Bou Abdo
email: jbouabdo@ndu.edu.lb

Jacques Demerjian
email: jacques.demerjian@ul.edu.lb

Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Abdallah Makhoul
email: abdallah.makhoul@univ-fcomte.fr

Efficient Cluster Based Routing Protocol for Collaborative Body Sensor Networks

Keywords: CBSN, Routing, Delay, Energy Consumption, Packets Dropped

Collaborative Body Sensor Networks (CBSNs) are collection of Body Sensor Networks that move in a given area and collaborate, interact and exchange data between each other to identify group activity, perceive events detected by group of individuals, and monitor the status of single and multiple persons. Even though some routing algorithms were proposed for Wireless Sensor Networks (WSNs) and Body Sensor Networks (BSNs), very few studies were found to cover routing in CBSNs. In this paper, we propose a robust cluster based scheme that increases the routing efficiency through the three steps of the routing process: cluster formation, cluster head election, and routing operation of data to the Base Station (BS). MATLAB simulations are performed to compare the performance of the proposed algorithm to other existing routing schemes. Results show that the proposed scheme outperforms others in terms of delay, energy consumption, and packet drop percentage, and therefore succeeds in addressing CBSN challenges.

INTRODUCTION

Collaborative Body Sensor Network (CBSN) is a network formed of multiple Body Sensor Networks (BSNs) [START_REF] Boudargham | Investigating low level protocols for wireless body sensor networks[END_REF] moving in the same area and able to collaborate and synchronize among each other to reach a common objective. This intercommunication between BSNs allows the development of collaborative applications like interactive games, social interactions between multiple persons, as well as group status monitoring such as supervising rescue teams condition, sports team performance, and employees status in industries etc., where instead of single individual monitoring, exchanging data and cooperative processing between many BSNs is a must to detect the activity of a group, identify the events perceived by many persons, and monitor the health of many individuals at the same time.

Cluster based routing is known to be efficient in extending WSN and BSN lifetime through spreading the energy consumption among sensor nodes [START_REF] Ul Huque | Sea-ban: Semi-autonomous adaptive routing in wireless body area networks[END_REF]. In cluster based routing, nodes are assembled into clusters [START_REF] Farhat | On the topology effects in wireless sensor networks based prognostics and health management[END_REF], and every cluster has one Cluster Head (CH) that is elected among the corresponding nodes. Nodes within the cluster transmit their data to the CH, and only the CH can forward this data to the sink. The number of active nodes is therefore reduced, which decreases the delay and energy consumption of the network.

Even though many cluster based routing algorithms were proposed for WSNs and BSNs, very few studies were found to cover routing in CBSNs. For instance, authors in [START_REF] Tauqir | Distance aware relaying energyefficient: Dare to monitor patients in multi-hop body area sensor networks[END_REF][START_REF] Watteyne | Anybody: a self-organization protocol for body area networks[END_REF][START_REF] Verma | Energy-efficient clusterbased mechanism for wban communications for healthcare applications[END_REF] propose schemes to route data between many patients in a hospital, however these articles do not account for mobility as they consider sensor nodes to be fixed either on the bedside, or in specific locations of the hospital. On the other hand, Aminian et al. propose in [START_REF] Aminian | A hospital healthcare monitoring system using wireless sensor networks[END_REF] a system capable of monitoring several patients moving in a hospital; however, authors suggest using relay nodes placed in predetermined places to route data sent by the coordinator node of every patient to the Base Station (BS), which may not be feasible in all mediums.

In this paper, we study and propose an efficient cluster based routing scheme that is able to send data reliably from many BSNs in motion to the BS, without the need to add additional nodes to the network.

The following scenario is considered. The CBSN is formed of several BSNs moving in a 400 m 2 indoor area. Every BSN is a person who can be a patient in a hospital, employee in an industry or a rescue team in a building, equipped with medical sensors and a coordinator node. The medical sensors capture physiological data from the person's body and send it to the corresponding coordinator node who will transmit it in return to the BS. Every BSN is considered to be one node in the CBSN; and therefore, in this paper, a new cluster based routing algorithm of data from the different nodes in motion to the BS will be proposed and compared to other existing schemes.

The remainder of the article is organized as follows: Related work and research contribution are discussed in Section 2. A new efficient cluster based routing algorithm is then proposed in Section 3. Simulation of the suggested scheme is presented in Section 4, to end up with the conclusion and future work in Section 5.

Related Work and Research Contribution

Many cluster based routing schemes for WSNs and BSNs are presented in literature. They differ from each other by the way clusters are formed, the criteria used to elect the CH of each cluster, and the routing process for data to reach the BS. For instance, LEACH protocol [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF] elects CHs by random rotation to distribute the energy consumption among all nodes in the network. Non-CH nodes then join the nearest CH. However, since CHs are randomly elected, non-CH nodes might be located out of the communication range of the elected CHs, and cannot therefore join a cluster; also, the number of nodes joining a cluster can be large, which would quickly exhaust the energy of the corresponding CH. In addition, direct transmission of data from nodes to the CH and from the CH to the sink is used, which might not be efficient if the distance between the nodes and the CH or between the CH and the sink is large [START_REF] Boudargham | Efcient cluster-based routing algorithm for body sensor networks[END_REF].

Another cluster based scheme is the Improved LEACH protocol for BSN presented in [START_REF] Zhang | Research on the wban structure based on leach protocol[END_REF]. Improved LEACH is an enhancement over the LEACH protocol since CHs are not only elected based on a certain probability, but also based on the residual energy of the nodes and the nodes type; i.e., less important nodes with the highest residual energy are chosen to be the CHs in a round. The problem with Improved LEACH is that even though it elects CHs based on significant parameters, it ignores other important criteria such as the nodes' distance to the sink, their mobility, and their communication range. Also, like in LEACH, the number of cluster members might be high, and direct transmission of data is adopted which decreases the routing efficiency [START_REF] Boudargham | Efcient cluster-based routing algorithm for body sensor networks[END_REF].

In LEACH-TLCH [START_REF] Fu | An energy balanced algorithm of leach protocol in wsn[END_REF], a secondary CH is elected and used in case the energy of the primary CH decreases below the average energy of all nodes in the network, or the distance between the primary CH and the BS increases above the average distance between the nodes and the BS. Non-CH nodes send their data to the primary CH either directly, or through the secondary CH that is the node with the highest residual energy in the cluster. This algorithm takes into account the energy of nodes in the election of the secondary CH, but other important parameters are disregarded. for instance if the distance between the secondary CH and primary CH is large, or if the connectivity between them is limited, the energy of the secondary CH will drain very quickly and data transmission will not be reliable.

Authors in [START_REF] Arioua | Multi-hop cluster based routing approach for wireless sensor networks[END_REF] propose a Multihop Cluster Routing approach for WSN. This scheme combines both LEACH and Minimum Transmission Energy (MTE) protocols. In this scheme, CHs are elected by random rotation, however unlike LEACH where cluster members send their data via direct transmission to the elected CH, data is sent indirectly via multi-hop route from the nodes to the CH based on the shortest path, in order to further minimize the energy consumption of nodes. Even though this algorithm succeeds in prolonging the network lifetime through multi-hop routing, CHs are elected via random rotation; inappropriate CHs might therefore be selected, which would decrease the routing efficiency.

Authors in [START_REF] Watteyne | Anybody: a self-organization protocol for body area networks[END_REF] propose the Anybody protocol, in which nodes with the highest density are elected as CHs, where the density is computed as the ratio of the number of links to the number of nodes within two-hop neighborhood. The data is then sent from the cluster members to the elected CH via a multi-hop intra-cluster path, and from the CH to the sink through a multi-hop inter-cluster route. Since the CH election is based on highest density, this algorithm may not be efficient when the number of cluster members is high, specially that other important criteria such as energy of nodes, distance to the sink, etc. are not considered in the CH election process.

The above discussion shows that none of the cluster based schemes implemented for WSNs and BSNs present a complete solution that addresses CBSNs requirements. They either present shortcomings in the CH election criteria, or in the cluster formation, or in the routing operation.

Therefore in this paper, a robust cluster based routing scheme is proposed for CBSN to provide better QoS and reliable transmission of data. The main aim of this algorithm is to increase the routing efficiency in CBSN by decreasing the energy consumption and delay through every step of the routing process: the clusters formation, the CHs election, and the routing operation of data to the sink.

Proposed Routing Algorithm

As stated earlier, the CBSN is formed of many BSNs, and in the proposed algorithm, every BSN (one person) is represented by one node. Therefore in the following, a routing scheme of data from the coordinator node of every BSN to the BS is suggested.

The proposed algorithm consists of three steps:

1. Clusters formation 2. Cluster head election 3. Routing operation: Intra and Inter cluster routing.

Energy Model

The first order energy model, was used in the simulations. This model is widely adopted in many WSN and BSN studies [START_REF] Tauqir | Distance aware relaying energyefficient: Dare to monitor patients in multi-hop body area sensor networks[END_REF][START_REF] Verma | Energy-efficient clusterbased mechanism for wban communications for healthcare applications[END_REF][START_REF] Nadeem | Simple: Stable increased-throughput multi-hop protocol for link efficiency in wireless body area networks[END_REF][START_REF] Javaid | M-attempt: A new energy-efficient routing protocol for wireless body area sensor networks[END_REF][START_REF] Sahndhu | Bec: A novel routing protocol for balanced energy consumption in wireless body area networks[END_REF][START_REF] Tümer | Energy-efficient and fast data gathering protocols for indoor wireless sensor networks[END_REF][START_REF] Liaqat | Distance-based and low energy adaptive clustering protocol for wireless sensor networks[END_REF]. The corresponding transmitter and receiver energy are as follows:

E T X (L, d) = E T x-elec • L + ε mp • L • d n (1) E RX (L) = E Rx-elec • L (2)
E T x-elec and E Rx-elec represent the transmitter and the receiver electronic circuits' energy consumption respectively, and ε amp represents the the transmit amplifier's energy consumption [START_REF] Sahndhu | Bec: A novel routing protocol for balanced energy consumption in wireless body area networks[END_REF]. These values depend on the type of the transceiver used. We consider using Nordic nRF24L01 2.4 GHz transceivers that are frequently used in BSNs [START_REF] Nadeem | Simple: Stable increased-throughput multi-hop protocol for link efficiency in wireless body area networks[END_REF][START_REF] Javaid | im-simple: improved stable increasedthroughput multi-hop link efficient routing protocol for wireless body area networks[END_REF]. L indicates the packet size, and n represents the average Path Loss (PL) exponent of the network. Since the value of the Path Loss (PL) exponent in indoor locations ranges between 1.4 and 6 depending on the present obstructions [START_REF] Perez-Vega | A simple and efficient model for indoor path-loss prediction[END_REF], it is set to an average of 3.5 to emulate an indoor environment with obstacles causing diffraction and scattering of the signal.

Clusters Formation

To form clusters, we consider that the BS is located at the center of MxM sensing area where persons forming the CBSN are distributed. This sensing area will be divided into a fixed number of clusters based on the optimal number of clusters formula presented in Equation ( 3). This formula is chosen since it evaluates the best number of clusters that leads to minimum total energy consumption in the network which is our target [START_REF] Amini | Cluster size optimization in sensor networks with decentralized cluster-based protocols[END_REF].

k optimal = N s • ε f s • A 2π(ε mp • d n toBS -E Rx-elec ) (3)
where:

k optimal : Optimal number of cluster. N s : Number of nodes distributed in the sensing area.

ε f s : Energy of amplifier in free space computed for n=2.

A : MxM sensing area.

ε mp : Energy of amplifier in multi-path fading. d toBS : Average distance between nodes and BS. n : Average PL exponent of the network.

Since CBSNs are sizeable networks and nodes in CBSN are randomly distributed, nodes' density can be high in some parts of the sensing area. In this case, the number of nodes joining a cluster can be very large, which would quickly drain the CH energy. Therefore to reduce the energy consumption in the network, the BS distributes nodes evenly among the K opt clusters. It limits the number of nodes in every cluster to N c obtained through dividing the total number of nodes (N s ) by the optimal number of clusters (K opt ). Every N c nodes will be therefore grouped in one cluster having one CH. Also, in order to reduce the computation overhead, re-cluster formation only occurs when nodes move outside their assigned cluster. Re-clustering computation is therefore avoided as long as the nodes remain in their assigned clusters even when they are in motion.

Cluster Head Election

To guarantee routing efficiency, it is essential to elect the appropriate CH of every cluster. In the proposed scheme, the CH is elected based on the following parameters:

• Distance between the nodes and the BS;

• Energy of nodes;

• Mobility of nodes;

• Transmission Scope (TS);

where TS of every node is defined as:

T S nodex = 1 PL exponent of node x . (4)
TS reflects the connectivity and coverage strength of a node. It is computed as the reverse of the PL exponent of every node since the PL parameter encloses all the types of losses in the network: free-space loss, reflection, absorption, refraction, and diffraction losses. It also depends on the environment type (indoor or outdoor, urban or rural, etc.) and the medium of propagation (dry or humid air), along with the distance from the node to the BS.

Since nodes are mobile, the TS value of nodes is not fix. It is dynamic and changes depending on the current location of every node. Equation (4) suggests that higher TS value is achieved for lower PL exponent based on the node's location.

For every node, the Selection Score (SS) of becoming CH is computed using the following formula:

SS x = E x • T S x d toBS • M x , (5)
where:

SS x : Selection Score of node x to become a CH. E x : Residual energy of node x. T S x : Transmission Scope of node x as per Equation (4). d toBS : Distance from the transmitting node to the BS. M x : Mobility factor of node x.

The mobility factor of a node is computed based on the relative direction of node mobility. In general, mobility is either considered positive or negative. Positive mobility implies that nodes are moving closer to each other, which decreases the total energy consumption of the network, whereas negative mobility indicates that nodes are moving away from each other, which increases the total energy consumption. In every round, node i in a cluster evaluates the distance to every node in the same cluster. If the difference of distance between the current round and the previous round is negative, then nodes are moving away from each other, otherwise they are either moving closer or are stationary relative to each other. The mobility factor of node i will be then computed as [START_REF] Kumar | An adaptive cluster based routing scheme for mobile wireless sensor networks[END_REF]:

M i (t) =
Nb. of nodes moving away from i N c (6)

Where N c represents the number of nodes in a cluster. Equation ( 6) is therefore a measurement of negative mobility. For instance, if a node moves away for the rest of the nodes in the cluster, the corresponding mobility factor increases, and if it moves closer or remains stationary with respect to the other nodes, then its mobility factor decreases. Nodes with low mobility factor should therefore be selected as CHs since they lead to low energy consumption.

Therefore, and as per Equation ( 5), in every cluster, the node with the highest energy and the TS, along with the lowest mobility factor and the shortest distance to the BS, will have the highest Selection Score (SS), will be therefore elected as CH.

Routing Operation

The routing operation encloses both intra-and intercluster routing. Intra-cluster routing refers to the process of transmitting data inside every cluster, i.e., the way to transmit data from the nodes belonging to a cluster to the elected CH. And inter-cluster routing is the process of delivering data to the final destination (the BS) from the different CHs in the network.

In the proposed algorithm, multi-hop flat model is used for both intra-and inter-cluster routing since it increases energy efficiency compared to direct routing models [START_REF] Boudargham | Efcient cluster-based routing algorithm for body sensor networks[END_REF]. In intra-cluster routing, a Cost Function (CF) of every node inside a cluster is computed as: Equation ( 7) implies that the node that is closest to the cluster elected CH, and possessing the highest residual energy and TS, is selected as a forwarder, and neighboring nodes send their data to this elected node. The CF computation aims therefore to optimize the routing operation by considering the dynamic environment and restricted resources in CBSN in the section of the forwarder.

CF x = d toCH E x • T S x (7)
Likewise, for inter-cluster routing, the CF of every CH is evaluated, and the CH with the lowest CF is chosen as the forwarder of data to the BS:

CF CH = d toBS E CH • T S CH (8)
The flow chart and the illustration of the proposed algorithm are presented in Fig. 1 and Fig. 2 respectively. To assess the performance of the proposed algorithm, simulations of the delay, the energy consumption, and the percentage of dropped packets were performed using MATLAB R2014b. The suggested scheme is compared to four algorithms:

1. The LEACH protocol [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF].

LEACH is chosen since it is one of the most famous cluster based routing schemes, and was implemented for many types of networks like BSN, WSN, and mobile networks.

2. The Improved LEACH [START_REF] Zhang | Research on the wban structure based on leach protocol[END_REF]. This algorithm is chosen since it is a recent scheme used in BSN.

3. LEACH-TLCH [START_REF] Fu | An energy balanced algorithm of leach protocol in wsn[END_REF]. This algorithm is chosen for being recent and widely used in mobile networks.

4. Multi-hop Cluster Routing [START_REF] Arioua | Multi-hop cluster based routing approach for wireless sensor networks[END_REF]. This algorithm is chosen since it is a recent algorithm using multi-hop intra-cluster routing.

Simulation parameters are summarized in Table 1. ε f s represents the energy consumption of the transmit amplifier in free space. It is obtained by computing ε mp in Equation (1) for n=2 and by using the actual power consumption of the Nordic transceiver as found in the datasheet [START_REF] Semiconductor | Single chip 2.4ghz transceiver product specifications[END_REF]. As explained earlier, the number of nodes inside every cluster is obtained by finding the ratio of the total number of nodes (N s ) to the optimal number of clusters (K opt ). For instance, if K opt is found to be 5, then every cluster will be formed of 10 nodes for 50 total number of nodes.

In order to make simulations closest to reality, the value of the PL exponent used to compute the TS of every node is variable, depending of the node's location. It ranges between 1.4 and 6 for indoor sites as per Table 2 [START_REF] Perez-Vega | A simple and efficient model for indoor path-loss prediction[END_REF].

Results and Discussion

To assess the performance of the proposed scheme, the total delay induced by the proposed algorithm, LEACH, Improved LEACH, LEACH-TLCH and Multi-hop clustering is presented in Fig. 3. Results show that LEACH induces the highest delay among the other protocols, since it elects CHs randomly without accounting for important parameters that guarantee correct CH election. Also LEACH use direct intra-and inter-cluster transmission of data which would induce higher delays due to transmission of packets over longer distances and through many obstacles. Improved LEACH performs better than LEACH since it considers the residual energy of nodes to elect CHs. However, but it underperforms other protocols since it doesn't consider other important criteria and follows direct intra-and intercluster routing operation. Multi-hop Clustering protocol induces lower delays than LEACH and Improved LEACH since it adopts intra-cluster multi-hop routing; however it underperforms LEACH-TLCH and the proposed scheme since it elects CHs by random rotation which might lead to incorrect CHs selection. LEACH-TLCH outperforms the other protocols since it considers both the distance to the BS and the residual energy of nodes in the routing process and follows two-hop intra-cluster routing operation; however, this protocol induces higher delay than the proposed scheme since it doesn't account for the medium condition surrounding the nodes, nor their mobility in the CH election. Also, the algorithm chooses the secondary CH based on its residual energy only, ignoring other important parameters like distance to CH and transmission scope, which increases the transmission delay. The proposed algorithm outperforms all the other schemes since it works on minimizing the network delay throughout the three steps of the routing process: It divides the the network into optimal number of clusters which would decrease communication overheads, leading to less delay. It also ensures the election of appropriate CHs through taking into account the mobility and the transmission scope of the nodes, in addition to the node's energy and the distance to the BS. This is in addition to adopting multihop intra-and inter-cluster routing and choosing the appropriate forwarder based on nodes distance, residual energy and transmission scope. This guarantees reliable transmission of data and therefore reduces the delay induced by re-transmission of packets or transmission of data through long paths. Fig. 4 and Fig. 5 illustrate the energy consumed by the nodes in different rounds and the total percentage of dropped packets for the five compared schemes. Both figures show that the proposed scheme performs better than the other algorithms. For instance, the LEACH protocol consumes the highest energy since CHs are elected randomly, thus much more energy is needed to transmit data to the BS. Also, large size clusters can be formed in LEACH, which will quickly drain the energy of the CH and increase the total energy consumption of the network, and will lead to high dropped packets percentage as shown in Fig. 5. Improved LEACH performs better than LEACH protocol, since it accounts for the energy of nodes in the CH election, which would better distribute the energy consumption between nodes and lead to lower packet drop percentage. As for Multi-hop Clustering scheme, it consumes less energy than LEACH and Improved LEACH due to its multihop inta-cluster routing operation that will guarantee transmission of data through shorter paths. LEACH-TLCH performs better than the above protocols since it considers both the energy of nodes and the dis-tance to the base station in the selection of the CHs, and adopts two-hop intra-cluster routing, which decreases the network overall energy consumption leading to less percentage of dropped packets. The proposed scheme outperforms all the compared scheme in terms of energy and packet drop rate since it works on saving energy throughout the cluster formation, CH election, and routing operation. Dividing the network into optimal number of clusters leads to minimum energy consumption, and limiting the number of nodes within clusters avoids the formation of large clusters that will quickly drain the energy of CHs; electing appropriate CHs fairly distribute the energy between nodes, and following muti-hop routing operation within every cluster and between clusters ensures reliable transmission of data to the BS, minimizing therefore the re-transmission of packets which will further decrease the network's energy consumption and packets' drop rate.

The obtained results prove therefore that the proposed algorithm succeeds in providing efficient routing and reliable transmission in CBSN.

Conclusion and Future Work

In this paper, a new robust and efficient cluster based routing algorithm is proposed to guarantee fast transmission of data while maintaining high energy efficiency. The proposed scheme works on increasing the delay and energy efficiency through the three routing phases: cluster formation, CH election and routing operation. The suggested protocol was compared to many other existing schemes. Results showed that it induces less delay and energy consumption than the other algorithms and leads to fewer packets drop, and thus succeeds in helping CBSNs to face many challenges such as mobility, limited resources, and coverage range. Future work includes testing the performance of multi-level cluster based scheme rather than flat model in inter-cluster routing for large number of nodes, as well as testing the proposed scheme under different scenarios such as underwater and hostile environments.

Figure 1 :

 1 Figure 1: Proposed Algorithm Flow Chart

Figure

  Figure 2: Proposed Algorithm Illustration

Figure 3 :

 3 Figure 3: Delay Performance of Different Routing Schemes

Table 1 :

 1 Simulation Parameters

	Simulation Parameter	Value
	Area	Indoor 400 m 2
	Number of Nodes (N s )	50
	Nodes Status	Mobile
	E T x-elec	16.7 nJ/bit
	E Rx-elec	36.1 nJ/bit
	ε amp	1.97 nJ/bit
	ε f s	10.9 nJ/bit
	PL Exponent	1.4 -6
	Average PL Exponent (n)	3.5
	Packet Size	4000 bits
	Clusters Density N c	N s / K opt
	Mobility Model	Random Way Point

Table 2 :

 2 PL Exponent Values

ACKNOWLEDGEMENTS

This work has been supported by the EIPHI Graduate School (contract "ANR-17-EURE-0002"), and by the Lebanese University Research Program (Number: 4/6132).


Hakim Mabed
email: hmabed@femto-st.fr

Enhanced Spread in Time On-Off Keying Technique for Dense Terahertz Nanonetworks

Nanotechnology becomes reality paving the way for many new applications. In nanonetwork system, each nanosized device is equipped with limited capabilities and is dedicated to a basic task but the combination of the numerous devices actions results in high-level functions. In this context, large number of devices concentrated in a limited area must exchange data using wireless links. Spread in Time On-Off Keying (TS-OOK) protocol was proposed as a technique to share the radio channel over the different terahertz nano-devices. TS-OOK is based on a Femtosecond-Long pulse modulation where communication data are sent using a sequence of pulses interleaved by a constant duration randomly selected. In this paper we provide a critical analysis of the TS-OOK approach. We prove that the TS-OOK is not adaptive against the traffic load variation and induces an imbalance between the active nodes. This inequity is due to the dependency of a communication quality on the randomly chosen symbol rate. We propose a dynamic TS-OOK modulation approach, called SRH-TSOOK (Symbol rate Hopping TSOOK), where the duration between two consecutive pulses of the same transmission follows a pseudo-random sequence. We show that this approach performs better than the standard protocol when the number of active nodes increases and guarantees a better distribution of the channel capacity over the active communications. For instance, while the throughput of a communication within a TS-OOK protocol may falls bellow 10 5 f rames/s with 300 active nodes, the throughput in the SRH-TSOOK protocol stabilizes around 20 7 f rames/s for all the active communications. The comparison is made on the basis of probabilistic analysis allowing a numerical and accurate evaluation of the protocols performance.

I. INTRODUCTION

Nanotechnology is moving forward in many domains. The objective is the fabrication of nano-size devices dedicated to a specific basic task such as identification [START_REF] Pathak | Multi-scale Modeling and Analysis of Nano-RFID Systems on HPC Setup[END_REF], computing [START_REF] Bounouar | Towards nano-computing blocks using room temperature double-gate single electron transistors[END_REF], sensing [START_REF] Sung | Performance of Wireless Nano-Sensor Networks with Energy Harvesting[END_REF]. One of the promising applications is the programmable material [START_REF] Boillot | Using Nano-wireless Communications in Micro-Robots Applications[END_REF], where a set of nano-scale robots change their positions in order to reach a given desired shape. To represent the physical aspect of a complex object, the nano-robots should be close enough to mask the empty spaces. Therefore a high number of nano-devices could be concentrated in the same area. In programmable material application, the size of robot is less than a cubic millimeter and the built objects can include billion of robots located in an area of 1m 3 . A further application is the Wireless nano sensor network [START_REF] Akyildiz | Electromagnetic wireless nanosensor networks[END_REF]. In this case, nano devices, which may be chemical particles, sense the local area and collaborate in order to provide accurate measurement of the environment.

In such systems, the main challenge is to conceive highly distributed and effective applications allowing the collaboration of numerous nodes. In other words, the question is to improve the communication procedures and allow faster data exchange between distant nodes without need for a physical contact. Therefore the use of wireless communications technology appears as a suitable solution. However, the use of traditional frequency bands is not convenient since the radio antenna size should be at the same scale as the used wavelength. Graphene based-antenna [START_REF] Qin | A tunable THz dipole antenna based on graphene[END_REF] enable the exploitation of Terahertz band [START_REF] Ilchenko | Tranceiver for digital radiorelay system in terahertz frequency band[END_REF] while accommodating the miniaturization requirements.

In [START_REF] Jornet | Femtosecond-long Pulse-based Modulation for Terahertz Band Communication in Nanonetworks[END_REF], Jornet and Akyldiz proposed a femtosecond pulse based modulation technique for Terahertz communications called TS-OOK. In TS-OOK, radio channel corresponds to a sequence of time windows during which a symbol (0/1) is transmitted using an electromagnetic pulse of a duration T p=100 femtoseconds. The time duration between two consecutive symbols, β, of the same communication is negotiated (randomly chosen) during the communication establishment between the two nodes [START_REF] Jornet | PHLAME: A Physical Layer Aware MAC Protocol for Electromagnetic Nanonetworks in the Terahertz Band[END_REF] and remains constant during all data transmission session. This proposition is similar to MAC protocol in Ultra Wide Band (UWB) technology [START_REF] Zin | A Review of UWB MAC Protocols[END_REF]. Except that the electrical pulse in UWB is larger with picosecond range and the covering range is about 10 meters against 1 meter for Terahertz nanonetworks. To reduce the collision probability between communications, two solutions was proposed [START_REF] Jornet | PHLAME: A Physical Layer Aware MAC Protocol for Electromagnetic Nanonetworks in the Terahertz Band[END_REF]. First, only 1-symbol is coded by a pulse while 0-symbol is represented by a silence.

Therefore the interfering impact of every communication is theoretically divided by 2. This advantage is better explored in [START_REF] Jornet | Low-weight Channel Codes for Error Prevention in Electromagnetic Nanonetworks in the Terahertz Band[END_REF] using a re-encoding procedure where the transmitted symbols are more likely 0 than 1. Secondly, the symbol rate, β, of a given communication is selected among a list of coprime numbers for example: 1001, 1002, 1003, 1007, etc. Therefore if a collision occurs at a receiver (see Fig. 1), the future collision between the same nodes could not occurs before a period of β 1 ×β 2 , where β 1 and β 2 are respectively the symbol rate of transmitter and jammer node.

The remaining paper is organized as follow. In section 2, we give a critical analysis of TS-OOK protocol where we underline its major disadvantages. Then in section 3, we present our Symbol Rate Hopping TSOOK approach. In section 4, we compare the standard and proposed approaches using probabilistic modeling of Bit Error Rate, Frame Error Rate and the MAC throughput of a given communication. In the last section, we conclude this work and give the major perspectives.

II. CRITICAL ANALYSIS OF TS-OOK

In TS-OOK, a communication, i, is carried by pulses (or silences for 0-symbol transmission) interleaved by a regular period. Let T s i the inter-symbol duration of the communication i and T p the pulse duration (100 femtoseconds). Before data exchange, the transmitter sends a communication request to the destination(s) using a control channel known by its constant inter-symbol duration T s 0 . In the communication request, the transmitter announces the value of T s i that will be used. Each received pulse allows to the receiver to synchronize with the transmitter to take into account changes on the communication parameters (distance, air composition, etc). The symbol rate β i of the communication i is determined by the ratio T s i /T p. The symbol rate is selected among a list of coprime numbers belonging to the interval [β min , β max ]. β min and β max represent respectively the upper and the lower data rate tolerated by the protocol. To best of our knowledge, the number of coprime numbers belonging to a given interval cannot be computed by numerical formulation. In fig. 2, we depict the evolution of the number of coprime values according to the evolution of the [β min , β max ] range.

The distributed approach of the TS-OOK protocol, leads to select the symbol rate randomly during the communication establishment in order to spread the co-channel risks over the active nodes. However, a high symbol rate may be selected inducing a low throughput even though the radio channel is free.

A. co-channel probability

According to TS-OOK mode, the probability that two active nodes T (transmitter) and I (jammer) be synchronized in reception at R (receptor) node is equal to the probability that: Where t T and d T (resp. t I and d I ) are the beginning time and the path duration (between the sender and R) of T signal (resp. I signal). Figures 1 shows an example of the reception of two communications originating from two source nodes. The second condition refers to the probability that the interfering pulse overloads the transmitter pulse.

Therefore the probability that the transmitter and jammer pulses be received systematically at the same time by a receiver (co-channel interference) is equal to:

(1)

P [T ,I co-channel at R] = 1 nbcoprime × 1 β
In equation ( 1

B. Bit Error Rate in TS-OOK

TS-OOK allows to adjust the system to the application requirements by setting the range of [β min , β max ] interval. However, increasing the interval range obviously increases the number of coprime values but increases also the disparity of the symbol rate between communications using a value of β ≈ β min and those with β ≈ β max . Communications using low symbol rate benefit of a better data rate than those using high symbol rate. In the other side, it is expected that when the number of interfering nodes increases, communications with lower symbol rate are more subject to collisions.

Indeed with a density of 1 node by 1mm 2 , the system may reach a population of 10 6 nodes in 1m 2 that largely exceeds the thousand of available symbol rates. The fact that nodes are not all active at the same time offers a protection against co-channel collisions between pair of communications, but the increase of active nodes number increase the observed BER.

Moreover, when nodes are located in a 3D area (programmable material case for instance), the number of nodes concentrated in a limited area increases exponentially and hence amplifies the collision probability.

Let R the reference node that listens to the communication transmitted by the node T and let N the number of surrounding nodes (nodes which signal can be received by R). Let nbcoprime the number of available coprime values. We assume that communications arrivals follow a Poisson distribution of parameter λ (corresponding to the average number of new communications in a second) and we assume that the communication duration follows an exponential distribution with a mean 1 µ . The conjunction of the two distributions (arrivals and communication durations) makes that the number of active nodes follows a Poisson distribution with a parameter θ = λ × µ. The Poisson distribution represents a good model [START_REF] Huo | Generalized Erlang-B formula for mobile and wireless radio channels[END_REF], [START_REF] Logothetis | Teletraffic models beyond Erlang[END_REF], [START_REF] Kim | Multiple Access Performance of M-ary Orthogonal Balanced UWB Transmitted-Reference Systems[END_REF] for arrival phenomena when the number of communication sources (nodes) is high enough, which is the case for the studied scenarios (the number N ). Indeed, the higher the number of communication sources is, more relevant the assumption about the inter-dependence of communications arrivals is. However the assumption concerning the communication duration neglects the effect of the symbol rate selection and the interference impact on the communication. The interference aspect can however be ignored by considering not reliable communications where the lost frames are not retransmitted and by assuming a fix error code mechanism.

The probability that the number of active nodes around the node R be equal to k is expressed by the following formula:

(2)

P [k active nodes] = θ k k! × [ ∞ ∑ i=1 θ i i! ] -1 = θ k k! × e (-θ)
When the listened communication uses the symbol rate β, the probability that a received symbol by R be in collision with a symbol transmitted by another active communication, I, is equal to 1 β . With p1 the probability that transmitted symbol be 1 (a pulse and not a silence), the probability that a symbol of the listened communication be interfered by a pulse of the communication I is expressed by:

(3)

P [I interferes with T ] = p1 β
The probability p1 could be less than 0.5 if Low-weight Channel coding [START_REF] Jornet | Low-weight Channel Codes for Error Prevention in Electromagnetic Nanonetworks in the Terahertz Band[END_REF] is used. We assume that the receptor uses the correlation-based energy detector extending the reception window to 2 × T p . We conclude that:

(4) P [I interferes with T ] = 2 × p1 β
In the following we consider that p1 = 0.5.

The joint action of the random selection of the symbol rates among coprime values and the randomness of communications arrivals leads to a uniform distribution in time of the interfering pulses. In the following, we assume that every concurrent communication is a potential jamming signal, which means that the signal powers are ignored. Therefore, the probability that a symbol of the listened communication be interfered by a communication transmitted by one of the k active nodes can be expressed by:

(5)

P [∃I interferes T /k active nodes] = k ∑ i=0 ( β -1 β ) i × 1 β
The probability that a received symbol by R be interfered by at least another communication (whatever is the number of active nodes) is equal to:

BER = ∞ ∑ k=1 P [∃I interferes T /k active nodes] × P [k active nodes] (6)
Which gives the BER of a given communication:

(7) BER = ∞ ∑ k=1 k ∑ i=0 ( β -1 β ) i × 1 β × θ k k! × e (-θ)
The observation of the BER formula reveals two main points. First the BER is closely linked to the symbol rate used by the communication. When the β is low, the value of the BER increases. We deduce that low β provides a better symbol throughput but increases the data loss when the number of active nodes augments. Secondly, the random selection of the symbol rate produces an unequal treatment between the different communications. In addition, the use of high symbol rate when the radio channel is free (low number of active nodes) is not relevant. In the next section we propose an enhanced TS-OOK protocol allowing to overcome these drawbacks.

III. SYMBOL RATE HOPPING TS-OOK

To address the disadvantages of TS-OOK protocol we were inspired by the frequency hopping technique used in FD-TDMA networks [START_REF] Stuckmann | The GSM Evolution: Mobile Packet Data Services[END_REF]. In Slow Frequency Hopping technique, the interference are repartitioned using a pseudo-random sequence. Every transmitter hops over the different available frequencies using pseudo-random sequences [START_REF] Verhulst | Slow frequency hopping multiple access for digital cellular radiotelephone[END_REF], [START_REF] Chiani | Up-link analytical outage evaluation for slow frequency hopping mobile radio systems[END_REF]. In place of hopping over different frequencies as in FD-TDMA technology, in our SRH-TSOOK protocol, transmitters hop over different symbol rates using a pseudo-random sequence known by both the transmitter and the receiver. The random sequence guarantees that the different symbol rates are used uniformly. Consequently, all active communications has the same transmission conditions expressed by the same average of BER and data rate. The Symbol Rate hopping aims to repartee the observed interferences over the concurrent communications. The operation mode of the Symbol Rate hopping TS-OOK method is depicted in Fig. 3.

The idea is to change the symbol rate of a communication after a regular number of symbols corresponding to the transmission of a MAC frame. The repartition of the interference depends on the shortness of this delay. The use of symbol rate hopping eliminates the effect of coprime values on reducing

1 Frame i 1 0 1 1 1 1 1 1 1' 1' Frame i+1 1 0 1 2 0 1 1 1 2 2' 1 2 0 0 1 1 1 2' 2' 2' 2' 2'
Frame j+1 Frame j Transmitter Jammer Fig. 3. Symbol Rate Hopping: after each frame, a new symbol rate β is generated and used to transmit the next frame.

the pair-nodes interferences. However, this feature is relatively less important than the reduction of the interference sum.

Many random generators exist in literature [START_REF] Blum | A Simple Unpredictable Pseudo-Random Number Generator[END_REF], [START_REF] Impagliazzo | Pseudo-random Generation from One-way Functions[END_REF] that can mainly expressed as a recursive function RN D:

(8) r current = RN D(r current )
r current represents the current random value. The selection of the RN D function should take into account the power limitation of the nano/micro-machines. A solution such as Linear Congruential Generator [START_REF] Ecuyer | Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure[END_REF] could be then considered.

During the communication establishment, the transmitter and the receiver agree on the initial r current value called seed using the control channel (T s 0 ). The sequence of numbers r current is then computed without exchange between receiver and transmitter based on the deterministic function RN D. After each exchanged MAC frame, the transmitter and the receiver use the new r current (eq. 8) to calculate the next symbol rate as follow:

(9) β = r current × (β max -β min ) RN DM AX + β min
RNDMAX represents the highest value returned by the RND function.

IV. PERFORMANCE ANALYSIS OF SRH-TSOOK

Now, we start studying the contribution of the SRH-TSOOK on the performance of the nano-networks. The co-channel probability, BER, FER and data throughput are taken as metrics to compare the standard and the proposed MAC protocols.

A. co-channel interference in SRH-TSOOK

Co-channel interference occurs when two communications are systematically in collision, which means that pulses sent by T to R always arrive at the same time that the interfering pulses sent by I. In SRH-TSOOK, co-channel probability is equal to the probability that the two communications use the same seed (the initial r c urrent) of the pseudorandom sequence. Since the seed is selected in the interval [O, RN DM AX], the co-channel interference is equal to 1/RN DM AX. With RN DM AX = 2 32 , the co-channel interference probability is then well below the co-channel probability in standard TS-OOK protocol given in equation 1.

B. BER in SRH-TSOOK

Since every communication uses sequentially the different available symbol rates in random way, the BER of a communication is equal to the average BER obtained using each symbol rate; which corresponds to the following expression: [START_REF] Zin | A Review of UWB MAC Protocols[END_REF] In Fig. 4, we present the communication BER according to the average number of active nodes. We compare the estimated BER of 6 communications using different constant symbol rates with the estimated BER of a communication using SRH-TSOOK protocol. We remind that the quality of a given communication in the standard TS-OOK protocol varies according to the selected symbol rate while this quality is smoothed over all the communications in the SRH-TSOOK approach. Figure shows that SRH-TSOOK allows to bring the BER to average values for all communications while the BER reaches high values in standard TS-OOK for communications using a low symbol rate (β = 1000). For instance, under 900 concurrent communications, a communication with symbol rate equal to 1000 suffers from a BER that exceeds the 60%, while the BER is less than 30% when the Symbol Rate Hoping is used for all communications. By contrast, in standard TS-OOK, communication that uses the symbol rate 5000 has a better BER (less than 10% with a number of active nodes bellow 600). However by using a high symbol rate, we expect that the data rate of such communication will be low. SRH-TSOOK allows to obtain better data rate without extremely increases the BER value. Comparison between the BER obtained by TS-OOK protocol for 6 communications using different fixed symbol rate (1000,1500,2000,3000,4000,5000) with the BER obtained by SRH-TSOOK protocol for any communication.

BER = ∑ βmax β=βmin ∑ ∞ k=1 ∑ k i=0 ( β-1 β ) i × 1 β × θ k k! × e (-θ) β max -β min

C. FER in SRH-TSOOK

The precedent section gives the BER of a communication using the SRH-TSOOK protocol. However, to better evaluate the quality of a communication the transmission error should be estimated in higher level to take into account detection and correction error codes [START_REF] Franceschini | LDPC Coded Modulation[END_REF]. Let evaluate now the error rate at MAC frame level. Let n the number of bits composing a MAC frame (data + detection/correction Error code). We assume that the used error code offers a capability [START_REF] Chilappagari | Guaranteed Error Correction Capability of Codes on Graphs[END_REF] of m, which means that the error code is able to fix the received frame if the number of corrupted bits does not exceed m. The number of corrupted bits (number of collided bits) in a MAC frame of size n follows a Binomial distribution with a parameter BER (equation 7 or 10 according to used symbol rate allocation). Consequently, the probability that the number of corrupted bits be equal to x is:

(11) P [x corrupted bits] = C x n × BER x × (1 -BER) n-x
The probability that the number of corrupted bits be higher or equal to m is:

(12) P [corrupted bits ≥ m] = n ∑ x=m C x n × (BER) x × (1 -BER) n-x
Where C x n = n! /k! ×(n -k)! corresponds to the Binomial coefficient. Since the error code capability is limited to m errors, we deduce that the Frame Error Rate is equal to:

(13) F ER = n ∑ x=m C x n × (BER) x × (1 -BER) n-x
Fig. 5 represents the FER variation of a given communication according to the number of concurrent nodes and to the used symbol rate. The used MAC frame size is of 128 bits and m is 20. The figure shows that SRH-TSOOK method allows a more progressive evolution of the FER contrary to TS-OOK protocol where the FER suddenly increases with the evolution of the number of active nodes. For instance, when the symbol rate is equal to 1000, the FER increases from 0% to 80% by varying the number of active nodes between 100 and 200. Whereas the FER evolution does not exceed 10% with SRH-TSOOK when the number of active nodes varies from 100 to 200. In the other side, while the standard TS-OOK presents certain communications with low FER (β = 5000) and other with high FER (β = 1000), SRH-TSOOK presents the same average FER for all the active communications.

D. Data rate in SRH-TSOOK

To estimate the impact of FER on the communication throughput (a lost frame is a retransmitted frame), we assume for simplification that frame acknowledgments are without errors and does not induce delay. The average number of frame retransmissions is equal to 1/(1 -F ER) times, where FER is determined using the equation 13.

The frame transmission duration is equal to n × β × T p. Where n is the frame size (in bits), β is the symbol rate of the studied communication and T p is the pulse duration. In case of SRH-TSOOK the β value changes after each frame transmission. In case of standard TS-OOK, the data throughput of a given communication is equal to: Comparison between the FER obtained by TS-OOK protocol for 6 communications using respectively a symbol rate (1000,1500,2000,3000,4000,5000) with the FER obtained by SRH-TSOOK method for any communication.

In case of SRH-TSOOK, the throughput is expressed as an average over available symbol rates. ( 15)

T hroughput = ∑ βmax β=βmin (1 -F ER)/(n × β × T p) (β max -β min )
Frames/s Fig. 6 allows to observe the evolution of throughput according the number of active nodes and used symbol rate. We observe clearly that SRH-TSOOK provides compromise between low and high symbol rate with a relatively good performances under low number and high number of concurrent communications. Contrary, TS-OOK presents an imbalance of the performance between communications using low symbol rate and those using high symbol rate. Whereas communications with low symbol rate perform well under weak load and give bad result under high load, communications with high symbol rate achieve the contrary. The imbalance that characterizes the standard TS-OOK makes that some communications are more subject to interference and therefore to data retransmission, which leads to a disproportion of energy consumption. Our proposed RSH-TSOOK mechanism guarantees the equal radio access conditions to all communications.

In Fig. 7, we give the comparison between the estimated Throughput of any communications using the RSH-TSOOK protocol and the worst throughput provided by the standard TS-OOK (when a random communication uses the worst symbol rate according to Fig. 6). The figure shows that standard TS-OOK performs badly when the traffic load increases while RSH-TSOOK displays a linear decrease according to traffic load. In addition when the traffic load is low, the randomness of symbol rate selection in standard TS-OOK protocol involves communications that do not benefit from the radio channel availability.

V. CONCLUSION AND PERSPECTIVES

In this paper we studied the Medium Access Control protocol in Terahertz based nanonetworks. We provided a critical Comparison between the throughput obtained by TS-OOK protocol for 6 communications using respectively a symbol rate (1000,1500,2000,3000,4000,5000) with the throughput of any communication in SRH-TSOOK protocol. and original analysis of Spread in Time On-Off Keying (TS-OOK) technique. This analysis shows that standard TS-OOK suffers of two major drawbacks. First, the random selection of the symbol rate induces imbalance in communications throughput between communication using the high symbol rate and those using low symbol rate. Secondly, the TS-OOK presents a lack of flexibility and adaptability against traffic load. We proposed a Symbol Rate Hopping TS-OOK technique allowing to overcome these drawbacks. SRH-TSOOK is inspired by the Slow Frequency Hopping technique used in FD-TDMA radio networks. The idea is to change regularly the symbol rate used by the communication in a pseudo-random way. This approach allows to spread the generated interference over the different communications and gives the same radio access conditions to all concurrent communications. The probabilistic analysis made in the paper proves the relevance of proposed techniques in terms of BER, FER and Throughput gain. In addition, the probabilistic analysis allows to clearly identify the impact of each parameter on the system behavior and allows to deal with big scenarios contrary to simulation analysis.

Some aspects of this analysis should be in-depth by introducing the signal powers. Indeed, in this paper we only studied the collision probability between sent pulses assuming that nodes are close enough to consider that collision induces certainly a symbol loss. However the interference depends also on the ratio between listened and interfering signals.

In addition, the flexibility of the SRH-TSOOK technique should be improved by adjusting the [β min , β max ] interval according to observed traffic load in the network. Therefore, when a low traffic is detected, communications can hop only on low symbol rate values to increase the throughput.

Fig. 1 .

 1 Fig. 1. TS-OOK modulation: β 1 and β 2 correspond to the inter-symbol period for the transmitter and the jammer nodes. The useful and jamming signals are received with a delay depending on the distance between the nodes.

•Fig. 2 .

 2 Fig. 2. Evolution of the number of corpime values according to βmax. β min = 1000

  ), nbcoprime represents the number of coprime values available in the interval [β min , β max ]. For instance with [β min , β max ] = [1000, 5000] and Transmitter symbol rate β = 2089, co-channel probability is equal to 1 511 × 1 2089 = 9.36 × 10 -7 .

  Fig. 4.Comparison between the BER obtained by TS-OOK protocol for 6 communications using different fixed symbol rate (1000,1500,2000,3000,4000,5000) with the BER obtained by SRH-TSOOK protocol for any communication.

( 14 )

 14 Fig. 5.Comparison between the FER obtained by TS-OOK protocol for 6 communications using respectively a symbol rate (1000,1500,2000,3000,4000,5000) with the FER obtained by SRH-TSOOK method for any communication.

  Fig.6.Comparison between the throughput obtained by TS-OOK protocol for 6 communications using respectively a symbol rate (1000,1500,2000,3000,4000,5000) with the throughput of any communication in SRH-TSOOK protocol.

Fig. 7 .

 7 Fig. 7. Comparison between the lowest throughput obtained by a communication using standard TS-OOK with the throughput of any communication obtained using SRH-TSOOK method.


Karla Breschi

Julien Bernard
email: julien.bernard@femto-st.fr

Construction of a Minimum Energy Broadcast Backbone with Bounded Delay in Heterogeneous Wireless Sensor Networks

Efficient broadcast in wireless sensor networks can exploit backbone structures, in relation to connected dominating sets in graphs. This paper proposes the construction of a backbone for broadcast in heterogeneous wireless sensor networks having minimum energy consumption and a delay bounded by a predefined constant hmax. For the purpose of the paper, we assume the sensors composing the network have an energy belonging to [Wmin; Wmax] such that Wmax = c * Wmin where c is a predefined constant. To address this problem we propose two different approaches. For small instances, we propose an integer linear program that computes an optimal solution for the problem. Since solving an integer linear program is NP-hard, obtaining solutions for large network instances may be impossible in a reasonable time, thus we propose an approximation algorithm that computes a solution for the problem in polynomial time and whose approximation ratio is c * hmax.

I. INTRODUCTION

A wireless sensor network is a set of sensors deployed in a more or less random manner forming a multi-hop network. The objective of such networks is to collect information from the environment, such as temperature, and to route them to a particular node named sink. A sensor is an embedded system characterized by an energy constraint due to the fact that they are battery powered. Often the sensors are placed in hostile areas difficult to access for a human, therefore saving energy is a primary problem. Wireless sensor networks are used in many fields such as aeronautics, automotive and medical surveillance.

Broadcast in wireless sensor networks is a fundamental problem that is linked to many applications. As soon as the base station needs to transmit an information to the whole network, broadcast is necessary.

The basic strategy called flooding, which consists in transmitting every received messages, consumes a large amount of energy, a critical resource for a wireless sensor network, directly influencing the network lifetime. Furthermore, flooding consumes bandwidth, increasing collisions and duplicating messages. The idea for broadcast protocols is to determine a subset of nodes, called backbone, that will transmit the messages, in order to reach all network nodes. A backbone brings many advantages: it removes unnecessary transmission links, reduces the communication overhead, reduces the redundancy and, by decreasing the energy consumption, increases network lifetime.

The backbone construction depends on the issue to be solved. In our case, the objective is to optimize two metrics at the same time: energy and delay. Energy consumption is strictly related to network lifetime whereas delay is associated with the network performance. Bounding the delay improves power consumption and reliability because fewer hops are needed to reach the targets. This also results in the reduction of transmission failures because the longer the path between the source and the destination, the higher the probability of failure.

In this paper, we propose an Integer Linear Program (ILP) to construct a minimum energy broadcast backbone with bounded delay. Since solving an ILP is NP-hard, we propose an approximation algorithm in order to solve the problem in polynomial time.

This paper is organized as follows: Section II presents the related works, Section III gives the definition of the problem treated in this paper, Section IV provides the definition of an Integer Linear Program giving an optimal solution for an energy efficient backbone with bounded delay, Section V presents an approximation algorithm solving the same problem, Section VI gives a theoretical study in order to prove the approximation ratio of the proposed algorithm and section VII summarizes the conclusions of this work.

II. RELATED WORK

The problem of determining an optimal backbone can be translated in the graph theory as determining an optimal Connected Dominating Set (CDS). The construction of a CDS has been widely studied with different approaches: linear programming, genetic algorithms or greedy algorithms. Different algorithmic models were used to represent a sensor network: for instance unit disk graphs, disk graphs or more restrictive graph classes like chordal graphs (definition will be given in the next section). According to the parameters to be optimized, several variations of CDS were proposed [START_REF] Yu | Connected dominating sets in wireless ad hoc and sensor networks-a comprehensive survey[END_REF].

We will focus on works that aim at optimizing energy and delay.

A. Backbone and bounded diameter

A number of works studying the construction of connected dominating sets with bounded diameter are available. Their goal is to minimize the diameter of the graph, i.e. the transmission delay in the context of wireless sensor networks.

Buchanan et al [START_REF] Buchanan | On connected dominating sets of restricted diameter[END_REF] introduce the notion of s-club to bound the distance traveled by the information and consequently reduce the latency. An s-club is a connected dominating set whose induced subgraph has a diameter at most s. In their paper, the authors prove that finding an s-club is a NPcomplete problem.

Schaudt [START_REF] Schaudt | On dominating sets whose induced subgraphs have a bounded diameter[END_REF] proves that for all k ≥ 1, the problem of deciding if a graph has a dominating set whose induced subgraph has a diameter at most k is NP-complete. Therefore the author decided to concentrate his efforts on a restricted class of graphs admitting a set with these particular features: chordal graphs. A graph is said to be chordal if each of its four or more cycle vertices has a chord, i.e. an edge connecting two non-adjacent vertices of the cycle. Using that specific class of graphs, he showed the problem can be solved in O(mn) time in a graph with n vertices and m edges.

Li et al [START_REF] Li | Constructing connected dominating sets with bounded diameters inwireless networks[END_REF] deal with the construction of a bounded diameter connected dominating set whose size is minimized. The authors propose an algorithm with constant approximation factor in the case of unit disk graphs and a time complexity of O(n 2 ) in a graph with n vertices. Kim et al [START_REF] Kim | Constructing minimum connected dominating sets with bounded diameters in wireless networks[END_REF] build connected dominating sets in unit disk graphs considering the following metrics: size, diameter and average hop distance. The authors propose two centralized algorithms and a distributed version for the second one. The main idea of those algorithms is to build a tree using the depth first search while seeking a maximal independent set. Finally, they connect the retained nodes in the maximal independent set.

Akbari Torkestani [START_REF] Torkestani | Energy-efficient backbone formation in wireless sensor networks[END_REF] underlines the fact that when the degree constraint decreases, the backbone delay increases. As a result, he treats the problem of the construction of a connected dominating set with minimum weight and an optimal degree in order to obtain an energy efficient backbone whose delay is bounded. For this purpose, the author develops a heuristic based on learning automata.

Krumme et al [START_REF] Krumme | Minimum eccentricity multicast trees[END_REF] present a work dealing with the construction of multicast trees with minimum eccentricity. The authors propose a polynomial time algorithm that exploits geometry properties to construct a multicast tree that allows connecting a set of sources nodes to a set of sink nodes while minimizing the hop distance between this two groups.

B. Backbone and energy

There are some works treating the construction of a backbone for routing like [START_REF] He | Greedy construction of load-balanced virtual backbones in wireless sensor networks[END_REF] and [START_REF] He | Approximation algorithms for loadbalanced virtual backbone construction in wireless sensor networks[END_REF]. In both contributions, the network is represented by an undirected graph where all the nodes have the same transmission range. The authors try to construct a load-balanced backbone by minimizing the maximum degree of the dominating nodes.

The paper [START_REF] Ben-Othman | Self-stabilizing algorithm for energy saving in wireless sensor networks[END_REF] proposes a self-stabilizing algorithm allowing to build a connected dominating set with minimal energy for the routing. To achieve this objective, the authors propose a solution based on topology control. Their algorithm reduces the transmission range of the nodes while ensuring the connectivity of the network which allows them to reduce the energy consumption.

Li et al [START_REF] Li | Energy efficient broadcast routing in static ad hoc wireless networks[END_REF] treat the construction of a broadcast tree that minimizes the total energy cost. They prove that this problem is NP-hard and propose two heuristics and one approximation algorithm. The authors model the network by a directed graph where each node has its own transmission power.

C. Comparison with our work

The above-mentioned works deal with the construction of a backbone whose energy is minimized and/or delay is limited. Most of them treat either one or the other metric and often build a backbone for routing. Only [START_REF] Torkestani | Energy-efficient backbone formation in wireless sensor networks[END_REF] focuses on both the energetic cost and delay.

Our goal is to optimize both energy consumption and delay in the case of a broadcast. We choose to model a heterogeneous wireless sensor network as a directed disk graph as this model is more generic than unit disk graphs. In particular, this model allows taking into account the asymmetrical links. In addition, to solve the problem, we will use a different method: linear programming for small program instances and an approximation algorithm in the other cases.

To build an efficient energy backbone whose delay is limited, we will use the same metric employed in [START_REF] Krumme | Minimum eccentricity multicast trees[END_REF]: the eccentricity. The difference with what we propose is that we concentrate our efforts in a more general case using directed graphs and we seek to optimize energy at the same time.

III. PROBLEM DEFINITION

A heterogeneous wireless sensor network is represented by a graph G = (V, E), where V = {0, . . . , n -1} is the set of n vertices that corresponds to wireless nodes and E ⊂ V * V is the set of edges that represents the wireless connections between nodes, i.e. a directed edge (i, j) models the fact that j is in the communication range of i. We define the neighborhood of i to be N + (i) = {j, (i, j) ∈ E}. We denote the node 0 as the base station of the wireless sensor network. V * is equal to V without the base station. The eccentricity of node 0, noted (0), is the longest of the shortest paths to every other node in terms of hop distance.

To define connectivity, we use the disk graph model (DG) [START_REF] Schmid | Algorithmic models for sensor networks[END_REF]. More precisely, if r i is the transmission range of node i, and d ij is the euclidian distance between node i and node j then j is a neighbour of i if d ij ≤ r i . This model takes into account the heterogeneity of a wireless sensor network by assigning different transmission ranges to the various nodes.

We note by W i the energy spent by node i to send data to all the nodes in his neighborhood. There is no constraint on how to calculate the energy consumption (e.g.: First order radio model [START_REF] Heinzelman | Energyefficient communication protocol for wireless microsensor networks[END_REF]).

A dominating set of graph G is a subset D of V such that every vertex not in D is in the neighborhood of a vertex in D. The nodes belonging to D are named dominators or dominating nodes and the nodes belonging to V \D are the dominated nodes or dominatees. A dominating set D of graph G is a connected dominating set (CDS) if D induces a connected subgraph of G. So computing a connected dominating set in a graph is equivalent to computing a backbone in a wireless sensor network. The aim is to reduce the energy consumption so we assign a weight to each node i which is the energy W i necessary to send a message to its neighborhood. The objective is to choose a subset of V respecting the dominance and connectivity properties and such that the sum of the selected nodes' weights is minimized. This problem is known as Minimum Weighted Connected Dominating Set (MWCDS).

In our case, we want, in addition, to bound the delay during the broadcast. As the delay is proportional to the number of hops, we compute a CDS with minimum weight and where the hop distance from the base station is bounded by a constant h max . Note that h max must be at least (0) in order to reach the node with the longest path from the base station. We call this problem Minimum Weighted Connected Dominating Set with Bounded Hop Distance (MWCDS-BHD).

IV. INTEGER LINEAR PROGRAMMING FORMULATION

In this section, we introduce a mixed integer linear program modeling the MWCDS-BHD problem. The program builds a backbone tree with minimum weight whose height is bounded by h max -1.

The formulation requires the following decision variables. First, x i , i ∈ V is a binary variable which indicates if the node i belongs to the backbone (x i = 1) or not (x i = 0). Then, in order to ensure that the set is connected, we construct a directed tree that is rooted in node 0, the base station. The nodes, belonging to the directed tree obtained by the ILP and that are not a leaf, represent the backbone nodes. Decision variable y i,j , (i, j) ∈ E tells whether edge (i, j) is in the directed tree formed by the backbone nodes. In other words, if y i,j = 1, then nodes i and j are in the backbone and node i is the father of node j in the directed tree. Finally, the decision variables u i , i ∈ V guarantee that there is no cycle in the backbone.

The objective function of the integer linear program aims to minimize the total energy cost W of the constructed backbone. Mathematically, this is written as follows: W = i∈V x i W i . The constraints are defined as follows:

∀i ∈ V * , {j|i∈N + (j)} x j ≥ 1 (1) ∀i ∈ V * , {j|i∈N + (j)} y j,i = x i (2)
∀(i, j) ∈ E, x i + x j -2y i,j ≥ 0 (3)
∀(i, j) ∈ E, (n + 1)y i,j + u i -u j + (n -1)y j,i ≤ n (4) ∀i ∈ V, u i ≤ h max (5) i∈V x i - (i,j)∈E y i,j = 1 (6)
x 0 = 1 (7)

u 0 = 1 (8)
Equation 1 ensures dominance: each node must either belong to the backbone or be adjacent to a node belonging to the backbone. Equation 2 specifies that only the backbone nodes have exactly one father in the tree. The other nodes have no father. Equation 3 asserts that when an edge belongs to the backbone, then both its ends are part of the backbone too.

Equation 4 is inspired by [START_REF] Miller | Integer programming formulation of traveling salesman problems[END_REF] where it is used to prevent cycles in the traveling salesman problem. This equation is also used in [START_REF] Fan | Solving the connected dominating set problem and power dominating set problem by integer programming[END_REF] for the same purpose on a spanning tree. It allocates a strictly positive number u i for each node in the backbone that represents its distance (plus one) from the base station in the tree. If nodes i and j are in the backbone and y i,j = 1, then it ensures that u j = u i +1. If one of the nodes i or j is not in the backbone, the difference between u i and u j is undefined (bounded by the maximum possible difference).

Equation 5 ensures that the distance in terms of hop number is bounded by h max . The variable u i represents the depth of node i in the backbone tree. So bounding the depth of each node in the backbone ensures that the height of the tree is bounded too. Equation 6stipulates that the number of backbone nodes is equal to the number of backbone edges plus one (property of trees). The last two equations (7 and 8) give the values for the base station. This integer linear program can be used to find optimal solutions. Unfortunately, the time taken to solve the problem can be quite long, even for moderated size networks due to the NP-hard nature of the problem.

V. APPROXIMATION ALGORITHM

In this section, an approximation algorithm calculating an MWCDS-BHD is proposed. The algorithm aims to calculate an energy efficient backbone and ensures that all paths are smaller than h max .

A. Principle

Given a weighted directed graph, the algorithm computes, at first, both arborescences: A 1 and A 2 . A 1 is obtained by a shortest path algorithm where the weight is a unit value for each node. Thus, paths in A 1 minimize the number of hops from the base station to any node. A 2 is constructed by a shortest path algorithm where the weight is the energy consumption W i of each node. To take into account the energy consumed by each node, we have tagged each outcoming edge of a node by its weight W i . Paths in A 2 minimize the energy consumed to reach the destination node.

The principle of the algorithm is to choose one node k and then to consider P 1 (k) and P 2 (k), respectively the path between the base station and node k in the arborescence A 1 and A 2 . As h max is at least greater than (0), the length of P 1 (k) is less than or equal to h max . Since P 2 (k) is the path minimizing the energy cost, to connect k to the base station we look at first to path P 2 (k) and if its length is less than or equal to h max , we keep it. Otherwise, we choose P 1 (k). This ensures that every path is less than or equal to h max . Therefore, the question arises as to what is the energy cost that is added when the chosen path is P 1 instead of P 2 . This is discussed in the section V-C.

To describe the algorithm, we introduce the definition of several sets of nodes. The set B is the set of nodes which are currently part of the backbone. The set U is the set of remaining nodes i.e. the nodes that are untreated yet. Initially, U is equal to V . D is the set of dominated nodes. At the beginning of each iteration, the following equation will be true:

V = B ∪ D ∪ U .

B. Bounded Backbone Algorithm (BB)

In this section, we will explain in detail the process of the proposed approximation algorithm described in Algorithm 1. As can be seen, at the beginning, the algorithm initializes the sets B, U and D. The main idea is to select iteratively a node k that is not reached by the broadcast yet. BB chooses the most distant node not covered yet in A 1 i.e. the distance is considered in terms of the number of hops. Once the appropriate node has been selected, the next step is to choose a path for reaching it between the paths P 1 (k) and P 2 (k) as described before. Afterward, the nodes belonging to the chosen path are added to the backbone and removed from the set U . Furthermore, the set of dominated nodes is updated.

At the end of each iteration, the energetic cost of nodes added to B is set to zero (setting to zero phase) and, then, since the shortest paths change following this update, the A 2 arborescence is computed again.

The processing explained above is repeated until the set U is empty. The solution is given by the set B constructed by this process.

Setting to zero the energy of the nodes added to the backbone allows us to choose paths containing nodes belonging to the backbone. Indeed, since they already belong to the backbone, they will not increase the cost of the backbone. To better explain, consider the example of figure 1.

In The backbone represented in figure 1b is less expensive in terms of energy. Indeed, the backbone consists of nodes a, c, e, f , and g and has an energetic cost of 8. At the second iteration, the zeroing of the energy of the backbone nodes allows us to consider the path P = (a, e, f, g, c, d) and to select it because its energy cost is inferior to the energy of

P = (a, b, c, d). Indeed, W a = W e = W f = W g = 0.
With this method, we obtain the backbone in figure 1b. Therefore, by setting energy costs to zero, BB selects the paths that will minimize the energy cost of the backbone.

Algorithm 1 Bounded Backbone algorithm

Input: Graph G (WSN), Maximum hop distance h max , En- ergy W max and W min Output: Backbone B B ← ∅ U ← V D ← ∅ while U = ∅ do k ← the most distant node in A 1 not covered yet if L(P 2 (k)) ≤ h max then P ← P 2 (k) else P ← P 1 (k) end if B ← B ∪ {x|x ∈ P ∧ x = k} U ← U \ {x|x ∈ P } D ← D ∪ (x∈P )∧(x =k) N + (x) for x such that x ∈ P ∧ x = k do //setting to zero phase W x ← 0 end for Compute A 2 end while return B
The time complexity of the Bounded Backbone algorithm depends on the algorithm chosen for the calculation of A 1 and A 2 : in our case, it is Dijkstra's algorithm. The Dijkstra's algorithm is used in the main loop to recompute Proof: B is a CDS if, and only if, B is a dominating set and the graph induced by B is connected. By construction, B is a connected set. Indeed, the set B is constructed by iterative addition of paths all connected to the sink.

To prove that B is dominant we will proceed by absurd. Suppose B is not dominant. This means that:

∃v ∈ V \ B, ∀u ∈ B, (u, v) / ∈ E
There are two possible cases: either v is in D or v is in U .

• Case v ∈ D. By construction of set D, we know that:

∃d ∈ B such that v ∈ N + (d) thus (d, v) ∈ E.
This is in contradiction with our hypothesis.

• Case v ∈ U . Since v ∈ U then U = ∅. This is impossible
because in this case the stopping condition of the loop is not respected. So B is dominant. Therefore B is a CDS.

Lemma 2: In the set B, the distance in terms of hop number between the base station and any other node of the graph is at most h max .

Proof: Let u be a node in V . There are two possibilities:

• u is one of the nodes k selected by BB. To link u to the base station, BB selects either path P 1 (u) or P 2 (u).

If P 1 (u) is chosen then we have: L(P 1 (u)) ≤ (0). By assumption, (0) ≤ h max so L(P 1 (u)) ≤ h max . If the chosen path is P 2 (u), then we know that L(P 2 (u)) ≤ h max otherwise it would not be chosen. • u is not one of the nodes k selected by BB. Then there are two possibilities :

u is an internal node of the path of a node k selected by BB. Suppose that u is a node internal to the path of k i . We know that L(P (k i )) ≤ h max , consequently L(P (u)) ≤ L(P (k i )) ≤ h max . u is a leaf from the resulting tree that has not been selected by the algorithm for processing. Since it was not chosen by the algorithm as a node to be processed, we can deduce that all the nodes necessary to connect it to the base station are already present in the backbone. Furthermore, u is in N + ({x|x ∈ B}).

As demonstrated previously, for any node k selected by BB, L(P (k)) ≤ h max so any node x ∈ B has a hop distance to the base station of at most h max -1. Suppose that y is the father of u. Then the hop distance of u is equal to the hop distance of y plus one. Finally, y is at h max hops from the base station.

VI. THEORETICAL STUDY OF BB

In this part, we present a theoretical study to determine the energy loss when the chosen path is P 1 instead of P 2 . For Theorem 3, we consider the case when there are two possible energies for nodes: W min and W max , with W max = c * W min .

Then we prove the approximation ratio of the BB algorithm by considering that the nodes can have an energy belonging to [W min ; W max = c * W min ].

The first theorem we want to prove is the following: Theorem 3: The path P chosen by the algorithm has a bounded cost: w(P ) ≤ c * w(P 2 ).

For this purpose, we will at first, study the structure of the P 1 path compared to the P 2 path.

1) Structure of the path P 1 with respect to P 2 : We assume that P 2 consists of u nodes with energy W min and v nodes whose energy is W max . And P 1 consists of u -∆u nodes whose energy is W min and v + ∆v nodes of W max energy.

As P 1 is the shortest hop path, we have:

u -∆u + v + ∆v ≤ u + v So we can infer: ∆v ≤ ∆u (9)
Knowing that P 2 minimizes the energy, we deduce the following:

(u -∆u) * W min + (v + ∆v) * W max ≥ u * W min + v * W max
Thus, we obtain:

∆u ≤ W max W min ∆v (10)
Four cases can occur: 1) ∆u < 0 and ∆v ≥ 0. Impossible because of equation 9 (∆u would be positive). 2) ∆u ≥ 0 and ∆v ≤ 0. Impossible because of equation 10 (∆u would be negative). 3) ∆u < 0 and ∆v ≤ 0. Then we have -∆v ≤ -Wmin Wmax ∆u < -∆u. This is a contradiction with 9. 4) ∆u ≥ 0 and ∆v ≥ 0. This case is the only possible and so we deduce the following equation:

0 ≤ ∆v ≤ ∆u ≤ W max W min ∆v (11)
2) Proof of theorem 3: With the results obtained previously, we can complete the proof of theorem 3.

Proof: The energy cost of the P 1 path can be written as follows:

w(P 1 ) = (u -∆u) * (W min ) + (v + ∆v) * (W max ) = u * W min -∆u * W min + v * W max + ∆v * W max
Following Equation 11, we know that ∆v ≤ ∆u. So we obtain:

w(P 1 ) ≤ u * W min -∆u * W min + v * W max + ∆u * W max
Replacing W max by c * W min , we obtain:

w(P 1 ) = u * W min -∆u * W min + v * c * W min + ∆u * c * W min = W min * (u -∆u + v * c + ∆u * c) = W min * (u + v * c + ∆u * (c -1))
Since u -∆u ≥ 0, we can upper bound ∆u by u:

w(P 1 ) ≤ W min * (u + v * c + u * (c -1)) = W min * (u + v * c -u + u * c) = W min * (v * c + u * c)
As W max = c * W min , we get:

w(P 1 ) = v * (W max ) + u * (c * W min ) ≤ c * (v * W max + u * W min ) = c * w(P 2 )
Thus we can conclude that: w(P 1 ) ≤ c * w(P 2 ). As the path P is equal to either P 1 or P 2 , we can deduce that its energetic cost is equal to either w(P 1 ) or w(P 2 ). So w(P ) ≤ c * w(P 2 ).

Theorem 4: The backbone obtained by BB has an approximation ratio of c * h max .

Proof: Suppose that L * is the set of leaves in the optimal tree. We assign to each node l * of L * the nodes composing the path between l * and the base station starting with the most distant node each time we are processing a new set. If a node belongs to several paths, we assign it to the first node k in which it appears. This process constructs the set S * (l * ).

Then, we assign to each node a charge such that the sum of the charges of the set l * gives his optimal total energy denoted by w * (S * (l * )). Thanks to the way of constructing these sets, the sum of the charge of all the nodes of the sets constructed gives the cost of the optimal tree. To calculate the approximation ratio what we need to do is to calculate the charge that each node in a constructed set can take in the tree constructed by BB. Then, as before, by summing all the charges of all the sets, we will get the cost of the tree constructed by BB. We denote w(S * (l * )) the cost of the set S * (l * ) obtain by adding the charge that nodes in S * (l * ) can take in the tree constructed by BB.

We know that the biggest charge a node can take is W max : ∀i ∈ V, e i ≤ W max Moreover, by construction, the number of nodes in a path is at most h max . Therefore, we can deduce that the cost of w(S * (l * )) is at most: w(S * (l * )) ≤ W max * h max Hence, the ratio between the energy W of our algorithm and the optimal energy W * is:

VII. CONCLUSION

In this paper, we focused on the problem of building an energy efficient backbone with a bounded delay for a heterogeneous wireless sensor network. To solve this problem, initially, a linear program has been proposed. However, given the complexity of the program and therefore the time needed to get a result on large networks, an approximation algorithm with polynomial time complexity has been proposed. A theoretical study has been done proving the correctness of the algorithm as well as its approximation ratio which is equivalent to c * h max .

  this figure, we assume h max = 5. The backbone of figure 1a represents the backbone obtained without the setting to zero phase. It is obtained as follows. At the first iteration, BB chooses to treat node h. The chosen path is P = (a, e, f, g, h). Therefore, nodes a, e, f and g are added to the set B, and they are removed from U . Nodes h, c and b are added to D. At the second iteration, the node to be processed is d. The path selected is P = (a, b, c, d). Nodes b and c are added to the backbone set B and are removed from U . Finally, d is added to D. The algorithm terminates since the set U is empty. At the end, the backbone consists in nodes a, b, c, e, f , and g. Its energetic cost is 10.

Fig. 1 .

 1 Fig. 1. Explanation of the zeroing of energy by BB. Backbone obtained without zeroing (on the left) and backbone obtained by setting to zero the energies (on the right)

1 :

 1 A 2 . Consequently, the time complexity of BB is O(|V | * (|V | * log |V | + |E|)) which is polynomial. C. Theoretical study Lemma The set B constructed by BB is a CDS.

  * w(S * (l * )) l * ∈L * w * (S * (l * )) ≤ |L * | * (W max * h max ) |L * | * W min ≤ c * h maxIn conclusion, the algorithm has an approximation ratio of c * h max .