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

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

Hervé Guyennet
email: guyennet@lifc.univ-fcomte.fr

Wireless sensor network system helping navigation of the visually impaired

Keywords: Wireless Sensor Networks, Navigation aids, energy conservation, zone partitionning, routing protocol. I

Navigation aids

for the pedestrians are considered new research challenges. The visually impaired are particularly concerned, because of their need to detect and avoid obstacles, as well as to orient themselves in unknown environments. In this paper, we discuss some existing projects in this domain and we propose a novel aid system formed of wireless sensors, meant to help navigation of the visually impaired, which addresses both orientation and obstacle negotiation. The proposed system is GPS-free and does not need external assistance in navigation.

INTRODUCTION

The orientation and navigation in unknown environments are old challenges. Orientation is the possibility of locating specific targets and of constructing routes to them. This implies the ability to establish and maintain an awareness of one's position in space relatively to landmarks in the surrounding environment and relative to a particular destination. Navigation extends the orientation challenges by the obstacle detection and avoidance. Thus, information on obstacles is taken into account for the route discovery and planning. Formerly, the sea and the air were the most difficult places where to be directed because they missed visible roads or other references. Moreover, the navigation systems were developed and integrated into several various applications. Recently, navigation systems for the vehicles appeared on the market and due to technological progresses, the equipment became increasingly small and light-weight. Consequently, the navigation systems became universally applicable, therefore useful for the pedestrians. Navigation for pedestrians became a challenge of research since mobility for people is a very significant component for our modern society. The navigation systems for the pedestrians are currently at the beginning of their development. Many researches were carried out or are currently work in progress. Pedestrian navigation covers a large field of applications with very different characteristics because the user's needs may vary considerably. One of these needs is the navigation for the visually impaired people and especially for blind individuals.

Existing electronic travel aids (ETAs) for the visually impaired respond either to the need of obstacle detection and avoidance, or to that of spatial orientation. Integration of both aspects in the system design, in order to offer navigation aids, still remains a research challenge. Our proposed system is meant to help navigation (so both obstacle detection and orientation) of the blind into an urban space equipped with wireless sensors. The blind person is also equipped with an advanced wireless sensor. Sensors form a network enabling transmission of environmental information (obstacles, targets) to the smart sensor which is treating the information, in order to construct the itinerary of the visually impaired. The system is designed to integrate detection of both dynamic and static obstacles. The main advantage of our system is that it does not need any GPS (Global Positioning System) information. GPS enables mobility when trying to reach a specific destination, which is important for any traveler, the visually impaired included. In spite of its orientation indications, the GPS presents some drawbacks. GPS system can provide accurate information to a traveler if it receives a signal from at least four satellites. Inclement weather and tall buildings can both interfere with signal reception. Another disadvantage of GPS is its dependence on battery power. Even though using a battery makes GPS systems portable, a battery can fail without warning. Moreover, most of the GPS products use digital commercial mapping, and maps become obsolete if not updated periodically. Another drawback is that GPS systems lack in detection of minor changes in the environment. A GPS receiver cannot inform a blind traveler of a drop-off on the sidewalk or a rise in elevation of the ground; therefore a blind pedestrian will not be able to use GPS to determine ordinary obstacles that may lie ahead or to decide whether it is safe to cross the street at a busy crossroad. GPS technology has other disadvantages worth mentioning. The largest drawback is that the GPS system is not reliable in all places where blind people want to travel (e.g. in indoor environments).

II. ARCHITECTURES AND FUNCTIONALITIES FOR THE VISUALLY IMPAIRED

The visually impaired requires information on their surroundings when they engage in travels. They need to detect the presence, location and nature of obstacles around them (obstacle negotiation) as well as the presence of particular targets or locations, identified by landmarks (orientation).

Obstacles may be stationary (objects, buildings, holes, stairs, and floors) or mobile (vehicles, other pedestrians). They may also be classified as underground, on the floor or suspended. Traditional mechanical mobility aids for obstacle detection and avoidance are the long cane and the guide dog. These tools do not offer enough range of detection (the cane), do not identify suspended obstacles (at head-height), are difficult to train or to look after (the guide dog) and are handheld devices; as a result they limit certain actions. In order to offer a maximum degree of safety and independence, electronic mobility aids have been designed. Their aim is to offer the visually impaired the ability to walk naturally and increase their mobilityas well as their travel speed. Electronic obstacles negotiators (Mowat [START_REF] Pressey | Mowat Sensor[END_REF], NavBelt [START_REF] Shoval | The NavBelt-a computerized travel aid for the blind based on mobile robotics technology[END_REF], GuideCane [START_REF] Borenstein | The GuideCane -A Computerized Travel Aid for the Active Guidance of Blind Pedestrians[END_REF]) give a larger vision of the 3D environment, using ultrasonic sensors, image sensors or infrared ones, or even standard cameras, which enlarge the cone vision up to 120 degrees. The interface between the electronic aid system and the human makes use of different senses (tactile or auditory). One important obstacle for the visually impaired in improving their quality of life is the inability to orient themselves. This handicap doesn't give them easy access to buildings, to important facilities (train stations, cultural places, post offices), and limits their use of public transportation. Persons having a visual handicap need to locate targets (destinations) and to construct routes to them. This capacity requires establishing and maintaining awareness of one's spatial position relatively to the destination. Electronic orientation aids may help the visually impaired to orient themselves in unknown environments. Generally, these devices provide information prior to travels (no dynamic information is integrated). MoBIC [START_REF] Petrie | MoBIC: Designing a Travel Aid for Blind and Elderly People[END_REF] is a project focused on the aid of the blind in mobility. The MoBIC travel aid consists of two interrelated components: the MoBIC Pre-Journey System (MoPS) to assist users in planning journeys, and the MoBIC Outdoor System (MoODS) to execute these plans by providing users with orientation assistance during journeys. The MoODS is a secondary aid, complementing primary aids such as the long cane or guide dog. It uses derived GPS information. Authors in [START_REF] Ladetto | In Step with INS -Navigation for the Blind Tracking Emergency Crews[END_REF] describe another GPS-based system, meant for orientation. They propose a module called PNM (Pedestrian Navigation Module) [START_REF] Guilliéron | Indoor Navigation Performance Analysis[END_REF]. PNM, in urban canyons with poor GPS signal reception, changes positioning strategy and uses step-length models and algorithms to determine the user's position. Some of the previous cited aids give limited useful information or require extensive training in the use of the obstacle or orientation map interface. The integration of obstacle detection within the orientation process helps to take into account the obstacle information in route discovery and planning. Electronic navigation aids, integrating location and orientation with respect to obstacles ahead, are less developed in the current approaches. Out of few projects proposing navigation aids (so both obstacle detection and orientation) for the visually impaired is the remote sighted guidance system developed at Brunel University. Its architecture is illustrated in Fig. 1. This system integrates three main technologies: Global Positioning System (GPS), Geographical Information System (GIS) database and digital video streaming over 3rd Generation (3G) mobile networks [START_REF] Garaj | A system for remote sighted guidance of visually impaired pedestrians[END_REF][START_REF] Hunaiti | Personal Navigation System using 3rd Generation Mobile Technology in conjunction with Global Positioning System[END_REF]. The system user contacts, firstly, the guide and requests navigation assistance from the Navigation Service Centre. During user displacement, the video camera captures video images of the surrounding and the GPS receiver gives the position. This data is sent to the guide. By using the GIS module, the guide determines the optimal route in order to arrive to the destination. According to the updated and received information from GPS and camera, the guide communicates navigational instructions to the user [START_REF] Hunaiti | A Remote Vision Guidance System for Visually Impaired Pedestrians[END_REF]. Our objective is to propose a new wireless sensor network system deployed on a large scale based on current and low cost technology, which enables the navigation of the visually impaired both indoors and outdoors. The aim of this system is offering mobility for the visually impaired in their journeys, and a maximum degree of independence. The former objective is achieved through the smart sensor worn by the visually impaired, collecting information about the environment. The latter exploits sensed information from devices placed in the surroundings. The deployment of these devices ensures, unlike GPS technology, that information on the environment can always be extracted. The general description of this system is presented in the next section, with the scientific challenges involved.

III. THE PROPOSED NAGIVATION SYSTEM

We propose a system based on a wireless sensor network architecture deployed on an urban space, in which sensors communicate (see Fig. 2) and transmit information to a particular smart sensor, worn by the visually impaired person. In order to guide the visually impaired, the sensing sensors collect information about the static obstacles (i.e. wall, barrier...) and the dynamic obstacles (i.e. cars, people...). The person to be guided is equipped with a smart sensor that treats and translates the information collected by the sensing sensors, and also interacts with the network. In the following, we pose a scenario to exemplify the approach. When the visually impaired interrogates, via the smart sensor, the sensor network in order to find a route to a particular destination, sensors collaborate to find the best routes, taking into account static obstacles and distance factors. A route is formed of a sequence of sensors identifiers, which helps to daw a navigation map for the visually impaired. During navigation, dynamic information on the environment is transmitted to the person, like the presence of vehicles in motion (see Fig. 3). The itinerary may, consequently, be modified according to these data. Two main scientific challenges are dealt with in this architecture and system: system lifetime and routing protocols (the process of selecting paths in a network along which data is sent). The energy of sensors in the network is essential to preserve the total lifetime of the system. During navigation of the visually impaired, several zones are not concerned with his travel, so sensors in those areas may be put into the sleep mode. This behavior led us to propose an algorithm of sensor organization, which divides the network into zones. In this way, only the sensors of the sub-zone in which the person moves are in communication with him. Therefore, the sensors in the other zones are switched off into the sleep mode in order to save their energy. We will detail this algorithm in the next section. A second research objective is finding routing protocols based on this architecture. The energy issue is also integrated in the routing approaches, making routing decision inside a zone and between zones (intra and inter zone routing protocols).

IV. ZONE PARTITIONING ALGORITHM

In this section we will briefly describe the new approach for sensors grouping in multiple zones. Firstly we give the objectives. Zone partitioning helps with addressing the scalability and energy efficiency issues in large sensor networks which is the case for our deployed sensor infrastructure. Classical ad-hoc routing in large wireless sensor networks is too expensive because of the routing table space storage and processing. Routing in smaller groups of sensor uses reduced routing tables, but needs another routing protocol between zones. Routing does not use specific zone node, as the cluster heads, in clustering algorithms, because cluster heads are not always reachable in one hop communication. We do not favor particular nodes forwarding task, but we make a two-level routing: between zones and inside zones.

As illustrated in Fig. 4, nodes are grouped in disjoint zones. The nodes of a zone can communicate between each other within one or more hops. If such information must be exchanged between a zone and another, it should pass by the nodes at the border with the other zone (dashed arrows). Our algorithm virtually constructs the zones with the necessary routing information. The border nodes will have a list of the border nodes of the others adjoining zones. In the suggested approach, the sensors are deployed randomly. We suppose that each node has a global ID. Information concerning nodes (such as energy, link states, geographic positions, etc...) is not required. This algorithm divides a wireless sensor network into several zones and provides useful information for the routing. There are some randomly selected nodes named inviting nodes, which launch the algorithm.

Zones are determined depending on the zone radius. The zone radius is the maximum number of hops between the inviting node and the invited nodes to its zone. The number of zones and the zone radius are algorithmic parameters that can be modified. The number of inviting nodes equals the number of zones. The detailed algorithm is given in [START_REF] Beydoun | Energy-Efficient WSN Infrastructure[END_REF].

V. EXPERIMENTATION

Experiments were built upon the J-Sim simulator [START_REF][END_REF] dedicated to WSN simulations. It is a component-based simulation environment, using the notion of autonomous component programming model. J-Sim is developed entirely in Java. In order to show the performance and the effectiveness of our algorithm, we compared it to another similar group division technique based on the number of hops, that of Lin and Chu [START_REF] Lin | A clustering technique for large multihop mobile wireless networks[END_REF]. They proposed a clustering algorithm that organizes nodes in clusters based on the number of hops. Each cluster has a cluster head and nodes of a cluster are within a given maximum number of hops R from the cluster head. Clusters may be dismissed and new clusters may be formed. A cluster is dismissed when two cluster heads are within a distance smaller than a predetermined number of hops D (D<=R), called cluster dismiss distance. In this case, each node of the dismissed cluster will try to join a new cluster. If a node cannot find a cluster head within R hops it becomes the cluster head of a new cluster. In order to make the clustering, each node has a 4-tuple information (i,C i ,D i ,N i ) including: 1. the ID of the node, supposed unique and represented as a positive number, 2. the cluster head ID of the cluster to which the node belongs to, 3. the number of hops from the node to its cluster head, and the ID of the node along the path from the node to its cluster head. We have demonstrated that our approach is energy-efficient because the number of sent packets is reduced considerably (see Fig. 5). We have also demonstrated the scalability of our approach by increasing the number of nodes in the network. Another advantage of our approach is that we can precise, in advance, the required number of zones (zN=15 in these simulations) which is not the case in Lin's algorithm where the number of zones may be very important.

Lin's algorithm creates small zones (several zones contain one/two nodes). Moreover, the number of zones in Lin's algorithm can be neither bounded nor pre-defined. Table I compares the number of zones generated by both algorithms. The error rate, in our approach, is the percentage of the unallotted nodes to any zone (these are alone). We can see that even if some nodes remain unallotted in our approach, their number progressively decreases when the number of nodes increases (Table I). That shows the scalability of the approach. In Lin's algorithm, we have calculated the error rate as the percentage of the nodes that are alone in their zones. As shown in Table I, the error rate is important and increases when the number of nodes increases (or the network density increases). Furthermore, Lin's algorithm generates a considerable number of zones. Each zone has few nodes (in average 2 nodes per zone) which is not adequate for an intrazone routing protocol as intended in our system. Unlike this behavior, in our approach, the number of zones is predefined and the average number of nodes per zone is 26. More simulations and results are shown in [START_REF] Beydoun | Energy-Efficient WSN Infrastructure[END_REF]. This paper presents a novel wireless sensor network system to help the visually impaired during navigation. This navigation method includes approaches that integrate both obstacle detection/avoidance and orientation/guidance aids, thus taking into account information on obstacles in route discovery and planning. It is GPS-free needing only low cost devices and obstacle detection sensor technologies. We also don't need remote assistance to guide the visually impaired. We have also cited other existing systems and aid technologies that are not complete solutions for helping navigation of the visually impaired.

The architectural approach highlights the challenges of minimizing energy consumption and of providing routing protocols. The virtual structure proposed through zone partitioning simplifies routing and can help to reduce energy consumption by switching particular sensors to the sleep mode.

Figure 1 .

 1 Figure 1. The Brunel University's system componentsThe challenges in ETAs research are both technological (finding new sensors to better detect obstacles, new architectures able to reconstruct needed information, new techniques to display the computed information and to give navigation indications to the visually impaired) and functional (associating obstacle identification and space orientation). Our objective is to propose a new wireless sensor network system deployed on a large scale based on current and low cost technology, which enables the navigation of the visually impaired both indoors and outdoors. The aim of this system is offering mobility for the visually impaired in their journeys, and a maximum degree of independence. The former objective is achieved through the smart sensor worn by the visually impaired, collecting information about the environment. The latter exploits sensed information from devices placed in the surroundings. The deployment of these devices ensures, unlike GPS technology, that information on the environment can always be extracted. The general description of this system is presented in the next section, with the scientific challenges involved.

Figure 2 .

 2 Figure 2. Sensors deployed on the urban space

Figure 3 .

 3 Figure 3. Communication between sensors

Figure 4 .

 4 Figure 4. Wireless Sensor Network zone infrastructure

Figure 5 .

 5 Figure 5. Average of the sent packets

Table I .

 I Error rate and number of zones

	# nodes	Our approach	Lin's algorithm
		Error	zN	Error	zN
	300	24%	15	38,3%	164
	400	8%	15	34,2%	210
	600	0,7%	15	46,1%	325
			VI. CONCLUSION


Jean-Baptiste Aupet
email: jean-baptiste.aupet@lifc.univ-fcomte.fr

Nabil Elmarzouqi
email: nabil.elmarzouqi@lifc.univ-fcomte.fr

Eric Garcia
email: eric.garcia@lifc.univ-fcomte.fr

Jean-Christophe Lapayre
email: jean-christophe.lapayre@lifc.univ-fcomte.fr

Virtual Awareness Card for adaptability in Collaborative Virtual Environments

Keywords: Adaptability, Awareness, Awareness information, Collaborative Virtual Environment, Distributed System, Telediagnosis, Telemedicine

This article exposes the concept of Virtual Awareness Card in Collaborative Virtual Environments (CVE). This concept allows users to send information about their preferences and their hardware and software properties. Our approach is focused on the Awareness in order to use the awareness information to ensure the adaptability of various sites in the collaborative environment. The VAC is used in the CVE during the synchronous and asynchronous sessions to assure a collaborative work using heterogeneous support and multitude tools. VAC concept is based on three awareness directives: Convenience Awareness, Preferential Awareness and Restrictive Awareness. The goal is ultimately to offer adapted workspace to increase the awareness among the collaborators. In function of information of Virtual Awareness Card, collaborators can interact with more possibilities and make more efficient use of workspace functionalities. We'll show with several scenarios the use of the VAC in CVE of telemedicine to show the increase of possibilities offered by this concept.

INTRODUCTION

Virtual Collaborative Environments (VCE) are in expansion these last years thanks to the improvement of the communication links and networks capabilities. Possibilities offered by these environments are in constant evolution and will be in adequacy with the needs of the users. To be efficient, we need to know at each time how to provide the good information at the good time. To do this, we develop a structured way to obtain information about all the actors of the collaborative work. This information allows the system to provide adapted environments to users in function of their needs.

Our approach focuses on the awareness of collaborative environment by promoting the interactive nature of the group environment and considering that the systems of interaction are systems of awareness [START_REF] Peter | Computer supported cooperative work: New challenges to systems design[END_REF]. We have singled out the awareness information as a key element linked to the actor, shared objects, activities and full aspects of group environment.

In existing collaborative environments, users may register information of his environment such as preferences or the type of connection that he disposes to connect the service. These information wasn't updated without human interaction. The concept of Virtual Awareness Card (VAC) will improve the management of the evolution of inquiries. VAC includes part of information such as description of the user and his preferences. But the VAC will give more information about the user and especially of his environment and how to be aware of him.

An adaptable Virtual Awareness Card which collects evolution of user's information could offer in date data to adapt the environment in correlation with user's attempts and possibilities. We'll present the Virtual Awareness Card concept in Telemedicine collaborative environment to show how that concept can upgrade the efficiency of work. We'll also show these applications with scenarios and its implementation as a web service.

Virtual Collaborative Environments and Telemedicine

Virtual Collaborative Environments

Collaborative Virtual Environments (CVE) are systems of interaction allow multiple actors to interact among themselves and with their area work. The particularity of CVE lies in their ability to offer a multitude of tools for users to share data and work on the same space. From user point of view, the collaborative sessions is the concept of co-presence of actors in time and space. The actors are, most often, represented by avatars which movements and behavior, a model and physical properties are allocated. The use of new technologies facilitates the access of actors to their work areas from afar. The copresence of collaborators in synchronous session is designed to promote the group and to facilitate access to communications between individuals two by two or using multicasting protocols.

With advances in communication networks and processors power, the transition to the third dimension has been a great success. The integration of a multitude of ways to diversify the possibilities of human-machine interaction has become, notably an obligation in the group environment. This obligation is explained by the heterogeneity of media access used by the actors: web, PDA, personal computer, desktop ... Provide an environment of immersion [LEU00] remains an ambition sought by the very common CSCW (Computer Supported Cooperative Work), especially as the themes addressed by CVE are very broad: distance learning, telemedicine, remote monitoring... This requires a great effort to designers of these virtual environments to put players in the proper environment to the treated theme and the scenario required by employees (meeting room, medical surgical room ...). The recreation of artificial stimulation generated by the group environment in reality strengthens the work of individuals in the virtual world, dedicated to collaborative work.

Tele medicine

Telemedicine and eHealth are the use of electronic communication technologies as a method of delivering health care, education, and related services (medical imaging, distance teaching, patients files consultation). Dissolving barriers such as distance, time, geography, weather, and economics, applications are designed to bring services to clients rather than clients to services and improve the accessibility to the specialized health care thanks secured transfer of data. These applications give the practitioners the possibilities to exchange their information and experiences as they were in the same room to deliberate together [BEN 02]. EVC are environments that provide all the services to perform these applications.

Collaboration and awareness features are used to make new telemedicine software more efficient than classical software in terms of collaboration level. The goal of telemedicine is to allow practitioners to act as if they were at the same diagnosis table, using a great panel of medical tools.

Virtual Awareness Card

Which adaptability we need for CVE?

A lot of criterions could change the system to accommodate with the users attempts, but the users won't lose their time to configure these criterions of the system especially if they want to use the system with different terminal. For example with their computer in their house or with a public access point with a PDA... If users must change the configuration of their system each time they change of work environment, they quickly unused this system in other environment that he has configure to avoid losing time at each change. Therefore the system must be adaptable but to provide an environment that evolves with the attempts of the users [TRE 04], it will be adaptable and adaptive. That's the reason why we introduce the notion of adaptive systems. The difference between adaptive and adaptable refers to the extent to which users can exert influence on the individualization process of a system. Adaptable systems are customized by the users themselves [RUI 02], whereas with adaptive systems this process will be made automatically.

Concept of VAC

In CVE, several actors interact with each other in the group environment and via a multitude of media. Our basic architecture [ELM08] centralizes awareness in the CVE. This helps users get together being aware of one another and acting on shared data. We move towards an "Aware Collaborative Environment" that supports multiple levels of collaboration and offers a variety of tools to develop collaborative group work. We use this awareness information to address three important notions for collaborative workspace:

-Convenience Awareness: accessibility to the group environment requires, in addition to an awarenessoriented working group, the medium adaptability according to the support used by the actor. The user, via his area work, is aware of its medium and different media access used by all actors. We use the awareness information, in this level, to dynamically adjust the profile of the actor by his support. What determines the first generator field of the VAC. The actors adopt an awareness of convenience in access to EVC via the appropriate hardware medium for the actor (PDA, laptop ...), -Preferential Awareness: the handling ability of operations in the working group takes into account the adaptability to custom attributes of each collaborative site. We use the awareness information of actor's workspace to adapt the various collaborators to different preferences of actors available in the EVC. We feed the workspace of the actor with a workspace awareness that takes into account their preferences. What determines the second field generator of the VAC. The actors at this level opt for preferential awareness.

-Restrictive Awareness: the involvement of adaptive actors takes into account the constraints imposed at each actor by the environment itself. We use the awareness information at this level to adapt the actor in question, and then the rest of the collaborators, with various restrictions imposed by the nature of the working homogeneous spaces that are connected (bandwidth, restrictive access to specially tool…). The actors adopt a restrictive awareness for their adaptability to the group environment.

As shown in Figure 1, the VAC is designed using awareness information: convenience awareness, preferential awareness and restrictive awareness. The adaptability of the different sites of collaboration is achieved by the management and handling of cards assigned to each collaborative site. In this article we discuss the awareness information from each site separately, and regardless of his membership in the working group: Individual Awareness.

Awareness information for adaptability

We have limited awareness information handled by the VAC and that comes from the three kinds of awareness required for adaptability. We focus on four types of information:

-Hardware: on the different media used by each player (PDA, laptop…) -Software: referring to the list of tools installed on the medium used by each player (videoconferencing tool, audio player…), -Network: that characterizes the networks properties involved in each medium (speed down and speed up, proxy configuration, gateway ...) -Multimedia: on the appropriate configuration tools manipulated by the actor (codec, video configuration...) As shown in Figure 2, we organized the information handled by the VAC in the form of XML structure.

Adaptability information

The virtual awareness card will be able to give information of the user but although information about the system. These information enable the environment to change and adapt itself to preferences and habits of users. To provide an adaptable and adaptive system to the users, we must identify the most important criterions that interact with system and what criterions are significant for the interaction among system and users but also among users themselves.

There are two levels of adaptable and adaptive criterions, the Application level and Network level [ZHA 07]. In their level we must show the relevance of criterions according to their utilities and their performances. In function of restrictions of the system, some criterions will be used or not. We will study which criterions will be required and those that will be optional.

Application

To implement the virtual awareness card we've made an xml description file that describe the environment of the user with these preferences and these environment attributes such as terminal properties, network possibilities, mobility… That is not an exhaustive description and lot of attributes are optional, it is possible to require some attributes according to the EVC necessities. In optimal version of VAC, these information will be autogenerated by the system when user has a change of his environment or if he's on movement. The Web service offers a bank of codec and tools to users for installing the good codec such as MPG4 H264 for video encoding/decoding or G729 for audio or the same tool (White board, ITK library for medical image processing) in all environments.

We've got down to one's studies about three scenarios that illustrate the use of virtual awareness card. These scenarios will show how users could take advantages of updating data with through his virtual awareness card. In this work, we have limited to study the impact of the diffusion of adaptabilities information's with the VAC in an existent EVC. The VAC processing should not affect the operations in the EVC.

We'll study the case of a practitioner who's travelling among several hospitals or directly visiting patients at home. He needs to be connected to his environment if he wants some help to make a diagnosis or to attain patient's files. If he has at one's disposal an internet connected computer to access his telemedicine application or if he has only access with a laptop or a PDA with 3G connection, he couldn't access to his application with the same functionalities. The presentation and the options accessible will be adapted to his work environment.

Uses of VAC illustrating by scenarios

Scenario A: The practitioner A and practitioner B use the same environment (Computer and network) to consult patient's files stored in the centralized database server. They can log in the EVC of telemedicine to work and make diagnosis with tools offer by the EVC. The VAC will automatically harvest information about the hardware and software possibilities of the computer. Users have also saved their preferences (descriptions of user, see like, preferred applications…) with the VAC Web service.

The practitioner C disposes of a powerful multimedia computer that is equipped with devices and software with associate codec for multimedia applications. Automatically all these features will be detected and put to the EVC server thanks to the VAC web service Thus practitioner C can take advantage of EVC tools providing most level of interaction.

If practitioner A wants to enjoy new services offered by the new environment, he can log into the EVC with the powerful computer and he will automatically be able to use these tools.

Scenario B:

The practitioner A makes a medical examination at the patient's home. He needs to ask his colleague to make a diagnosis. He can connect to the EVC with his PDA and 3G connection. With the generated VAC send to the VCE the practitioner A can access to the patient's file and can profit of available applications for this type of terminal and connection.

He can collaborate with his colleague as if they were in the same room as their habit. He can explain his diagnosis and show information about the patient. The VAC information had allowed users to communicate with available devices and software. He uses his laptop with a wifi connection. When he log into the telemedicine EVC, the generated VAC list the properties of his connection and his hardware and software environment. He's connected with a specialist of a medical center to collaborate on a diagnosis with the possibilities and tools of the medical center. The service has detected that the laptop is equipped with webcam. Codec and software are installed too. The specialist asks for the practitioner to use this equipment.

Practitioner can make a movie of an injury or a symptom and encode it with the good format supported by his colleague. They can exchange data on good format with the information diffused by the VAC Web Service and make a collaborative diagnosis.

Performance of VAC

To experiment the benefits of this concept we choose to make a simulation with the diffusion of VAC for each user. We have tested the mechanism of VAC with 6 collaborative sites. We have varied the frequency of updated awareness information between 1s and 60s in function of environment changes. We note that the size of VAC is of the order of 700 bytes. Each node receives the VAC of others according to different frequencies. We used the Soap protocol for exchanging data between the users of EVC. SOAP protocol allows developers to send and receive XML Data over HTTP. This protocol allows data exchange over proxy without specific port configuration. This mechanism will assure the access of data. In final version, this XML file will be automatically updated and diffused to each user by using centralized architecture. According to the results of simulation shown on figure 6, we note that both up and down speed remain negligible (about 5 kb / s) when the frequency of changing of collaborative site profile exceeds 6 s. This test shows that VAC diffusion doesn't affect the speed of the network.

Conclusion and perspectives

In this article we have introduced a new concept of adaptable awareness in Virtual Collaborative Environments provided by the virtual awareness card. We prove that card will increase the use of these environments by applying the best user-profile in function of these preferences but especially these hardware and software possibilities. The card can be used for a non exhaustive list of information. Information will automatically provide an interaction and the awareness of the others. Each user knows how he could collaborate with the other participants. The CVE with VAC updated information could adapt the environment and provide to the users exchangeable tools and data.

Perspectives: A way to increase the performance is to develop more awareness information used for the auto-generation of the card depending of the environment functionalities. With this kind of awareness information each user will be advised about the global awareness of the group. The diffused information will be used to adapt the virtual topology of the network in order to create an optimized overlay network to create a real distributed architecture.

Figure 1 :

 1 Figure 1: Conception of VAC in CVE.

Figure 2 :

 2 Figure 2: XML description file.

Figure 3 :

 3 Figure 3: Scenario A.

Figure 4 :

 4 Figure 4: Scenario B.

Figure 5 :

 5 Figure 5: Scenario C. Scenario C: As in the scenario B, the practitioner A makes a medical examination at the patient's home. He needs the diagnosis of a specialist to determine if the patient is showing special symptoms.

ACKNOWLEDGMENT

The authors wish to thank the members of the LIFC for their experiences in telemedicine and Distributed systems. This work was supported in part by region council with the Servastic project.


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

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

Hervé Guyennet
email: herve.guyennet@lifc.univ-fcomte.fr

Wireless Sensor Network Infrastructure : Construction and Evaluation

Keywords: WSN, zone partitioning, energy management, scalability I

Large area wireless sensor deployments rely on multi-hop communications. Efficient packet transmissions and virtual topologies, which structure sensor networks, are two main features for efficient energy management in wireless sensor networks. This paper aims to present a distributed and low-cost topology construction algorithm for wireless sensor networks, addressing the following issues: large-scale, random network deployment, energy efficiency and small overhead. We propose structuring nodes in zones, meant to reduce the global view of the network to a local one. This zone-based architecture is the infrastructure used by our hierarchical routing protocol. The experimental results show that the proposed algorithm has low overhead and is scalable.

INTRODUCTION

Technological advances in microelectronic and wireless communications have enabled environmental monitoring using small sensor devices grouped in new types of networks called wireless sensor networks (WSNs). Space exploration, vehicular movement monitoring and critical events detection are some examples of wireless sensor network applications. Sensor nodes are equipped with both sensory devices allowing data sensing and wireless transceivers that help them communicating. When detecting a stimulus, sensor nodes (called sources) generate data packets and transmit them through the network to one or several special nodes (called sinks). Direct communications would be possible if large transmission power on the transmitter node was used. However, in largely deployed networks, high transmission power would not be enough to reach the sink and would consume lots of energy. This problem can be overcome by multi-hop communications, sensors playing thus a double role: data generator and data router.

Routing protocols providing this path construction should fill some requirements concerning energy efficiency, distributed-based algorithmics and scalability. Among different routing techniques, table-based routing (inspired from ad hoc networking) exploits communication costs (generally in terms of expended energy), which are required to reach the sink via a given neighbor. These protocols are a trade-off between path availability and the overhead due to the construction of the routing tables themselves. Moreover, in WSNs, routing protocols should be designed under the constraints of limited memory and large-scale node deployments.

In wireless, mobile and multi-hop networks, routing protocols should be able to deal with random node deployment. It means that even though sensors' positions are known (manually deployed) no particular hypotheses concerning its neighbors can be done due to the large scale (neighborhood discovery protocols need to be implemented). Therefore, sensor networks are considered as a subclass of ad hoc networks because of the absence of infrastructure. Thus, ad hoc networking may influence some routing approaches in wireless sensor networks, in respect to topologies. In hierarchical structures, topology control can be applied to minimize the set of active nodes (switching off some of them to preserve energy) or to define coordination tasks for some particular nodes. We are interested in hierarchical structures because flat architectures generally depend on the size of the network, which makes routing approaches difficultly scalable. In either approach, an important issue that needs to be addressed is the most crucial aspect: the energy efficiency.

Our contribution to the topology construction is a hybrid solution: organizing sensors in zones (virtual architectures) at a low cost. For this purpose, an inexpensive neighborhood discovery algorithm is proposed. The idea is to distribute routing roles between nodes inside a zone, avoiding cluster management (including cluster head election and rotation, cluster construction as in classical hierarchical approaches). The paper is organized as follows. In the next section, we present some of the solutions in literature concerning the construction of virtual network structures for WSNs. Next, we give our zone partitioning algorithm. Then, we compare it to some existing partitioning algorithms. We also show its evaluation through simulations. Finally, the last section concludes the paper.

II. RELATED WORK

Energy consumption is one of the main challenges in wireless sensor networks. Energy saving assures a long lifetime for the system. Another main goal is reducing the size of the stored data (e.g. routing table) in each node of the network. Clustering is an important technique for prolonging the system lifetime and reducing the size of the stored data. In clustering, nodes are gathered in several groups, generally disjoint, which are named clusters. Each cluster has a cluster head (CH). The nodes collect data and send it to the CH that forwards this data to the final user or Base Station (BS). CHs can communicate with the Base Station directly or via other CHs. There are many existing clustering protocols. LEACH [START_REF] Heinzelman | Energyefficient Communication Protocol for Wireless Microsensor Networks[END_REF] is a distributed clustering-based protocol that uses randomized rotation of the CHs to evenly distribute the energy load among the sensors in the network. LEACH assumes that the fixed sink is located far from the sensors and that all sensors in the network are homogeneous and battery-constrained. Lin's protocol [START_REF] Lin | A clustering technique for large multihop mobile wireless networks[END_REF] is a distributed clustering technique for large multi-hop mobile wireless networks. The cluster structure is controlled by the hop distance. In each cluster, one of the nodes in the cluster is designed as cluster head. Other nodes join a cluster if they are within a predetermined maximum number of hops from the cluster head. HEED [START_REF] Younis | Heed: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF] is a distributed clustering protocol that periodically selects cluster heads according to a hybrid function between their residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. In CES distributed protocol [START_REF] Lehsaini | An Efficient Cluster-based Self-organization Algorithm for Wireless Sensor Networks[END_REF], each sensor computes its weight based on the k-density, the residual energy and the mobility features. Then it broadcasts the weight to its 2-hop neighborhood. The sensor node having the greatest weight in its 2-hop neighborhood becomes the cluster head and its neighboring sensors will join its cluster. SPAN [START_REF] Chen | Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks[END_REF] is a distributed, randomized protocol in which nodes make local decisions on whether to sleep, or to join a coordinator that rotates at times. Each node makes its decision depending on the amount of available energy on the node and on its degree (the number of its neighbors when the node is active). SPAN is a protocol that operates under the routing layer and above the MAC and physical layers. The routing layer uses information SPAN provides, and SPAN leverages any power saving features of the underlying MAC layer [START_REF] Chen | Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks[END_REF]. The centralized PEGASIS protocol [START_REF] Lindsey | PEGASIS: Power-efficient gathering in sensor information systems[END_REF] constructs chains instead of clusters. Each node delivers the sensed data to the nearest neighbor node. One sensor node on the chain is assigned as the cluster head node that delivers sensed data to the base station. The head node is selected by turns; this technique allows to consume energy evenly in wireless sensor networks. However, the PEGASIS protocol causes redundant data transmissions since one of the nodes on the chain is selected as the head node regardless of the base station's location. In [START_REF] Jung | The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[END_REF], authors propose the enhanced PEGASIS protocol based on the « concentric clustering » scheme to solve this problem. It means that clusters have the shape of concentric circles. Similar to PEGASIS, the SHORT protocol [START_REF] Yang | SHORT: Shortest Hop Routing Tree for Wireless Sensor Networks[END_REF] adopts centralized approaches and requires powerful BS to take the responsibility of managing the network topology and to calculate the routing path and time schedule for data collection.

Most topologies based on clusters assume that cluster heads are high-energy nodes and their transmission power can be adapted in order to reach the base station at far distances and to communicate directly to other cluster heads.

Another assumption is that nodes within a cluster can directly communicate to the cluster head. In SHORT, HEED, CES, PEGASIS and Enhanced PEGASIS all nodes are supposed to have the ability to modify the transmission power in order to control topology. The LEACH radio model [START_REF] Heinzelman | Energyefficient Communication Protocol for Wireless Microsensor Networks[END_REF] is used for these protocols. Requirement of adaptive and dynamic transmission power modification can be prohibitive, especially for sensors not equipped with transmission amplifier. SPAN uses the radio model of the Cabletron Roamabout 802.1 card that has fixed transmission range and does not support power control. Lin's protocol does not mention the radio model used for simulations.

The transmission defines the set of neighbors for a sensor node, those able to receive the transmitted signals. Because variation of the transmission range consumes more resources, virtual topologies should be proposed for sensor networks that are made of sensors with fixed transmission power. The challenge addressed in this paper presents an approach of virtual structuring of networks without using topology control technique. Our contribution to topology construction addresses two main issues in WSNs: distributed approaches, and energy efficiency. Moreover, our approach is independent of the embedded sensor technology (being able to vary the transmission power or not); the only parameter considered is the current node's transmission range. The algorithm is executed simultaneously with the neighborhood discovery protocol for random sensor node deployments. In the next section, we will detail our work for structuring wireless sensor networks into zones, which is not a real clustering algorithm like the cited related work. Therefore, no cluster heads exist in our topology; no other information on the network (e.g. geographic position) is required.

III. VIRTUAL WSN STRUCTURING: ZONE PARTITIONING ALGORITHM

Virtual topology construction for wireless sensor networks should deal with the following challenges: largescale and random network deployment, energy efficiency and small overhead. These are the issues addressed by our algorithm of WSN virtual structuring, achieved through node grouping in multiple zones. As illustrated in Figure 1 the proposed algorithm tends to divide a wireless sensor network in several zones and to save useful information for routing. This zone construction enables intra-zone view for every node, which reduces complexity compared to a global network management.

Figure 1. Zones in a Wireless Sensor Network

The nodes in the same zone can communicate within one or more hops. After structuring the network, the nodes at the border of each zone route data between these zones (dashed rows in Figure 1).

We consider the general case of randomly-deployed nodes. In our approach, there are some network nodes named inviting nodes that launch the partitioning algorithm. These nodes are designed randomly because we assumed that nodes in the network have no information either about its neighbors (e.g. geographic positions) or about the network in order to elect the inviting node in a distributed way. In addition, election protocols in large networks are expensive in terms of number of control packets and energy consumption. Note that the inviting nodes do not have any additional role like the cluster heads in the clustering protocols, so there is no need to execute an expensive protocol to elect the inviting nodes. The ideal solution is to choose the inviting nodes such that the distance between them is maximal in order to avoid closely placed inviting nodes. Therefore, the problem that could intervene in random selection is to have geographically close inviting nodes. In order to justify our assumption, we have calculated the probability of finding an inviting node in the communication range of another one. For that, we have simulated a network of sensor nodes that are distributed randomly. These nodes include several special nodes (inviting nodes). We varied the network size from 400, 500 nodes (low-density network), to 600, 700 and 800 (highdensity network) nodes. The simulations were performed on a large area of 1500m*1500m. The transmission range T r is set to 300 meters 1 . Each simulation result in Figure 2 is an average of 1000 simulation results. We varied the number of the inviting nodes from 5 to 25 nodes. Figure 2 shows that the probability of finding an inviting node in the communication range of another one does not exceed 1.2*10 -3 when considering a deployment of 800 nodes and 25 inviting nodes. We conclude from the negligible probability that the random distribution of the inviting nodes can be fairly used to partition sensor networks; moreover, this method has the advantage of being less expensive than the execution of a distributed election protocol.

A. The algorithm parameters

In our approach, we suppose that each node in the network has a global ID, NodeId. The partitioning algorithm depends on three parameters: R, zN, and N. R is the radius of a zone. It is the maximum number of hops between the inviting node and the invited nodes that will possibly join the zone. zN is the required number of zones. N is the number of nodes in the network. Each node specifies, during the algorithm execution, the following attributes: ZoneId, NodeType, and BorderTable. ZoneId defines the zone to which the node belongs. NodeType is the node type. It may have two possible values NORMAL or BORDER. All nodes have the NORMAL type at the beginning. Node may change its type to BORDER if it is located between two or more zones. BorderTable is the table in which a border node (of The fields of a packet exchanged during the execution of the algorithm are shown in

B. Zone partitioning algorithm description

In the proposed algorithm, information concerning nodes (such as energy, link states, geographic positions, etc...) is not required. The details of the algorithm executed by each network node are shown in Figure 3.

Initially (Figure 3, part A), the zones are formed of the inviting nodes (one node per zone) which broadcast an INVITATION packet only once to its neighbors in order to join its zone (the number of the inviting nodes in the network equals the number of zones zN). This INVITATION packet has an initial TTL value that equals the zone radius R. In Figure 3

C. Topology maintenance: node join, leave and mobility

Once the initial topology is built (either in clusters, chains or even zones as in our algorithm), a main problem needing solution is topology maintenance. Maintaining consistent view of a virtual network structure generally needs information update on neighbor nodes when nodes join and leave the network (due to failure), or/and when node mobility is involved.

In our partitioning algorithm, if a new node joins the network, it must broadcast a NEW_NODE packet in order to be assigned to a zone. Concerning node failure, only border nodes send regularly neighbor discovery packets (e.g. HELLO packet) to update their BorderTable tables. A normal node failure does not have any effect in the present network topology. It will be treated in our future proposed routing protocol based on this hierarchical structure.

Node mobility can be treated as a node leave and its join in a different geographical environment. This change can be reflected in our zone-based network topology in the following manner: a node moving to another location resets its attributes (BorderTable and ZoneId) and broadcasts a NEW_NODE packet. Nodes receiving this packet answer by an INVITATION packet. The mobile node, when receiving an INVITATION packet, treats it according to the algorithm presented in Figure 3.

IV. DISCUSSION

In this section, we compare the proposed algorithm in the paper with some similar existing work. The aim of our zone partitioning algorithm is to organize sensor networks in local view structures in order to reduce complexity of routing protocols. The proposed zone infrastructure may be compared with other topology constructions, in particular with clustering techniques. We show in the remainder of this part several differences between the two approaches, which justify considering our zone partitioning different from clustering.

One critical aspect concerning cluster construction and maintenance is the overhead. Control messages exchanged in order to choose the cluster heads, to define the cluster to which a node belongs and to maintain consistent view of cluster may generate important overhead.

In LEACH, sensors elect themselves to be cluster-heads at any given time with a certain probability. These cluster head nodes broadcast their status to the other sensors in the network. Each sensor node determines to which cluster it wants to belong choosing the cluster head that requires the minimum communication energy (based on the received signal strength) [START_REF] Heinzelman | Energyefficient Communication Protocol for Wireless Microsensor Networks[END_REF]. The clustering phase in LEACH needs several communications between different sensors in the network. In Lin's protocol [START_REF] Lin | A clustering technique for large multihop mobile wireless networks[END_REF], each node, at the beginning, is a cluster head. Depending on the distance between the cluster head nodes and on their IDs, clusters merge up to a point where there is no more fusion possible. This technique needs important communications and computation. HEED [START_REF] Younis | Heed: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF], CES [START_REF] Lehsaini | An Efficient Cluster-based Self-organization Algorithm for Wireless Sensor Networks[END_REF] elect and re-elect the cluster heads according to nodes information (residual energy and position). Exchanging this information needs more communications between nodes, which means more energy consumption. SPAN [START_REF] Chen | Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks[END_REF] uses routing information and geographical position of nodes in order to construct its own topology. SPAN adaptively elects « coordinators » from all nodes in the network. SPAN coordinators perform multi-hop packet routing within the network. SPAN also rotates the coordinators. PEGASIS [START_REF] Lindsey | PEGASIS: Power-efficient gathering in sensor information systems[END_REF] and enhanced PEGASIS [START_REF] Jung | The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[END_REF] assume that all nodes have the knowledge of the network, which requires communications between nodes. In comparison with the previous protocols, our approach diminishes the number of communications (sent and received packets) between the network nodes. Decisions are less cooperative and there is no need of any network information (geographic position, energy, routing tables, etc...) like in the distributed algorithms LEACH, Lin's, HEED, SPAN, enhanced PEGASIS and CES. In addition, these algorithms, except for Lin's, require that the node have ability to modify the transmission power in order to control topology, which is not the case in our approach. PEGASIS and SHORT, two centralized approaches, design the BS, considered more resourced, to control the network, whereas our approach is completely distributed.

V. ZONE PARTITIONING: EXPERIMENTATIONS AND RESULTS

Experiments were built upon the J-Sim simulator [9] dedicated to WSN simulations. It is a compositional, component-based simulation environment. It is built upon the concept of autonomous component programming model. J-Sim is developed entirely in Java. The signal attenuation due to obstacles or other factors (e.g. use of unidirectional antennas) is simulated in J-Sim. Therefore, the vicinity of a node in terms of transmission range is not necessarily spherical.

In order to evaluate the efficiency of the zone partitioning algorithm, we considered three metrics: the error ratio, the overhead and the scalability. Zone construction virtually affects sensor nodes to particular zones. Ideally, every network node should be member of a zone. Depending on the parameters of the algorithm and on the interconnection topology of the network, we evaluate the efficiency of our algorithm in terms of percentage of unassigned nodes (isolated nodes), defined as the error ratio. One particular evaluation metric for infrastructure construction is the generated overhead. We estimate it by both the number of sent and received packets (exchanged during the execution of the zone partitioning algorithm) and the dissipated energy. The previous two evaluation metrics depend on the network size. Scalable zone partitioning is of main interest for largearea sensor deployments. For this reason, we also evaluate the behavior of the proposed algorithm when varying the network size.

The simulations were performed on a large area of 1500m*1500m. The node's maximum transmission range is set to 150m. In our experiments, we varied the network size from 300, 400 nodes (low-density network), to 600 and 800 (highdensity network). Each simulation result in our graphs is an average of five simulation results with the same algorithm parameters.

A. Error ratio evaluation

The error ratio is defined as the percentage of nodes unassigned to a zone (isolated nodes). It is evaluated depending on the two algorithm parameters: the zone radius (R) and the number of zones (zN).

The left side of Figure 4 shows that the error ratio of our algorithm in a low-density network (300 nodes) is quite high. If we increase the number of nodes (400 nodes), the error decreases (see Figure 4, right side). In the previous two cases, this error decreases when we increase the zone radius and the number of zones. A high error ratio, in a low-density network, is due to two main causes:

• the node connectivity -nodes do not experience enough transmission range to reach neighboring nodes in the network or there is an obstacle between them obstructing communication, • the radius of the zone R -it is not large enough. The propagation of invitation packets stops before reaching all nodes in the network. The radius of the zone serves to reach more nodes that are within long hop-distances from the inviting nodes. The number of zones serves to increase the probability for a node to be assigned to a zone. There is the same effect when we increase the zone radius. In a dense network (600 nodes), the error ratio goes down to 4% (left side of Figure 5) and close to zero in a network of 800 nodes (right side of Figure 5). That shows the importance of node connectivity which assures total communication coverage (every node is reachable).

B. Overhead evaluation

The overhead, in our experiments, was evaluated by counting the control packets and by estimating the battery level. The control packets are the sent and the received packets exchanged to partition the network into zones.

Figure 6 (left side) shows the average number of the received packets for several simulations (different values of R and zN). The average does not exceed 13 packets per node in large networks (800 nodes). In Figure 6 (right side), the average number of the sent control packets is shown. It does not exceed 3 packets per node in the network made of 800 nodes.

To estimate the energy consumption of the battery on each node, we have used the energy consumption model of the MICA2 sensor [START_REF]Crossbow. MICA2 Data sheet[END_REF]. The size of the exchanged control packet equals 64 bytes. The CPU energy consumption has been ignored because the time of packet processing is generally very small compared to the time of transmission and/or reception.

C. Scalability of the zone partitioning algorithm

The scalability refers to the ability of the algorithm to deliver pertinent results when increasing the number of nodes in the network. As shown by the previous results, our algorithm adapts well when the number of nodes is increased. For example, in a random distribution of 800 nodes with the radius of the zone set to 10 and the number of zones set to 10, few nodes have not been assigned to any zone (isolated nodes). The error ratio is 0.375% of the total number of nodes.

VI. CONCLUSION AND FUTURE WORK

Energy efficiency and data storage are two main features in wireless sensor networks. Network partitioning into many zones tends to save energy and minimize the size of the routing information saved on the sensor. In this paper, we propose a new distributed zone partitioning algorithm for sensor networks based on the number of hops. Network information (e.g. node's energy level, geographical position) is not required to accomplish the partitioning. We have evaluated our approach by estimating the error ratio (percentage of unassigned nodes to any zone), the overhead (number of control packets) and the scalability. In our undergoing work, we propose a routing protocol for wireless sensor networks based on this virtual topology.

1Figure 2 .

 2 Figure 2. Probability of finding an inviting node in the communication range of another one (Tr =300 m)

Figure 3 .

 3 Figure 3. Zone partitioning algorithm

Figure 4 .

 4 Figure 4. Error ratio for 300 nodes (left) and 400 nodes (right)

Figure 5 .

 5 Figure 5. Error ratio for 600 nodes (left) and 800 nodes (right)

Figure 6 .

 6 Figure 6. Average number of the received (left) and sent (right) packets

Figure 7 .Figure 7

 77 Figure 7. Average percentage of the battery consumption Figure 7 gives the average percentage of the battery consumption on one network node, based on the energy model of the MICA2 sensors. It shows that our algorithm is energy efficient because of the very low energy consumption during zone construction. The consumed energy does not exceed 3*10 -5 % of the battery's initial energy level.

TABLE I .

 I Three possible values for the packet subject are used in the algorithm: Next, we describe the use of each packet subject in the algorithm.

	INVITATION,	DISAGREEMENT,	BORDER	and
	NEW_NODE.

TABLE I . Fields of a control packet SrcId

 I

Global ID of the node sending the packet DestId Global ID of the destination node ZoneId Zone ID of the node sending the packet Subject Subject of the packet NodeType Type of the node sending the packet TTL Time To Live of the packet

table

  , part B: the node that receives an INVITATION packet treats it according to its state (assigned or not). BorderTable of the border nodes. When a new node joins the network, it has to broadcast a NEW_NODE packet in order to be assigned to a zone. Nodes that receive this packet answer by an INVITATION packet to its zone. As output, the node attributes (BoderTable, ZoneId and NodeType) are defined. The constructed zones are disjoint: every node belongs to only one zone (the first from which it receives an INVITATION packet).

	Nodes subjects (DISAGREEMENT or BORDER) in order to specify the node also exchange packets having other IF (n is an inviting node, it sends the INVITATION packet P only once) PART A : broadcast INVITATION packet P(n.nodeId, ANY, n.ZoneId, INVITATION, NORMAL, R) ENDIF PART B : when node n receives a packet P IF (P.Subject = INVITATION) IF (n.ZoneId undefined) join the zone (n.ZoneId := P.ZoneId) IF (P.TTL = 0) n.NodeType := BORDER broadcast a BORDER packet P'( n.NodeId, ANY, n.ZoneId, BORDER, n.NodeType, 1 ) RETURN ELSE broadcast an INVITATION packet P'( n.NodeId, ANY, n.ZoneId, INVITATION, n.NodeType, P.TTL -1 ) RETURN ENDIF ELSE IF (n.ZoneId = P.ZoneId) RETURN ELSE n.NodeType := BORDER broadcast a DISAGREEMENT packet P'( n.NodeId, ANY, n.ZoneId, DISAGREEMENT, n.NodeType, 1 ) n.BorderTable.add (P.ZoneId, P.SrcId) RETURN ENDIF ENDIF ENDIF type (NORMAL or BORDER) and to complete the INPUT : R IF (P.Subject = BORDER OR P.Subject = DISAGREEMENT)

IF (n.ZoneId = P.ZoneId) RETURN ELSE n.NodeType := BORDER broadcast a BORDER packet P'( n.NodeId, ANY, n.ZoneId, BORDER, n.NodeType, 1 ) n.BorderTable.add (P.ZoneId, P.SrcId) RETURN ENDIF ENDIF IF (P.Subject = NEW_NODE) send an INVITATION packet P'(n.NodeId, P.SrcId, n.ZoneId, INVITATION, n.NodeType, 1 ) RETURN ENDIF OUTPUT : NodeType

, ZoneId, BorderTable at node n


Qianxue Wang
email: qianxue.wang@univ-fcomte.fr

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

Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

A novel pseudo-random number generator based on discrete chaotic iterations

Keywords: Chaotic sequences, Topological chaos, Pseudorandom number generator, Statistical tests, Internet security, Discrete chaotic iterations

Security of information transmitted through the Internet, against passive or active attacks is an international concern. The use of a chaos-based pseudo-random bit sequence to make it unrecognizable by an intruder, is a field of research in full expansion. This mask of useful information by modulation or encryption is a fundamental part of the TLS Internet exchange protocol. In this paper, a new method using discrete chaotic iterations to generate pseudo-random numbers is presented. This pseudo-random number generator has successfully passed the NIST statistical test suite (NIST SP800-22). Security analysis shows its good characteristics. The application for secure image transmission through the Internet is proposed at the end of the paper.

I. INTRODUCTION

Nowadays, the world is highly computerized and interconnected, this leads to a growing interest in the use of digital chaotic 1 systems offering the possibility to reinforce the security of cryptographic algorithms, like those present in the Transport Layer Security protocol (TLS is an Internet exchange protocol). The advantage of the use of chaotic dynamics for security problems lies in their unpredictability character and in the mathematical theory of chaos. This theory brings many qualitative and quantitative tools, namely ergodicity, entropy, expansivity and sensitive dependence to initial conditions, these tools allow the study of the randomness of the disorder generated by the considered system.

Most of these new applications use chaotic maps as pseudorandom number generators to obtain a binary stream, for example, for symmetric encryption. Random number generators are essential in several fields like statistical studies, simulations (used for performance evaluations) or cryptography. They may be based on physical noise sources or on mathematical algorithms. However, in both cases, truly random numbers are not obtained because of data acquisition systems in the first case and machine precision in the second one. Instead, any real implementation actually produces a pseudo-random number generator (PRNG). Before using those generators in cryptographic applications, some strong requirements must be checked, for instance, they have to pass the up-to-date National Institute of Standards and Technology (NIST) statistical test suite [9], they should possess a long cycle length and a good entropy, etc. At the same time, the PRNG must also pass usual evaluations using traditional digital signal processing tools (autocorrelation function, crosscorrelation function and fast Fourier transform). 1 In this document, chaos means Devaney's topological chaos [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF] which implies a deterministic but unpredictable system very sensitive to its initial conditions.

The behaviors of chaotic dynamical systems are very similar to those of physical noise sources [START_REF] Schuster | Deterministic chaos -an introduction[END_REF]. Their sensitivity to initial conditions and their broadband spectrum make them good candidates to generate cryptographically secure PRNGs. Particularly, they have several basic properties that any good PRNG must possess: a long cycle length, strong randomness and entropy, speed, reproducibility, etc. However, chaotic dynamical systems are usually continuous and hence defined on the real numbers domain. The transformation from real numbers to integers may lead to the loss of the chaotic behavior. The conversion to integers needs a rigorous theoretical foundation.

In this paper, a new chaotic pseudo-random bit generator is presented, which can also be used to obtain numbers uniformly distributed between 0 and 1. Indeed, these bits can be grouped n by n, to obtain the floating part of x ∈ [0, 1] represented in binary numeral system. This generator is based on discrete chaotic iterations which satisfy Devaney's definition of chaos [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF]. A rigorous framework is introduced, where topological chaotic properties of the generator are shown. This generator successfully passes the whole NIST statistical tests. Moreover, because of its topological chaotic properties, this generator can be used for cryptographic applications.

The rest of this paper is organized in the following way. In Section II, some basic definitions concerning chaotic iterations and PRNGs are recalled. Section III is devoted to the new generator which is based on discrete chaotic iterations, all the design steps of this PRNG are described. In Section IV the results of some experiments and statistical tests are given. In Section V, some application examples are proposed in the field of Internet secure exchanges. Some conclusions and future work end the paper.

II. BASIC RECALLS

This section is devoted to basic notations and terminologies in the fields of chaotic iterations, Devaney's chaos and pseudorandom number generators.

A. Chaotic iterations

In the sequel 1; N means {1, 2, . . . , N }, s n denotes the n th term of a sequence s = (s 1 , s 2 , . . .), V i denotes the i th component of a vector V = (V 1 , V 2 , . . .) and f k denotes the k th composition of a function f ,

f k = f • ... • f k times (1)
Let us consider a system of a finite number N of cells, so that each cell has a boolean state. Then a sequence of length N of boolean states of the cells corresponds to a particular state of the system. A sequence which elements belong in 1; N is called a strategy. The set of all strategies is denoted by S.

Definition 1

Let S ∈ S. The shift function is defined by σ : (S n ) n∈N ∈ S -→ (S n+1 ) n∈N ∈ S and the initial function i is the map which associates to a sequence, its first term: i : (S n ) n∈N ∈ S -→ S 0 ∈ 1; N .

Definition 2

The set B denoting {0, 1}, let f : B N -→ B N be an iteration function and S ∈ S be a chaotic strategy. Then, the so-called chaotic iterations are defined by [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF] x 0 ∈ B N ,

∀n ∈ N * , ∀i ∈ 1; N , x n i = x n-1 i if S n = i f (x n ) S n if S n = i. (2)
In other words, at the n th iteration, only the S n -th cell is "iterated". Note that in a more general formulation, S n can be a subset of components and f (x n ) S n can be replaced by f (x k ) S n , where k n, describing for example delays transmission (see e.g. [1]). For the general definition of such chaotic iterations, see, e.g. [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF].

Chaotic iterations generate a set of vectors (boolean vector in this paper), they are defined by an initial state x 0 , an iteration function f and a chaotic strategy S.

B. Devaney's chaotic dynamical systems

Consider a metric space (X , d) and a continuous function f

: X -→ X . f is said to be topologically transitive, if for any pair of open sets U, V ⊂ X , there exists k > 0 such that f k (U ) ∩ V = ∅. (X , f
) is said to be regular if the set of periodic points is dense in X . f has sensitive dependence on initial conditions if there exists δ > 0, such that, for any x ∈ X and any neighborhood V of x, there exists y ∈ V and n 0 such that |f n (x)f n (y)| > δ. δ is called the constant of sensitivity of f . Quoting Devaney in [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], a function f : X -→ X is said to be chaotic on X if (X , f ) is regular, topologically transitive and has sensitive dependence on initial conditions.

When f is chaotic, then the system (X , f ) is chaotic and quoting Devaney it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And in the midst of this random behavior, we nevertheless have an element of regularity: fundamentally different behaviors are then possible and occurs with an unpredictably way.

The appendix gives the outline proof that chaotic iterations satisfy Devaney's topological chaos property. They can then be used to construct a new pseudo-random bit generator.

C. Low-dimensional chaotic systems

The dynamics of low dimension systems can be predicted using return map analysis or forecasting. Messages can thus be extracted from the chaos [START_REF] Robilliard | Enhancing the security of delayed differential chaotic systems with programmable feedback[END_REF]. In addition, its randomness nature is deteriorated when a finite precision arithmetic is used. The chaotic properties are reduced: some severe problems such as short cycle length, non-ideal distribution and high-correlation have been observed [START_REF] Kwok | A fast image encryption system based on chaotic maps with finite precision representation[END_REF].

Therefore, it is required to merge two or more low-dimensional chaotic systems, to form a composite one [START_REF] Li | Cryptanalysis of two chaotic encryption schemes based on circular bit shift and xor operations[END_REF][13][7] [START_REF] Pareek | Image encryption using chaotic logistic map[END_REF]. With respect to this requirement, a new method based on discrete chaotic iterations is proposed in the next section.

III. THE NOVEL GENERATOR BASED ON DISCRETE CHAOTIC ITERATIONS

The design of the new pseudo-random number generator based on discrete chaotic iterations, satisfying Devaney's chaos, is proposed and discussed. Detail operations of this approach are described in this section, while their performance will be presented in the next section.

A. Chaotic iterations as pseudo-random generator

The novel generator is designed by the following process. Let N ∈ N * , N 2. Some chaotic iterations are done, which generate a sequence (x n ) n∈N ∈ B N N of boolean vectors: the successive states of the iterated system. Some of those vectors are chaotically extracted and their components constitute our pseudo-random bit flow.

Chaotic iterations are realized as follows: initial state x 0 ∈ B N is a boolean vector taken as a seed, explained in Subsection III-D and chaotic strategy (S n ) n∈N ∈ 1, N N is constructed from a logistic map y (eq. 4 in Subsection III-B). Last, iterate function f is the vectorial boolean negation

f 0 : (x 1 , ..., x N ) ∈ B N -→ (x 1 , ..., x N ) ∈ B N .
To sum up, at each iteration, only S i -th component of state X n is updated, as follows

x n i =    x n-1 i if i = S i , x n-1 i if i = S i . (3)
Finally, let M be a finite subset of N * . Some x n are selected by a sequence m n as the pseudo-random bit sequence of our generator, where a sequence (m n ) n∈N ∈ M N is computed with y (eq. 6 in Subsection III-C). So, the generator returns the following values:

• the components of x m 0 , • following by the components of x m 0 +m 1 , • following by the components of x m 0 +m 1 +m 2 , • etc. In other words, the generator returns the following bits:

x m 0 1 x m 0 2 x m 0 3 . . . x m 0 N x m 0 +m 1 1 x m 0 +m 1 2 x m 0 +m 1 3 . . . x m 0 +m 1 N x m 0 +m 1 +m 2 1 x m 0 +m 1 +m 2 2
x m 0 +m 1 +m 2

3

... and its k th bit is x

P ⌊k/N⌋ i=0 mi k+1 (mod N) .
The basic design steps of the novel generator are also presented in flow chart form in Figure 1 (N • L is the length in bits of obtained sequence).

N = 5 and M = {4, 5} are adopted in the following subsections for easy understanding.

B. Chaotic strategy

Let y 0 ∈]0; 1[ be a real number deduced as a seed too (see Subsection III-D) and y = (y n ) n∈N ∈ [0, 1] the logistic sequence defined as bellow

∀n ∈ N, y n+1 = 4y n (1 -y n ) ( 4
)
Chaotic strategy is then the sequence (S n ) n∈N ∈ 1; 5 N equal to

C. Sequence m of returned states

Let us recall that m n is the number of iterations between the n th return of 5 pseudo-random bits and the following n + 1 th return. To define (m n ) n∈N , the chaotic sequence of equation 4 is used another time:

∀n ∈ N, m n = 4 if y n < 0.5 5 if y n 0.5 (6)

D. Parameters of the generator

The initial state of the system x 0 and the first term y 0 of the logistic map are seeded by the current time in seconds since the Epoch, or a number that the user inputs.

Different ways are possible. For example, let us denote by t the decimal part of the current time. So x 0 can be t (mod 32) written in binary digits (2 5 = 32 and the system is constituted by 5 bits) and y 0 = t.

E. Illustration example

In this example, the current time in seconds since the Epoch is 1237632934.484076. So, t = 484076, x 0 = t (mod 32) in binary digits, i.e. x 0 = (1, 0, 1, 0, 0) and y 0 = 0.484076.

Then

• y = 0.484076, 0.998985..., 0.004053..., 0.016146..., 0.063543.., 0.238022..., 0.725470..., 0.796651... • m = 4, 5, 4, 4, 4, 4, 5, 5, 5, 5, 4, 5, 4,... • S = 2, 4, 2, 2, 5, 1, 1, 5, 5, 3, 2, 3, 3,... Chaotic iterations are made with initial state x 0 , vectorial logical negation and strategy S, as shown in Table I, and m gives the states x n to return: x 4 , x 4+5 , x 4+5+4 , ....

In this situation, the output of the generator is: 10100111101111110011...

IV. STATISTICAL TESTS AND EXPERIMENTS

The security of the new scheme is evaluated via both theoretical analysis and experiments.

A. NIST statistical test suite

1) Presentation: Among the numerous standard tests for pseudo-randomness, a convincing way to show the randomness of the produced sequences is to confront them to the NIST (National Institute of Standards and Technology) Statistical Test: an up-to-date2 test suite by the Information Technology Laboratory (ITL).

The NIST test suite, SP 800-22, is a statistical package consisting of 15 tests. They were developed to test the randomness of (arbitrarily long) binary sequences produced by either hardware or software based cryptographic random or pseudo-random number generators. These tests focus on a variety of different types of non-randomness that could occur in a sequence.

2) Interpretation of empirical results: P is the tail probability that the chosen test statistic will assume values that are equal to or worse than the observed test statistic value when cosidering the null hypothesis. For each statistical test, a set of Ps is produced from a set of sequences obtained by our generator (i.e., 100 sequences are generated and tested, hence 100 Ps are produced). The interpretation of empirical results can be conducted in any number of ways. In this paper, the examination of the distribution of Ps to check for uniformity (P T ) is used.

The distribution of Ps is examined to ensure uniformity. If P T ≥ 0.0001, then the sequences can be considered to be uniformly distributed.

In our experiments, 100 sequences (s = 100), each with 1,000,000-bit long, are generated and tested. If the P T of any test is smaller than 0.0001, the sequences are considered to be not good enough and the generating algorithm is not suitable for usage.

Table II shows P T of the sequences based on discrete chaotic iterations using different schemes. If there are at least two statistical values in a test, the test is marked with an asterisk and the average value is computed to characterize the statistical values. Different schemes are using different lengths N of the iterated system and different sets M (range of m i which gives the states to return).

We can conclude from Table II that the worst situation is Scheme 1: it just can be observed that 3 out of 15 of the tests are failed. However, if we find a right combination of N and M (Scheme 6) a noticeable improvement is observed, and all the tests are passed.

B. Experiment results

The PRNG adopted in this section is Scheme 6 of Table II. The auto-correlation and cross-correlation of the symbolic sequence are also given in Figure 2. It can be seen that this sequence has δ-like auto-correlation which is required for a good PRNG. The sequences generated with different initial values will have zero cross-correlation due to the sensitive dependence on initial conditions.

The FFT of the sequence (Figure 3) is performed and the corresponding power spectrum is computed. A complete flat x 4 x 9

x 13 1 1

1 -→ 0 1 -→ 1 1 1 0 2 -→ 1 2 -→ 0 2 -→ 1 1 1 2 -→ 0 0 1 1 1 3 -→ 0 3 -→ 1 3 -→ 0 0 0 4 -→ 1 1 1 1 0 0 5 -→ 1 5 -→ 0 5 -→ 1 1 1 Output: x 0 1 x 0 2 x 0 3 x 0 4 x 0 5 x 4 1 x 4 2 x 4 3 x 4 4 x 4 5
x 9 1 x 9 2 x 9 3 x 9 4 x 9 5 x 13 1 x 13 2 x 13 3 x 13 4 x 13 5 ... = 10100111101111110011...

C. On the periodicity of chaotic orbit

Suppose the system is realized in k-bit finite precision (under fixed-point arithmetic) and then digital chaotic iterations are constrained in a discrete space with 2 k elements, it is obvious that every chaotic orbit will eventually be periodic [START_REF] Li | Analyses and New Designs of Digital Chaotic Ciphers[END_REF], i.e., finally go to a cycle with limited length not greater than 2 k .

The schematic view of a typical orbit of a digital chaotic system is shown in Figure 4. Generally, each digital chaotic orbit includes two connected parts: x 0 , x 1 , . . . , x l-1 and x l , x l+1 , . . . , x l+n , which are respectively called transient (branch) and cycle in this paper. Accordingly, l and n + 1 are respectively called transient length and cycle period, and 8) 1100( 12) 1111(15) 0111( 7) 0001(1) 0000(0) 1100( 12) 1110( 14) 0111( 7) 0011(3)...

V. AN APPLICATION EXAMPLE OF THE PROPOSED PRNG

Cryptographically secure PRNGs are fundamental tools to communicate securely through the Internet.

For example, in order to guarantee security of image transmission, the previous pseudo-random sequence can be used to encrypt the digital image (one-time pad encryption). The original image and the encrypted image are shown in Figures 5(a The generator presented in this paper has passed the whole NIST800-22 statistical test suite, so it can reasonably be considered as a possibly usable PRNG. We believe that this generator can also be used for cryptographic applications, because of its topological chaos quality. Indeed, it is proved in [2] that Devaney's chaos property is satisfied by the discrete chaotic iterations: they are regular, transitive and sensitive to initial conditions.

Because of transitivity, the discrete dynamical system cannot be decomposed: the behavior of the system cannot be reduced to the study of one of its parts. As a consequence, the knowledge of a part of the private key (or the encrypted image) cannot help an hypothetical attacker to guess the whole key (image). Moreover, the sensitiveness conducts to the fact that, even if the attacker tries anyway to decrypt the cypher message by attempting to complete the part in his possession, he cannot succeed.

Last the regularity participates to an increase of the randomness of our generator and conducts to the impossibility of the prediction of its future evolution. Two very similar sequences can have completely different behaviors after some iterations, the first can quickly enter into a cycle whereas the second can follow a more divergent trajectory. Thus, two different seeds generate completely different keys.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, a novel pseudo-random generator based on discrete chaotic iterations is proposed. Different schemes are used to generate this chaotic sequence. A particular scheme (Scheme 6) offers a sufficiently secure randomness for cryptographic applications. The proposed PRNG is based on a rigorous framework. In addition, a detailed statistical analysis concerning the numbers produced by this method is given. These experimental results lead us to conclude that our generator is a very good and reliable PRNG and that chaotic iterations can be used in computer science security field [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF].

In future work, different random sequences will be used in place of logistic map, the influence of N and the range M of m j for the output sequence will be explored and other iteration functions will be studied. New applications in computer science field will be proposed, specially in the security and cryptography domains.

Figure 1 .

 1 Figure 1. Flow chart of chaotic strategy

Figure 2 .

 2 Figure 2. The auto-correlation and cross-correlation of the pseudo-random sequence

Figure 3 .

 3 Figure 3. The FFT of the pseudo-random sequence

Figure 4 .

 4 Figure 4. A pseudo orbit of a digital chaotic system

  ) and 6(a). Figures5(b) and 6(b) depict the histograms. It can be seen that the distribution of the encrypted image is very close to the uniform distribution, which can well protect the information of the image to withstand the statistical attack. TLS protocol is another example in which cryptographically secure PRNGs are needed, during the generation of private key for symmetric cypher. This generation requires a high quality of the randomness for the PRNG.

Figure 6 .

 6 Figure 5. Distribution of original image

A new version of the Statistical Test Suite (Version 2.0) has been released in August 25, 2008.

APPENDIX

In this appendix we give outline proofs of the properties on which our pseudo-random number generator is based.

Denote by δ the discrete boolean metric, δ(x, y) = 0 ⇔ x = y. Given a function f , define the function

, where + and . are the boolean addition and product operations.

Consider the phase space: X = 1; N N × B N and the map

then the chaotic iterations defined in (II-A) can be described by the following iterations

Let us define a new distance between two points (S, E), ( Š, Ě) ∈ X by d((S, E); ( Š, Ě)) = d e (E, Ě) + d s (S, Š), where

It is then proved in [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF] by using the sequential continuity that Proposition 1 G f is a continuous function on (X , d).

Then, the vectorial negation f 0 (x 1 , . . . , x N ) = (x 1 , . . . , x N ) satisfies the three conditions for Devaney's chaos, namely, regularity and transitivity and sensitivity in the metric space (X , d). This leads to the following result.

Proposition 2 G f0 is a chaotic map on (X , d) in the sense of Devaney.