Alain Bonardi
email: alain.bonardi@ircam.fr

INTRODUCING FUZZY LOGIC AND COMPUTING WITH WORDS PARADIGMS IN REALTIME PROCESSES FOR PERFORMANCE ARTS

When trying to introduce qualitative information into processes for performance arts, two major points must be considered: how to really deal with qualitative data and how to insert this into the processes. We propose to design a library for Max/MSP with the aim of offering a wide and full range of tools to be able to reason with all kinds of qualitative concepts. The idea is to implement inside Max/MSP the well-known fuzzy logic concepts, considering the numerous ways to represent imprecise data.

INTRODUCTION

Fuzzy logic is often confused with fuzzy control. People have heard of autonomous control of such devices as boilers, cars or watering systems, and this is often considered as the alpha and omega of fuzzy logic. Even in the academic field, some open source fuzzy logic libraries in fact deal with fuzzy control. It is for instance the case of jFuzzyLogic [START_REF] Jfuzzylogic | Open source fuzzy logic library and fcl language implementation[END_REF] or Free Fuzzy Logic Library [START_REF] Ffll | Free fuzzy logic library[END_REF]. Between fuzzy logic and fuzzy control, there are of course many common points but also differences: fuzzy control uses fuzzy logic concepts, that are specialized to optimize the computerized implementation [START_REF] Bouchon-Meunier | La logique floue et ses applications[END_REF]. In fuzzy control, observed facts are precise, represented as singletons and therefore the generalized modus ponens is reduced to fuzzy implication; moreover fuzzy implications are based on AND conjunction: € A ⇒ B is translated into A AND B, which is implemented either by a min (Mamdani implication) or product operation (Larsen implication). This approach does not enable for instance to deal with the equivalence in classical logic between € A ⇒ B and € B ⇒ A, which requires other fuzzy implications, for instance Reichenbach, Willmott or Rescher-Gaines ones.

In the field of real-time interactive music, fuzzy logic has nearly been absent from research and development efforts. A few authors have proposed Max/MSP patches to enable the use of some AI techniques. As an example, in a recent work [START_REF] Eigenfeldt | Drum Circle: Intelligent Agents in Max/MSP[END_REF] Eigenfeldt describes methods to create networked multi-agents within Max/MSP and also some fuzzy logic ratings for a drum ensemble. Less recently Elsea [START_REF] Elsea | Fuzzy Logic and Musical Decisions[END_REF] explains how the core concepts of fuzzy logic and fuzzy control may be applied to problems of musical decisions, for instance chord inversions.

Knowing that the Computing with Words (CW) [START_REF] Zadeh | From computing with numbers to computing with words: From manipulation of measurements to manipulation of perceptions[END_REF] paradigm has shown to fit very well all kinds of human expressions (feelings, perceptions, emotions, impressions, believes, etc.) we are interested in introducing these concepts in the world of real-time processes for performing arts. Our research is based on two concurrent tasks: exploring the necessary concepts in fuzzy logic being not limited to fuzzy control; identifying case studies showing the relevance of fuzzy approaches and concepts. This double approach led us to specify and develop our own fuzzy library adapted to real-time formalisms and opened beyond fuzzy control. It is named FuzzyLib. At the same time we started using it for precise applications: first, for the semantic control of effects in a theatre play; secondly, for fuzzy filtering and decision in gesture recognition.

In this paper, we will first of all recall the design of our fuzzy logic library for Max/MSP before explaining the novelties to overcome the simple fuzzy control. We then present two case studies where it was used. Last but not least, we will evoke future work.

FUZZYLIB, A FUZZY LOGIC LIBRARY FOR MAX/MSP

We have developed a software library named FuzzyLib for the realtime environment Max/MSP [START_REF] Bonardi | Designing a library for computing [performances] with words[END_REF]. This library is currently available on Internet at http://imtr.ircam.fr. We have designed three objects that correspond to three levels of fuzzy logic: fuzzification, reasoning and defuzzification, fuzzy rule expression. We present these three objects and then give the main features of the library.

Linguistic variable handling for fuzzification

The first step in fuzzy logic is fuzzification. The purpose is the semantic representation of a phenomenon usually handled with digital values. Thanks to a range of values provided by an expert and to a certain (generally odd) number of fuzzy subsets, one can represent this phenomenon as a linguistic variable.

We have designed an object named lv, which stands for 'linguistic variable'. A screenshot of its help patch is given on figure 1, and shows the fuzzification of the quantity of movement of a performer using five fuzzy subsets: 'still', 'nearlyStill', 'slightlyMoving', 'moving', 'veryMoving'. These labels are provided by the user thanks to the outFormat message entering the left input of the object. The right input collects the numerical boundaries (in our case from 0 to 127) of the variable as supposed to be known by an expert. On the right frame of the patch, one can see the various parameters of the object, mainly the shape of fuzzy subsets (triangular or trapezoidal) and the type of partitioning. We have implemented two partitioning possibilities: either uniform or based on an algorithm already published for automatic partitioning according to training data [4] [5]. This option is interesting to quickly set a linguistic variable from a set of training data.

A module for linguistic variable and fuzzy subset graphical display has also been developed. It receives data from the 'lv' object and displays fuzzy subsets and the current value of the variable.

Reasoning and defuzzification level

Reasoning is computed thanks to the generalized modus ponens that enables to solve the following syllogism: if we assume € A ⇒ B and we get A' close to A as input, what should the answer B' be? We have developed an object named gmpa for Max/MSP, which stands for 'generalized modus ponens application'. A screenshot of its help patch is given on figure 2. The 'gmpa' object receives both:

data from 'lv' objects: declaration of new linguistic variables, removal of previous variables.

fuzzy rules connecting input linguistic variables with output linguistic variables. The rules are expressed as Max/MSP messages. The object also provides defuzzification (by barycentre or maximum methods) for linguistic variables implied as consequents of fuzzy rules. The user has to choose the fuzzy implication and the t-Norm and t-CoNorm to be handled (on the screenshot, Reichenbach fuzzy implication has been selected, whereas Min() and Max() have been chosen as t-Norm and t-CoNorm.

An assistant for fuzzy rule composing

We also have implemented an interface object named ruleComposer, associated with the 'gmpa' object to help users to write fuzzy rules and avoid syntax errors. This object automatically collects the names of the linguistic variables declared with 'lv' objects and provides help to write fuzzy rules. Figure 3 gives a screenshot of its patch.

Main features of FuzzyLib

FuzzyLib provides realtime fuzzy logic handling. As we said in the introduction of the paper, our purpose is to design a framework that fits Max/MSP paradigm and also is not limited to fuzzy control. In that purpose, we include the computation of all classical fuzzy implications proposed by literature. Classical t-Norms and t-CoNorms are also implemented.

For its first version, we have made a simplification to quickly sketch the environment. We have considered all measures provided by captors as precise ones. In this case, the General Modus Ponens computation is limited to the fuzzy implication involved, and that enables less complex algorithms.

It means this first version of FuzzyLib overcomes fuzzy control on the implication side, but it does not implement yet the full fuzzy logic paradigm with imprecise measures as input. This will be implemented in version 2 after studying the optimization of computation of the generalized modus ponens [START_REF] Dubois | Practical computing in fuzzy logic[END_REF] [15].

TWO CASE STUDIES OF APPLICATION

Semantic control of a crowd generator

To put in practice our library, we have proposed to M. Bataille-Testu, the stage director of a theatre play called Les petites absences, to use it during a show, with the imperative constraint of realtime.

He used Max/MSP enhanced with our FuzzyLib to control a crowd sound generator that would fit the behavior of the main actor from a video and voice capture and analysis. As a non-specialist, he could very easily define rules to be activated depending on the cases he wanted to point out. Two levels of fuzzy rules were used: first one to identify voice and motion particular states; the second one to map these states to the control of the audio crowd generator. The result is very encouraging since the stage director was able to overcome his difficulties to develop directly in Max/MSP; and the play has continuously been performed since december 2008 with a satisfying (especially for the artistic team) fuzzy-driven interaction.

Fuzzy decision and filtering in gesture recognition and following

We have outlined another application of the FuzzyLib that consists in coupling HMM-based gesture recognition and following with fuzzy filtering and decision. We have experimented character recognition in handwriting starting from previous work at IRCAM by Bevilacqua & al. [START_REF] Bevilacqua | Wireless sensor interface and gesturefollower for music pedagogy[END_REF] implementing in Max/MSP HMM gesture recognition and following: the decoding of the result following the various likelihood curves is neither easy nor convenient. Generally users take into account the result given at the very end of the process. We have added a fuzzy level that receives instantaneous information about the likeliest gesture and its likelihood during the gesture presented. It enables to filter with fuzzy decisions non-significant fragments of gestures, and to provide a synthetic semantic abstract of the gesture.

For instance, we have learnt three characters in the system: 'c', 'o' and 'b'. Figure 4 shows the abstract generated when drawing a 'c': "At the beginning of the movement the likeliest was the first half of gesture #1" (gesture # 1 is 'c'). It is a kind of semantic overview of the gesture. Figure 5 shows the abstract generated when drawing an 'o', which is ambiguous since the beginning is the same as with the 'c': "At one half of the movement, the likeliest was the third quarter of gesture #1 ('c'). At four fifths of the movement, the likeliest was the last quarter of gesture #2 ('o')". We can easily imagine applications of this kind of systems to interactive device that would assist dancers or musicians in learning precise gestures. Next step of this research will consist not only in following the likeliest gesture but the various features of all the gesture models when presenting a new gesture.

Necessity of a full implementation of fuzzy logic paradigms

For simple mapping between input and output values, a simple fuzzy control is sufficient, and FuzzyLib is perfectly suitable for that.

There are however applications that would require a full implementation of fuzzy logic paradigms especially of the generalized modus ponens:

-Situations handling imprecise values as inputs. This can be due to many reasons: bad quality of sensors, low frequency of measures, etc.

-Imprecise reasoning: as soon as we handle an intermediary level of variables between input and output ones, we need to handle fuzzy subsets and not only precise values. For instance, in Les petites absences, we build an intermediary variable named performerGlobalPosition from such input variables as the bounding box stretching, etc. At present time, since we cannot handle imprecise values we need to fuzzify and defuzzify all values coming in and out variables, passing only numerical values to other variables.

We should be able with the version 2 of FuzzyLib to pass fuzzy subsets between modules. -Situations handling particular values as inputs, especially input values coming directly from humans (i.e. expressed through linguistic assessments). In these situations, only words are available, no fuzzy sets. Two different formalisms has been proposed, one in [START_REF] Herrera | A 2-tuple fuzzy linguistic representation model for computing with words[END_REF] and the other in [START_REF] Ffll | Free fuzzy logic library[END_REF], to handle words directly without the help of an expert: words are proposed on a scale (with balanced or unbalanced term sets) and the whole process for the reasoning seems to be transparent, giving finally an outcome as a word or possibly a fuzzy number. However only aggregation and comparison tools have been studied and proposed, so one has to look for the best combination between those tools to propose a convenient reasoning for our framework.

CONCLUSION

In this paper we have recalled the spirit of our work since the very first version of our fuzzy library FuzzyLib. The current version goes further than the simple fuzzy control in proposing all the implication operators that exist in the literature. We have seen that in practice the FuzzyLib is very useful and corresponds to a real need. That is why we will continue this work by proposing an end-to-end linguistic treatment of the fuzzy inference, including all kinds of input values; an approach that could better match user's needs and intentions.

Figure 1 .

 1 Figure 1. A screenshot of the help patch of the 'lv' object (Linguistic Variable).

Figure 2 .

 2 Figure 2. A screenshot of the help patch of the 'gmpa' object (Generalized Modus Ponens Application) connecting two linguistic variables (qom and freq) and taking into account fuzzy rules.

Figure 3 .

 3 Figure 3. A screenshot of the help patch of the 'ruleComposer' object.

Figure 4 .

 4 Figure 4. A screenshot of the gesture recognition and following patch, in the situation of handwriting a 'c'.

Figure 5 .

 5 Figure 5. A screenshot of the gesture recognition and following patch, in the situation of handwriting an 'o'.


Samir Medjiah
email: medjiah@labri.fr

Toufik Ahmed

Hamid Asgari
email: hamid.asgari@thalesgroup.com

Streaming Multimedia over WMSNs: An Online Multipath Routing Protocol

Keywords: WSN, WMSN, Online Multipath Routing, Geographic Routing, Angle Routing, Multipath Routing, Energy Aware routing

Routing has become an important challenge to Wireless Multimedia Sensor Networks (WMSNs) from the standpoint of supporting multimedia applications due to the constraints on energy and computational capabilities of sensor nodes, and acquiring of the global network knowledge for disseminating packets to nodes. In this paper, we propose an online multipath routing protocol for use in WMSNs. The proposed protocol uses sensor nodes' positions to make packet-forwarding decisions at each hop. These decisions are made in real-time, in such a way that there is no need for having the knowledge about the entire network topology. This new routing protocol achieves load-balancing of traffic and minimizes energy consumption among nodes by using: (1) smart greedy forwarding scheme based on adaptive compass for selecting the most appropriate next hop for forwarding the traffic and (2) walking back forwarding scheme to bypass network holes. Performance comparison of the proposed protocols with Two-Phase Geographical Greedy Forwarding (TPGF) and Greedy Perimeter Stateless Routing (GPSR) shows that they: (a) maximize the overall network lifespan by not draining energy from some specific nodes, (b) provide quality of service delivery for video streams by influencing the best node along the route to destination, and (c) scale better in densely deployed wireless sensors network.

Introduction

With the advancement in miniaturization and the availability of low-cost hardware, the computing nodes embed various kinds of sensing and capturing elements including microphones and video cameras. Hence, the use of ubiquitous Wireless Multimedia Sensor Networks (WMSNs) is becoming a reality [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF][START_REF] Gurses | Multimedia Communication in Wireless Sensor Networks[END_REF][START_REF] Misra | A Survey of Multimedia Streaming in Wireless Sensor Networks[END_REF][START_REF] Shu | Multimedia over Sensor Networks[END_REF]. WMSNs are generally used for surveillance applications, intrusion detection, environmental and building monitoring, etc. These applications imposes additional challenges such as energy-efficient data processing both within node and innetwork, audio/video bandwidth/rate adaptation to overcome the variations in networking conditions, Quality of Service (QoS) delivery to meet application specific requirements and routing and selecting appropriate paths for continual delivery of multimedia streams. Due to the distributed and dynamic nature of these types of networks, the design of a critical information infrastructure based on a WMSN raises many other challenges such as ensuring confidentiality and the integrity of the data stream, providing the means for node authentication and access control, securing routing and node grouping [START_REF] Aivaloglou | Trust Establishment in Sensor Networks: Behavior-based, Certificate-based, and a Combinational Approach[END_REF]. Among all these challenges, our work focuses on the routing and path selection issues taking into account energy constraints and QoS delivery needs.

Generally, routing in wireless sensor networks (WSN) is a challenging task. A comprehensive survey of routing protocols in WSN is given in [START_REF] Al-Karaki | Routing techniques in wireless sensor networks: a survey[END_REF]. A large number of research works exists to enable energy efficient routing in WSN. In fact, we can find different routing techniques that try to achieve energy-efficiency and to provide a best quality of service. One example is the multi-channel transmission in WMSNs. In [START_REF] Vassis | Performances Evaluation of Single and Multi-Channel Actor to Actor Communication for Wireless Sensor Actor Networks[END_REF], authors have evaluated the performances of routing (routing delays) when using a single and multi-channel communications in a wireless sensor and actor networks. The authors showed that the multi-channel scheme performs better than the single channel scheme especially for higher volumes of generated traffic putting the light on the important need to parallel transmissions in a wireless multimedia sensor network, where delay and packets loss are stringent constraints.

In higher layers of the communication protocols stack, performances evaluations of routing protocols for WMSNs suggests multipath routing approach to maximize the throughput of streaming multimedia traffic. This is to utilize diverse paths to route packet streams towards the destinations in order to avoid draining the energy of nodes along a specific route. In [START_REF] Li | Efficient Multi-path Protocol for Wireless Sensor Networks[END_REF], the authors propose a multipath routing protocol based on the well known routing protocol Directed Diffusion [START_REF] Intanagonwiwat | Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks[END_REF] that reinforces multiple routes with high link quality and low latency. In [START_REF] Vidhyapriya | Energy Efficient Adaptive Multipath Routing for Wireless Sensor Networks[END_REF], the authors focused on two key questions regarding multipath routing in WMSNs: (a) how many paths are needed? And (b), how to select these paths? The authors then proposed a multipath routing mechanism in order to provide a reliable transmission environment with low energy consumption by utilizing the energy availability and the received signal strength of the nodes to identify multiple routes from the source to the destination. In [START_REF] Maimour | Maximally Radio-Disjoint Multipath Routing for Wireless Multimedia Sensor Networks[END_REF], the author addresses the problem of interfering paths in a WMSN and considers both intra-session as well as inter-session interferences. The author proposes an incremental path creation mechanism where additional paths are set up only when required (typically in case of congestion or bandwidth shortage). In [START_REF] Huang | Multiconstrained QoS Multi-path Routing in Wireless Sensor Networks[END_REF], authors propose MCMP (MultiConstrained MultiPath) routing protocol in order to guarantee a better QoS in terms of delay and reliability. Unlike end-to-end QoS schemes used in WSNs, the authors utilize a multiple paths creation mechanism based on local link information. Other examples of multipath routing protocols for WMSNs include: MPMPS (Multi-Priority Multi-Path Selection) (Zhang et. al, 2008) and TPGF (Two-Phase Geographical Greedy Forwarding) (Shu et. al, 2008). However, these "offline multipath" protocols have to explore the multiple routes that may exist between the source and the destination before the actual data delivery phase. They may not be well adapted for large-scale highly dense network deployments and for networks with frequent node mobility.

Geographic routing is the process in which each node is aware of its geographic coordinates and uses the position of packet's destination to perform routing decisions. These types of routing scales better for WSNs. Greedy Perimeter Stateless Routing (GPSR) [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF] was defined as a geographic routing protocol in order for the network to scale in large size networks, i.e., to accommodate a large number of nodes having very low exchange of route state information and maintenance. The advantage of this protocol is that each node only gathers the topology information about its immediate neighbors. Thus, its greedy forwarding relies on local-knowledge for selecting the closest next hop node to the destination. This process ends up with continuous selection of the same path that leads to fast depletion of the energy of the nodes along the selected route and premature dying of these nodes.

In this paper, we examine the benefit of geographic routing along with "online" multi-path route selection process (i.e. multiple routes are created as packets advance towards the destination) and propose a new routing protocol called AGEM (Adaptive Greedy-compass Energy-aware Multipath) that takes into account both node's energy constraints and QoS needs of audio and video streams. The design of AGEM is driven by the following factors:

1

Alternative paths: multimedia applications are delay sensitive and have delay and delay variation constraints. Multimedia traffic should be delivered satisfying these requirements. In typical networks, shortest paths are heavily used for the delivery of this traffic types whereas other appropriate routers that could satisfy these traffic requirements are underutilized.

2

Load balancing: In order to maximize the lifetime of WSN nodes and to avoid depletion of nodes' energy and consequently node's failures, load balancing and multi-path delivery across the network must be considered during the design of a routing protocol.

3
Multipath transmission: Packets in a multimedia stream are generally large in size and the transmission requirements can be several times higher than the maximum transmission capacity of sensor nodes if a single path is used for routing these packets. 4

Online decisions: As the topology may change from time to time, it is more appropriate to make the routing decisions in a distributed manner and in real-time. This is due to the fact that offline routing processes cannot react to topology changes and result in forwarding packets to unavailable nodes or towards disconnected routes.

5

Node selection process: in densely deployed networks, different neighbors may be selected as candidate for packet forwarding. To deduce an appropriate selection, the node selection process should take into account, node's energy, its distance to the destination and packet's QoS requirements. The rest of this paper is organized as follows. Section II reviews the related work in the area of WSN routing that influenced the design of our proposed protocol. Section III presents the functionalities of proposed AGEM protocol. Section IV provides the results of performance evaluations of our proposed protocol in comparison with GPSR. Finally, section V presents our conclusions.

Related Work

In geographic routing, two greedy schemes are used to make packets progress towards the destination node. Greedy progression scheme based on distance to the destination node [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF][START_REF] Stojmenovic | GEDIR: Loop Free Location Based Routing in Wireless Communication Network[END_REF][START_REF] Li | A Scalable Location Service for Geographic Ad Hoc Routing[END_REF][START_REF] Stojmenovic | Position-based Routing in Ad Hoc Networks[END_REF] and greedy progression based on angular offset in the direction towards the destination node [START_REF] Kranakis | Compass Routing on Geometric Networks[END_REF][START_REF] Morin | On line routing in geometric graphs[END_REF][START_REF] Urrutia | Routing with guaranteed delivery in geometric and Wireless Networks[END_REF]. In both schemes, a route between source and destination is progressively chosen only based on node-level forwarding decisions made locally at each hop. For WMSNs, two important protocols have been proposed that make use of node positions for packet forwarding i.e., GPSR and MPMPS. MPMPS is itself based on TPGF. These protocols are further explained below.

The GPSR Routing Protocol

The GPSR (Greedy Perimeter Stateless Routing) [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF] was originally designed for MANETs but rapidly adapted for WSNs. The GPSR algorithm relies on the correspondence between the geographic location of nodes and the connectivity within the network by using the location position of nodes to forward a packet. Given the geographic coordinates of the destination node, the GPSR algorithm forwards a packet to destination using only one single hop location information. It assumes that each node knows its geographic location and geographic information about its direct neighbors. This protocol uses two different packet forwarding strategies: Greedy Forwarding and Perimeter Forwarding. When a node receives a packet destined to a certain node, it chooses the closest neighbor out-of itself to that destination and forwards the packet to that node. This step is called the Greedy Forwarding. In case that such node cannot be found, (i.e. the node itself is the closest node to the destination out-of its neighbors but the destination cannot be reached by one hop), the Perimeter Forwarding will be used. The Perimeter Forwarding occurs when there is no neighbor closest to Destination (D) than node (A) itself. Figure 1 illustrates that node A is closer to D than its neighbors x and y. This situation is called "voids" or holes. Voids can occur due to random nodes deployment or the presence of obstacles that obstruct radio signals. To overcome this problem, Perimeter Forwarding is used to route packets around voids. Packets will move around the void until arriving to a node closest to the destination than the node which initiated the Perimeter Forwarding, after which the Greedy Forwarding takes over. By maintaining only information on the local topology, the GPSR protocol can be suitable for WSNs. However, the greedy forwarding leads to choose only one path from the source to the destination.

The TPGF Routing Protocol

TPGF (Two Phase geographical Greedy Forwarding) (Shu et. al, 2008) routing protocol is the first to introduce multipath concept in wireless multimedia sensor networks (WMSNs) field. This algorithm focuses in exploring and establishing the maximum number of disjoint paths to the destination in terms of minimization of the path length, the end-to-end transmission delay and the energy consumption of the nodes. The first phase of the algorithm explores the possible paths to the destination. A path to a destination is investigated by labeling neighbors nodes until the base station. During this phase, a step back and mark is used to bypass voids and loops until successfully a sensor node finds a next-hop node which has a routing path to the base station. The second phase is responsible for optimizing the discovered routing paths with the shortest transmission distance (i.e. choosing a path with least number of hops to reach the destination). The TPGF algorithm can be executed repeatedly to look for multiple node disjoint-paths. It's worth to note that TPGF is an offline multipath routing protocol.

The MPMPS Routing Protocol

The MPMPS (Multi-Priority Multi-Path Selection) (Zhang et. al, 2008) protocol is an extension of TPGF. MPMPS highlights the fact that not every path found by TPGF can be used for transmitting video because a long routing path with long end-to-end transmission delay may not be suitable for audio/video streaming. Furthermore, because in different applications, audio and video streams play different roles and the importance level may be different, it is better to split the video stream into two streams (video/image and audio). For example, video stream is more important than audio stream in fire detection because the image reflects the event, audio stream is more important in deep ocean monitoring, while image stream during the day time and audio stream during the night time for desert monitoring. Therefore, we can give more priority to the important stream depending on the final application to guarantee the using of the suitable paths.

Policies for Greedy forwarding

In literature, there are different policies that can be used in geographic routing and for the selection of the next hop node. To illustrate these policies, let take 'u' as the current forwarder node and 'd' the destination node, then we can define these routing policies (see Figure 2): 1

Compass routing: See Figure 2(a) -The next relay node is ' ' such that the angle is the smallest among all neighbors of ' ' [START_REF] Kranakis | Compass Routing on Geometric Networks[END_REF].

2

Random compass routing: See Figure 2(b) -Let ' ' be the node above line ( ) such that is the smallest among all such neighbors of ' '. Similarly, define ' ' to be node below line ( ) that minimize the angle . Then, node ' ' randomly chooses ' ' or ' ' to forward the packet [START_REF] Kranakis | Compass Routing on Geometric Networks[END_REF].

3

Greedy routing: See Figure 2(c) -The next relay node is ' ' such that the distance ‖ ‖ is the smallest among all neighbors of ' ' [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF].

4
Most forwarding routing (MFR): See Figure 2 [START_REF] Bose | Online Routing in Triangulations[END_REF][START_REF] Morin | On line routing in geometric graphs[END_REF].

Discussion on routing/forwarding

Paths are selected a priori by protocols such as TPGF and MPMPS. In such cases, paths are chosen in advance from the source to the destination. Knowing the full map of the deployed network to perform routing as done by most "offline multipath" routing protocols is not suitable for many reasons: (1) the exchange of the network map is energy consuming, (2) the map may not reflect the current network topology, and (3) nodes' failure can be more frequent in WSN than in other ad-hoc networks. These reasons cause routing problems. In GPSR protocol, packets are forwarded hop by hop based on information available local to node i.e., the use of "Greedy routing" policy. GPSR seems to be more promising to scale to large network but does not achieve load balancing by making use of multiple routes.

Hence, we propose a new geographical and online routing protocol called AGEM that (1) selects neighbor nodes using an adaptive compass mechanism which is a newly defined policy, (2) routes packets on multiple paths using greedy routing policy for load balancing purposes, and (3) avoids network holes using walking back forwarding.

AGEM Routing Protocol

The main idea behind AGEM protocol is to include a loadbalancing feature while being a greedy geographic routing protocol in order to increase the lifetime of the network and to reduce the queue size in the most used nodes across the network. While using a pure greedy routing protocol like GPSR, data/video streams always use the same route. In AGEM routing protocol, data/video streams are routed using different paths. At each hop, a forwarder node decides to which neighbor to send the packet. The forwarding policy at each node is based on the following four parameters: (1) the residual energy at node, (2) the number of hops visited by the packet before it arrives at this node, (3) the distance between the node and its neighbors, and (4) the history of the packets forwarded belonging to the same stream. Furthermore, only a subset of available neighbors is chosen according to the new adaptive compass selection mechanism.

The AGEM routing protocol has two modes, the Smart Greedy Forwarding and the Walking Back Forwarding. The first mode is used when there is always a neighbor node closer to the destination node than the forwarder node. The second mode is used to get out of a blocking situation in which the forwarder node can no longer forward the packet towards the destination node.

Figure 3 presents an overview diagram of AGEM routing mode switching.

The following section will explain the two routing modes.

Figure 3 GEAMS Routing mode switching.

Walking Back Mode

Smart Greedy Mode

CN : Number of Closer Neighbors to the Sink

CN > 0 CN = 0

Smart Greedy forwarding mode:

AGEM is a geographic routing protocol where the nodes are aware of their geographic coordinates. This information can be obtained using a positioning system such as GPS or by using distributed localization techniques such as DV-Hop [START_REF] Niculescu | DV Based Positioning in Ad hoc Networks[END_REF], Amorphous [START_REF] Nagpal | Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network[END_REF], etc.

In AGEM routing protocol, each sensor node keeps track of related information about its immediate neighbors and stores the information that includes the estimated distance to its neighbors, the distance of the neighbor to the destination, the data-rate of the links, and the remaining energy of neighbors. This information is updated by the mean of beacon messages propagated locally, scheduled at fixed adjustable intervals. Relying on this information, a forwarder node will give a score to each neighbor according to a function (i.e. "f(x)").

Since AGEM protocol is an online protocol and relies on beacon exchange for neighborhood state maintenance, AGEM can be used for static or mobile sensor networks. Since AGEM routing algorithm is based on geographic coordinates, distance-based greedy progression is used along angle-based greedy progression for next hop node selection. So, not all the neighbors closest to the destination than the forwarder node are going to be selected as the candidates for packet forwarding. This set of nodes is reduced to only include those nodes with best angular offset towards the destination.

At the beginning, the forwarder node chooses only neighbor nodes that are within an angular (α) view towards the destination with an initial angle of α 0 (e.g., α = α 0 <30°). A minimum of "n" neighbor nodes (neighboring set with n>=2) must be found to perform load balancing. If n=1 then there is just one node set where no load balancing can be achieved. If no node is found, the angle α is incremented by Δα (e.g., Δα =10°) until it reaches 180°. At this stage, if no node is found then a walking back forwarding is needed since the forwarder is facing a hole. Figure 4 illustrates this adaptive forwarding policy. Figure 4 AGEM adaptive compass policy. Choosing a node from the neighboring set to forward a packet will depend on the score given to each node according to the "f(x)" function (see Figure 5). The f(x) considers the energy consumption which is defined in the following subsection.

Figure 5 One-hop neighbors sorted according to their scores.

Sink Source

one-hop Neighbors

Forwarder Node

Neighbor N1

Neighbor N2

Neighbor Nm

Packet energy consumption : When a node ( ) sends a packet ( ) of bits size to a node ( ), the energy of node ( ) will decrease by ( ̅̅̅̅ ) while the energy of the node will decrease by ( ). Consequently, the cost of this routing decision is ( ̅̅̅̅ ) ( ) considering the energy of the whole network. Figure 6 illustrates this energy consumption. We assume that the transmitted data packets in the network have the same size. We propose an objective function to evaluate a neighbor for packet forwarding. This objective function takes into account the packet energy consumption and also the initial energy of that neighbor. The proposed objective function can simply be:

( ) ( )

Where:

( ) is the estimated energy to transmit a data packet through a distance D, and is the estimated energy to receive the data packet.

These two functions rely on the energy consumption model proposed by [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF]. According to this model, we have:

( ) ( ) ( )
Where: is the size of the data packet in bits, is the transmission distance in meters, is the energy consumed by the transceiver electronics, is the energy consumed by the transmitter amplifier.

was taken to be and . Upon receiving a data packet from the source node , the forwarder node retransmits the packet to a neighbor that is closest to the destination node and in such a way that the number of hops the packet traversed, will meet the rank of that neighbor (neighbors are ranked according to their score). The main idea is to forward a packet with the biggest number of hops through the best neighbor, and consequently a packet with the smallest number of hops is routed through the worst neighbor to allow a proper load balancing in the network (see Figure 8 and Figure 9). Figure 7 describes an algorithm as the forwarding policy. For each known source node a forwarder node (N) maintains a pair (

).

represents the mean hop count that separates from N, and j represents the neighbor (Nj) whom score (i.e. f(x) function) is closest to the average score of all closest nodes to the sink in the neighbor set (called best neighbor set).

Figure 7

The Smart Greedy Forwarding algorithm. As shown in Figure 7, the algorithm checks (Line 1) if a packet is already received from a source node. If no, the packet will be always forwarded to the best node (line 2), and the hop count "H" and the average score index "j" in the best neighbor set are set. These empirical values will be used later to allow load balancing. It is clear that the first packet received from an unknown source will be always forwarded to the best neighbor node.

Upon_Recieving_a_Packet

Line 7 specifies that we have already an empirical estimation of the hop count H and the average index j from a particular source. These values are retrieved as shown in line 8. We calculate (in line 9) the deviation Δh of the hop count of the received packet compared to the stored value H. The index of the new forwarder neighbor that allows best load balancing will be adjusted by Δh (line 10). However, two different out of range situations may occur. Line 11 specifies that the received packet has passed through a lot of hops, and thus it needs to be forwarded to the best node (i.e. node with index=1). The received packet that has experienced a less hop count than the empirical value H (line 15), and thus it has to be forwarded to node with higher index (index=m). The new empirical value is computed (Line 12 and 16) that will be used later as a new reference. Finally, the packet is forwarded by using the described Smart Greedy Forwarding (line 19).

Walking Back forwarding mode

Because of node failures, node energy depletion due to processing and scheduling activities and node mobility, disconnections may occur in a WSN generating what we call "voids". At certain times, a forwarder node may face a void where there is no closest neighbor to the sink as illustrated in Figure 10. Forwarder node

(H, j) ← Get_Hop_Values(packet.Source) // not null Nj Score j ≈ σ MeanScore : σ Score [1] > Score [2] > . . . > Score [m]
Recieved packet

h = packet.HopCount h = H h ≤ H + j-m h = H + j -2 h ≥ H + j -1 H ← h-j+1 Update: Update: No Update No Update H ← h-j+m
Set_Hop_Values(packet.source, (H,j))

In this case, the node enters the walking back forwarding mode in order to bypass this void. In such a case (see Figure 10), the forwarder node will inform all its neighbors that it cannot be considered as a neighbor to forward packets to the sink. This node will also delegate the forwarding responsibility to its nearest neighbor to bypass the void. This process does recursively step back until a node is found that can forward the packet successfully. This technique is better than the perimeter routing mode used in GPSR, since this kind of process is only done once a packet is received from an unknown stream, all the other packets belonging to the same stream will be routed avoiding the nodes that are facing a void toward the sink.

4

Simulation and Evaluation

Simulation Environment

We have considered a homogenous WMSN, in which, nodes are randomly deployed through the sensing field. The sensing field is a rectangular area of 500m x 200m. The sink node is situated at a fixed point in the righter edge of the sensing field at coordinates (490, 90) while a source node is placed in the other edge at coordinates (10, 90). We have considered this network for video surveillance (see Figure 11). In response to an event, the source node will send images with a rate of 1 image per second during 30 seconds.

Figure 11

Data Delivery in Response to an Event in a WMSN.

Sink Event Sensor Node

To demonstrate and evaluate the performance of our proposed protocol AGEM, we used OMNeT++ 4 which is a discrete event network simulator [START_REF] Varga | An overview of the OMNeT++ simulation environment[END_REF]. To prove the effectiveness of AGEM, we have also implemented the GPSR algorithm (as an online but singlepath routing protocol) and an adapted version of MPMPS on top of the TPGF algorithm (as an offline-multipath routing protocol) and we compared the simulation results. We have also introduced GEAMS (Greedy Energy-Aware Multipath Stream-based) Routing protocol which consists of a "light" version of AGEM that does not include the adaptive compass mechanism for next hop node selection. Thus, GEAMS uses only distance-based greedy progression. Table 1 summarizes the simulation environment. We have considered that the link data is of type IEEE 802.15.4. To evaluate the performance of our protocol, we have considered the following three topology types:

Plain topology:

This topology is used to evaluate the behavior of the routing algorithm especially the smart greedy forwarding mode. Here, we have used three plain topologies; a network of 30, 50 and 80 sensor nodes. An example of these topologies is shown in Figure 12.

Figure 12

A 30-nodes network topology.

Topology with holes:

This topology is used to evaluate the performance of the routing algorithm in presence of holes (i.e. to evaluate the performance of the walking back forwarding mode).

We have used four topologies with holes; a network of 30 sensor nodes with one or two holes, and a network of 50 sensor nodes with one or two holes. An example of such topologies is shown in Figure 13.

Figure 13

A 30-nodes network topology with two holes.

Regular topology:

This topology is used to evaluate the load-balancing feature of the algorithm. We have used one grid topology of 26 sensor nodes. This network is shown in Figure 14.

Figure 14

A 26-nodes grid network topology.

In all of the above topologies, we consider the minimum distance between two neighboring nodes to be greater than 1 meter. For each topology, we have measured various metrics:

Simulation Results:

In this section, we only present the simulation results obtained for different topologies using GPSR, TPGF, GEAMS and AGEM. The next section provides the discussion on the results obtained:

Plain topologies

The distribution of the residual energy in the network (GED) is shown in Figure 15.

Figure 15

Average residual energy in "plain" topologies.

The distribution of the residual energy across the network (LED) is shown in figures 16-18.

Figure 16

The distribution of the residual energy across the network for 30-node network topology.

Figure 17

The distribution of the residual energy across the network for 50-node network topology.

Figure 18

The distribution of the residual energy across the network for 80 nodes topology.

The distribution of the end-to-end delay is shown in Figure 19.

Topologies with holes

The distribution of the residual energy in the network (GED) is shown in Figure 21. The distribution of the residual energy across the network (LED) in a topology with holes is shown in Figure 22.

Figure 22

Residual energy distribution across the network for 50-node network topology with two holes (holes are in region 210m-290m along the sensing field)

The distribution of the E2E delay is shown in Figure 23.

Figure 23

Average end-to-end delay in topologies with holes.

The ratio of overall packet losses during the transmission is shown in Figure 24.

Figure 24

The packet-loss ratio in topologies with holes (please note the logarithmic scale)

Regular topology

To illustrate the load-balancing feature of AGEM, we have used a grid topology and simulated a transmission between nodes Src and Dest as shown in figures 25-26. The figures show the residual energy at each node by the mean of a graduated color that corresponds to their residual energy (Red to 0% and Blue to 100%).

Figure 25

Residual energy with GPSR in a grid topology.

Figure 26

Residual energy with AGEM in a grid topology.

Simulation Results Discussion

Global Energy Distribution (GED)

The GPSR protocol always uses the closest neighbor to the destination (see GPSR behavior in a grid topology as shown in Figure 25) due to inflexible selection of the next hop node. Forwarding packets to that neighbor is costly since the distance in a greedy forwarding is considered only and longer the distance is, the most energy consuming the transmission will be. This explains why residual energy in the case of GPSR is less than in the case of AGEM as shown in figures 15 and 23.

Although the use of multiple paths in TPGF, TPGF is still more energy consuming than AGEM since it uses "greedy" paths.

Moreover, the energy distribution in the network is well distributed with AGEM compared to GPSR. Unlike GPSR, AGEM use various nodes to perform online multipath routing and load balancing (see Figure 26).

Local Energy Distribution (LED)

Figures 16-18 and 22 illustrate the average residual energy of the network partitioned in regions of 40 meters width for the plain topologies and a topology of 50 nodes with two holes. We can clearly see that the energy is uniformly consumed through the network when using AGEM routing protocol compared to GPSR and TPGF routing protocols. Moreover, AGEM uses less energy than TPGF since TPGF is a greedy routing protocol and all the explored paths use always the greedy neighbor to forward packets. The benefit of such a feature is to prevent the network from being portioned into sub networks that are completely disconnected if some nodes die because of their energy depletion.

Packet Loss and Transmission Delay

By using multiple paths to transmit data packets, not only the packet transmission delay has been generally reduced first by using GEAMS and AGEM as shown in figures 20 and 26, but also, this end-to-end delay has become uniform as we can see by the mean of the standard-deviation as shown in figures 21 and 27.

However, this end-to-end delay remains quite bigger than the end-to-end delay while using an offline multipath routing protocol such as TPGF. This can be explained by the fact that TPGF uses totally disjoint paths to route packets. This makes packets safe from interference problems (retransmissions). The packet loss ratio has also been decreased as shown in figures 22 and 28 in comparison with GPSR. The decrease in packet loss ratio and delay can be explained by the following points: 1

The use of the same path will increase the queuing delays within nodes along the routes and causes network congestion. 2

Sensor nodes have resources constraints, packet loss may occur due to the limited buffer sizes in sensor nodes. 3

In the case of topologies with holes, the perimeter routing mode employed by GPSR is not suited for burst transmissions which causes buffer over loads and packet losses. These results demonstrate a better performance of AGEM to deliver multimedia traffic (still images in our simulation case) and provide better QoS compared to GPSR (lower the end-to-end delay and reduced packet loss ratio). AGEM is also more suitable to dense networks in which different paths to destination may exist.

Conclusion

In this paper, we have described a new algorithm namely AGEM that is suitable for transmitting multimedia streaming over WMSNs. Because nodes are often densely deployed, different paths from source nodes to the base station may exist. To meet the multimedia transmission constraints and to maximize the network lifetime, AGEM exploits the online multipath capabilities of the WSN to make load balancing among nodes. Simulation results show that AGEM is well suited for WMSNs since it ensures uniform energy consumption and meets the delay and packet loss constraint.

Figure 1

 1 Figure 1 GPSR Perimeter forwarding to bypass a void.D

Figure 2

 2 Figure 2 Greedy forwarding strategies: (a) Compass routing; (b) Random Compass routing; (c) Greedy routing; (d) Most Forwarding; (e) Nearest Neighbor routing; (f) Furthest Neighbor routing.

Figure 6

 6 Figure 6 Packet energy consumption considering two communicating nodes A and B. Node A Node B pk n Bits -ERX ( n ) -ETX ( n, AB )

Figure 8 Figure 9

 89 Figure 8Forwarding the first packet of a data stream.

Figure 10 A

 10 Figure10A blocking situation where a forwarder node has no neighbor closer to the sink than itself.

  1 Global Energy Distribution (GED): it is the average and the standard-deviation of the residual energy at all network nodes. 2 Local Energy Distribution (LED): it is the average residual energy in contiguous regions of 40 meters width. 3 End-to-End Delay Distribution: it is the average and the standard-deviation of the end-to-end delay. 4 Packet Loss Ratio: it is the percentage of lost packets during the transmission.

Figure 19

 19 Figure 19 Average end-to-end delay in plain topologies.

Figure 20

 20 Figure 20 Packet-loss ratio in plain topologies.

Figure 21

 21 Figure 21 Average residual energy in topologies with holes.

Table 1

 1 Simulation parameters.

	Parameter	Value
	Network Size	500m x 200m
	Number of Sink Nodes	1
	Number of Source Nodes	1
	Number of Sensor Nodes	30, 50, 80
	Number of Images	30 images
	Image Size	10Kb
	Image Rate	1 image/sec
	Maximum Radio Range	80 meters


Sylvain Miossec
email: sylvain.miossec@bourges.univ-orleans.fr

Laurence Nouaille
email: laurence.nouaille@bourges.univ-orleans.fr

Structural link optimization of an echography robot

It is an interesting goal to obtain robots lighter, more precise or to minimize other criteria. Among robot optimization problems, optimizing the structure of robot links considering all its conditions of use can be a very computationally intensive problem, due to the dimension of the configuration space. Maybe for this reason, such problems has never been solved thoroughly. We considered the case of a 3-degrees-of-freedom echography robot. We optimize the shape of two links to minimize the weight and deformation under an end-effector force condition, and whatever the robot configuration. In order to obtain a rapid optimization, we use a non-uniform beam model for links with sensitivity computations. We proposed an easy-to-solve compromise formulation between two criteria. We showed that some substantial weight decrease could be obtained while keeping small deformations, with reasonable computation times, and that several configurations must be considered simultaneously.

I. Introduction

Design optimization of robots is challenging to obtain more precise, lighter, faster, less energy-consuming or stronger robots. To obtain this goal, it is possible to choose the robot structure (number, type and position of joints) the links shape, the choice and position of the actuators. In this paper we are interested in the optimal choice of links shape. Our contributions on this problem are:

• to optimize the robot shape under a strength constraint of its structure. At first, this problem is not different from structural optimization made in civil engineering or engineering design. Our contribution is to consider the complexity of robot due to its various configurations, and to environment forces it may undergo. This general problem is presented section II.

• to approximate the problem, compute its gradients and use a gradient-based optimization method to obtain a fast and robust optimization, see section III.

• to propose a compromise formulation between two criteria that can be easily and efficiently solved.

• to apply this method to a 3-degrees-of-freedom echography robot section IV to analyze the optimal solution, and to demonstrate the weight improvement obtained with the proposed approach section V.

Our approach is finally compared to previous works in section V-E.

II. The problem of static structural optimization of a robot

We consider the design of robots whose kinematic structure has already been chosen in a previous design stage under geometric and kinematic requirements. In this study, we are interested in the choice of the links shape parameters, such as thickness, beam section dimensions, and any other geometric parameters independent of the joints relative position. All shape parameters of links are grouped in the vector p ∈ R np . We consider the set of external load forces F ∈ F ⊂ R n f . n f could be more than 6 if forces apply not only on a single point. We also consider the joint variables q in the configuration space R nq . The robot static equations enable the writing of the 6-component joint forces and torques vector of link i F i with respect to joint angles q and external loads F . F i = J(q)F ∀i = 1..n q [START_REF] Hettich | Semi-infinite programming: Theory, methods, and application[END_REF] where J(q) is a Jacobian matrix.

We must consider a static structural model of links to get end-effector displacement and internal stress tensor σ. For each link this tensor depends on forces applied on this body and the point P of the link.

σ i (p, P, F i , F i-1 )∀P ∈ link i (2)
For notation simplicity, we only consider serial robots submitted to joint forces with previous and next body. But this notation can be extended to tree-like and parallel robots. We do not consider any stiffness for motors. In a static case, it could be infinite with an integral term in the joint control law. Any other source of joint deformation could be taken into account in a 3D structural model.

In this paper, we address the problem of optimally choosing the shape parameters p to minimize a criterion C(p) of the robot for the whole configuration space and external load space under a yield criterion and additional constraints g(p, q, F ) < 0. The mathematical formulation of this de-

σ VM i (p, P, F i , F i-1 ) < σ y F i = J(q)F g(p, q, F ) < 0        ∀P ∈ link i ∀i ∈ [1, n q ] ∀q ∈ R nq ∀F ∈ F (3)
Where σ VM is the Von Mises stress computed from σ that must be inferior to the yield strength σ y in order to avoid yield. This problem is a high-dimensional semi-infinite nonlinear optimization problem, see [START_REF] Hettich | Semi-infinite programming: Theory, methods, and application[END_REF]. Semi-infinite optimization problems carry an infinite number of constraints, which is the case of constraints on Von Mises stress that take place whatever the point P , robot configuration q and external load forces F . In this case, the semi-infinite space is of dimension n q + n f + 3 (the 3-dimensional space being the space of position of yield constraint). We will see in the next section how this problem is approximated in order to solve it numerically.

III. Approximation of the problem for numerical solving

A. Structural model of the robot

For the structural model, any Finite Element algorithm could be used, but as a first step, we choose the simplest beam model. This model is adapted for robot elongated links. For improved solution, we consider non-uniform links by discretizing them in piece-wise uniform beams. We also neglect the links gravity forces compared to the end-effector force and motors weight. For the computation of the internal stress, we considered bending, compression, torsion, as well as shear forces and moments. The beams section parameters will constitute the shape parameters of such a structural model.

B. Discretized optimization problem

In order to solve the problem (3) with nonlinear optimization methods, the semi-infinite constraints are discretized. We will note P i ∈ link i the set of discretized geometric points belonging to link i, Q ∈ R nq the set of discretized configuration points belonging to configurationspace, F ∈ F the set of discretized external loads. The new discretized optimization problem is then,

min p∈R np C(p) subject to σ VM i (p, P, F i , F i-1 ) < σ y F i = J(q)F g(p, q, F ) < 0        ∀P ∈ P ∀i ∈ [1, n q ] ∀q ∈ Q ∀F ∈ F (4)
It is important to notice that the evaluation of all constraints will need n c FEM computations, where n c = n f d × n qd with n f d the number of discretized external loads and n qd the number of discretized configuration points (in the hypothesis that all discretized loads apply to all discretized configuration). In the case where F would depend on q, computation would be different.

C. Gradients computation

To improve the convergence speed and robustness, we computed the gradients of the criteria and the constraints. To this end, we used the open-source OpenSees finite element software [START_REF] Mazzoni | The OpenSees Command Language Manual[END_REF], developed for the seismic response of structural and geotechnical systems. OpenSees includes sensitivity computations, as well as the parameters management, which allows us to compute the exact internal stress gradients, constraints and criteria.

D. Optimization method

We used the sequentially quadratic programming (SQP) method NPSOL [START_REF] Gill | User's guide for NPSOL 5[END_REF]. This is a gradient-based method that will find very efficiently a local solution.

IV. Application to Estele echography robot

A. Estele robot presentation

This work takes place in the context of tele-echography, which consists in a specialist controlling at a distance the motion of an ultra-sound probe through an echography robot. The analysis of echographic exams [START_REF] Bassit | Structures mécaniques à modules sphériques optimisées pour un robot médical de télé-échographie mobile[END_REF] showed two steps: a search for the organ to observe, and then the observation of the organ itself Fig. 1(a). For the complete exam 6 degrees of freedom are necessary. But for an emergency situation a portable robot is more adapted. It has been showed 6 dof robots are too heavy to be portable, therefore portable robots are usually restricted to 4 dof: 3 rotational dof, and one translation normal to the contact. Such dof are adapted to the second step of organ observation. Missing dof are provided by the person holding the robot that can be asked to change the position of the robot on the patient. The gesture analysis additionally showed that expert is observing essentially around the normal to the patient Fig. 1(b). Robots are then better adapted if the center of their workspace is around this normal. The work of this paper is applied to the Estele echography robot presented Fig. 2 [5]. This is a serial spherical wrist robot composed of three revolute joints (θ 1 , θ 2 , θ 3 ) with concurrent axes, which gives a remote center of motion, see Fig. 2(b). An additional fourth prismatic joint is also present to control the contact force applied, but will not be considered in this paper. For the Estele robot, the angle between joint axes is of 22.5 • so that the workspace is a cone of 45 • with the vertical. The distance between the center of rotation and the last revolute joint center is 18cm in order for the echographic probe to fit with its cable.

B. Optimization problem B.1 Parameters

The presented kinematic dimensions are taken for granted in this study, and we will focus on the shape optimization of the two first bodies of the robot. As said previously those bodies are modeled by non-uniform beams ap-proximated by piece-wise uniform beams. We considered all beams as tubes defined by inner radius R 0 and outer radius R 1 . We had to implement the computation of internal stress in a beam section, that does not exist in the OpenSees software. For a tube, we computed analytically the expression of stress due to compression, bending, torsion and shear. We considered N b beams for first and second links, and only one beam for the third. This makes a total of 2 × N b + 1 parameters in p.

B.2 Loads and configurations

The load requirement for the robot is to sustain a maximum vertical force of 20N on the probe. We considered also the weight of motors on the joints: 277g for the second joint, 394g for the third joint (including the fourth prismatic joint), as well as the weight of the probe of 100g. We also considered the situation where no contact force is applied on the probe, which correspond to a situation of the robot moved by the technician in free space.

First and last joints θ 1 and θ 3 have no effect on the forces applied on first and second links. Except for the third link that will undergo the same load in all directions for all third angle values θ 3 ; but since this link is a shape of revolution, the θ 3 orientation has no effect on the optimal tube parameters. Configuration space that must be considered for this study is then only the space of second joint θ 2 . Due to a symmetry, we consider only values between 0 • and 180 • .

B.3 Criteria

The problem considered is a compromise between two contradictory criteria: the mass of the robot M (p), and the deformation of the robot end-effector subject to the forces applied d(p, q, F ) that can be seen as the precision we can obtain for the end-effector. The mass M (p) includes both the structure mass, the motors mass 671g, and an approximate probe mass 100g. At first we dealt with the compromise between both criteria by minimizing M (p) under a maximum acceptable displacement on d(p, q, F ). Since criteria are contradictory, solution is at specified acceptable displacement or limited by other constraints. As will be seen on the Pareto frontier Fig. 3 structure mass is then very light and displacement important, and it is possible to decrease greatly the displacement with relatively small increase in mass M (p). This lead us to choose another point on the Pareto frontier: the point from which a relative decrease of one criteria gives the same relative increase of the other criteria. We show in AN-NEXE that we can find this point by minimizing criteria C(p) = ln(M (p)) + ln(max q,F d(p, q, F )), which can be re-

formulated in min p,s C(p, s) = ln(M (p)) + ln(s) subject to d(p, q, F ) -s < 0 ∀q ∈ Q ∀F ∈ F (5)
where s is a slack variable that will equal the maximum displacement among configurations and loads at the solution.

Additional constraints on the maximum values of both criteria had to be provided, since, as we will see, solution of proposed compromise can be for an infinite value of a criterion. 3cm was chosen for the displacement, and 10% of the mass of motors and probe for structure mass, corresponding to 77.1g.

B.4 Constraints

The yield constraints on the Von Mises stress σ V M are considered on the discretized volume of the beams. We considered a grid of 16 pieces on the circumference, one point per beam along the axis of the beam. For our problem, we also noticed that the maximum of the constraints were on the exterior surface. To keep the problem as light as possible, we added progressively the points that had Von Mises stress greater than the yield strength σ y .

We also added some constraints to problem (4) in order to obtain a minimum thickness of the tubes and a maximum radius of the tubes. Otherwise with the defined problem, we obtain solutions with too thin and large tubes, as will be detailed later.

We considered two materials for the robot: aluminum (Young modulus E = 69GP a, Poisson's ration ν = 0.33, yield strength σ y = 100M P a) and polyoxymethylene (POM, Young modulus E = 3GP a, Poisson's ration ν = 0.35, yield strength σ y = 50M P a).

V. Results

Optimizations were performed for 8 configurations with θ 2 varying from 0 • to 157.5 • for each of the two load conditions. We considered N b = 10 beams for first and second link. Aluminum optimizations were performed for tubes of minimal thickness 1mm and maximal radius of 15mm. POM optimizations were performed for tubes with a minimal thickness of 1.5mm and maximal radius of 15mm.

A. Pareto frontier of mass and displacement criteria

Pareto frontier Fig. 3 was obtained by performing several mass minimization problems with varying maximum constraint on displacement.

B. Case of minimum mass

For aluminum, convergence was obtained in 34 iterations and 3min, as can be seen Table I. The optimal shape of bodies obtained is presented Fig. 4. External radius range approximately from 2mm to 3mm, with a thickness of 1mm everywhere. Characteristics of the solution are presented Table I. The solution obtained is at the extremity of the aluminum Pareto of Fig. 3. Von Mises stress for all considered configurations/loads of the optimal structure are presented Fig. 5, and Fig. 6 focus on the zones of maximum stress that are at the limit of yield. For POM, we obtained a solution of weight 11.3g but a norm of displacement of the end-effector of 25cm, which is even larger than the size of the links. The corresponding solution is outside of the POM Pareto of Fig. 3. Our beam model is not valid anymore, and this is much too important for our application. This echography robot is used in a visual feedback loop including a human that can compensate for robot deformations, but not to that point. We then added a previously unformulated requirement as a maximum displacement of end-effector by 3cm. The solution obtained is at the extremity of the POM Pareto representation Fig. 3. Convergence characteristics and optimal solution are presented Table I. External radius ranges from 5mm to 7mm, We performed the same optimization as previously, but for the restriction that only the straight arm configuration θ 2 = 0 • was considered for constraints, as well as for only the configuration θ 2 = 90 • . All the convergence and solution data are presented Table I.

C. Compromise case

This problem corresponds to (5) with additional maximum structure mass of 77.1g and maximum acceptable displacement of 3cm. The solutions obtained are at the maximum structure mass of 77.1g, see Table II. Von Mises constraints were not included in the optimization process since they are not active at the solution. They were slowing down the computations and preventing the optimization algorithm to converge properly for numerical reasons. To solve it properly, Von Mises constraints could be added progressively during optimization process when they become violated. The aluminum optimal solution is composed of tubes of thickness 1mm, and radius from 13.5 to 15mm. The POM optimal solution is composed of tubes of radius 15mm, and thickness from 1.5mm to 3mm.

D. Discussion

D.1 Characteristics of solutions

In all cases, the solution was at the minimum thickness (1mm for aluminum and 1.5mm for POM) or at the maximum tube radius. If such constraints were not considered, the optimal solution would be for a null thickness with an infinite radius. To prevent this, the real physical constraint that should be added is the local buckling avoidance. But such constraint is difficult to express. And the limit of thickness could also be considered as a manufacturing constraint, since too thin bodies are difficult to produce. Maximum radius constraint can be considered as a limit on bulkiness of the links.

Minimum mass solutions are at the right extremities of Pareto frontier Fig. 3. What can be additionally observed is that displacement can be decreased a lot, while the structure mass is increased only slightly relatively to the total mass including motors and probe. It is therefore not interesting to stick to the minimum mass solution. That's why we translated this compromise in choosing the Pareto point with opposite relative variations of both criteria. Practically, if one move locally from this point along the Pareto frontier, when a criterion increase for example of 10%, the other criterion decrease also of 10%. We discuss this compromise later on.

For the case of minimum mass and several configurations, the other active constraints at the optimal solution depends on material: for aluminum structure those are the yield constraints ; for POM structure the only other active constraint is the displacement limitation. When yield constraints are active, they are active for each section only one time in the configuration space, as can be seen on Fig. 6. Such a solution seems to present a decoupling between all sections. Knowing this characteristic of the optimal solution, a dedicated algorithm could be developed to obtain the solution in a much faster computation.

We obtained that the use of aluminum gives a lighter or more rigid robot than POM for all problems. The convergence is fast when limiting constraints are the yield condition on the Von Mises stress. However convergence is slow when the limiting constraint is the displacement limit while Von Mises stress constraints are still defined in the problem.

Removing those non-active Von Mises stress constraints improved convergence (which theoretically should not be the case). It then seems all non-active yield constraints give numerical problems to the optimization program. In Table I we observe a slight yield constraint violation for the minimum mass aluminum structure with 8 configurations. It is due to the fact the discretization of the Von Mises stress is tighter for the presentation of the solution than during the optimization. This could be solve by adding the constraints that are not satisfied in a new optimization problem that we solve again.

For the compromise solution, it can be observed solutions are at the maximum allowed structure mass. This can be explained by analyzing roughly the dependence of criteria with respect to radius of tubes in bending (which is the main deformation taking place in the robot). For thinwalled tubes of radius R and thickness e, in first approximation the mass is homogeneous to Re, and the displacement is homogeneous to 1 R 3 e . Minimizing ( 5) is in first approximation equivalent to minimize -2 ln(R) which gives a Radius R tending to infinity and a displacement tending to 0 on Pareto frontier. It explains why we obtain the minimum displacement allowed by the maximum mass constraint.

Analyzing the compromise solution, with tubes of slight radius or thickness change, one could rather consider using uniform tubes instead, which would decrease slightly performance of the solution, but would be much easier to manufacture.

D.2 Interest of the approach

The Pareto frontier Fig. 3 gives insight in the problem, but require many optimizations. For more complex robot designs or problems with more criteria, it could be very time consuming to obtain. In such a context, the compromise optimization formulation proposed in this paper could be very interesting.

For the case of the minimum mass aluminum structure that is constrained by yield, the solution satisfying the constraints of 8 configurations is only slightly better than the solution satisfying only constraints of configuration with θ 2 = 0 • (weight is almost similar, the yield constraint violation is of about 5%). In this case, optimizing only one configuration could be enough. However it was the best configuration we could choose. For the configuration θ 2 = 90 • (which include a point of maximal stress for a section, see Fig. 6) solution obtained is not as optimal: the weight is decreased but at the expense of the yield constraint violation of about 16%. And for a random configuration, it could be even worse. For other cases structure is constrained by displacement of end-effector due to the load, and only one constraint is active. So taking the configuration with θ 2 = 0 • that gives the maximum displacement, the exact solution can be obtained. For example, considering only the configuration with θ 2 = 90 • gives a violation of the constraint of about 10% for the mass minimization of POM structure.

Minimum mass solution presented is not a good compromise. However this solution shows the interest in some cases of taking into account several configurations. We could imagine other problems where taking several constraints are important: if weight is much more important than precision, if load and configuration space are complicate we could have several maximum displacement loads/configurations.

We also compare our results with the original Estele echography robot. The equivalent structure parts of the Estele robot account for a weight of 740g in POM, while we found minimum weight of 22g in POM and 13g in aluminum, and 77.1g for our mass-displacement compromise. This is a very large difference that can be explained primarily by the fact Estele echography robot was not optimized. Another explanation why we found a very light structure is because of the simplifications we considered. We will present them in the next section.

D.3 Limitations of the approach

The beam model we choose does not allow to represent/choose the shapes near joints, that are complicate because of the integration of the joint, cables, motors, ... Furthermore, the beam model is only valid far from the extremities of the links. The current study then gives only an optimal choice valid near the center of each link. We also neglected gravity forces of links. The difficulty to integrate gravity forces of links is that it depends on the shape of the structure. Taking into account them will complicate the problem since loads on beams will depend on shape parameters.

Not making most of previous approximations will probably produce an heavier/less precise robot. However some improvement could still give some weight/precision gain: to consider different sections shape (in particular for the first link that is essentially submitted to bending, the optimal shape is an I section) and to include a precise nonbuckling constraint in addition to the thickness constraint. The buckling is a global characteristic of a link, that can not be reduced to each beam of the piece-wise representation. Furthermore, observing local buckling of tube walls require 3D FEM model. Hence some problem to integrate buckling with the FE software beam model.

E. Related work

Many works have been devoted to the optimization of structures, see for example the review paper [START_REF] Arora | Review of formulations for structural and mechanical system optimization[END_REF], and the books [START_REF] Rees | Mechanics of Optimal Structural Design[END_REF], [START_REF] Arora | Optimization of Structural and Mechanical Systems[END_REF], [START_REF] Allaire | Conception optimale de structures[END_REF]. But they usually consist in nonreconfigurable structure (like robots) and single loaded studies. However, [START_REF] Rees | Mechanics of Optimal Structural Design[END_REF] was very interesting: it gives analytical solutions of optimal beams, taking into account both buckling and yield constraints. It gave insight on the optimal section shape, depending on the type of loads. However the results and approaches presented were not reusable for non-uniform beams submitted to all type of constraints. We then had to use numerical methods. [START_REF] Allaire | Conception optimale de structures[END_REF] identified three types of numerical shape optimization methods:

• the parametric method which consists in choosing some basic geometric parameters from which the shape is defined. This method is adapted for the optimization of parametrized mechanical designs performed with CAD software.

• the geometric method, which consists in considering the shape model as the FE mesh, that allows to parametrize the shape more precisely, but does not solve the problem of topology choice.

• the topology method, which consists in discretising the space and determining where to put some material. It addresses the problem of topology choice. The approach presented in this paper is a parametric one.

Surprisingly, in the robotic field, few works have been devoted to the structural optimization of robots, maybe because it is a very high-dimensional, difficult to solve problem. Many design optimization studies of robots are limited to kinematic properties, see [START_REF] Chapelle | Evaluation functions synthesis for optimal design of hyper-redundant robotic systems[END_REF], [START_REF] Nouaille | Démarche de conception de robots médicaux -application à un robot de télé-échographie[END_REF], [START_REF] Bouyer | The multiobjective optimization of a prismatic drive[END_REF], [START_REF] Merlet | Optimal design of robots[END_REF]. The few studies that we found to consider structural aspects are [START_REF] Bidault | Structural optimization of a spherical parallel manipulator using a two-level approach[END_REF], [START_REF] Dixit | Shape optimization of flexible robotic manipulators[END_REF], [START_REF] Leger | Automated synthesis and optimization of robot configurations: an evolutionary approach[END_REF], [START_REF] Neugebauer | Method for the optimization of kinematic and dynamic properties of parallel kinematic machines[END_REF], [START_REF] Roy | Structural design optimization and comparative analysis of a new high-performance robot arm via finite element analysis[END_REF], [START_REF] Zhu | Simultaneous optimization of a two-link flexible robot arm[END_REF]. Comparison of these works with this paper is presented in Table III. It can be seen that most structural optimization of robots, are interested into stiffness and displacement of the end-effector or vibrations. Only the work of [START_REF] Bidault | Structural optimization of a spherical parallel manipulator using a two-level approach[END_REF] was also interested in strength of the robot. It computed the maximal forces in the worse configuration, and optimized the robot only for this configuration/load. However, we have seen in this paper Fig. 6 that the maximum stress can take place on several configurations, and that several configurations must than be taken into account simultaneously. Another contribution that we did not found in those papers is the computation of gradients to increase robustness and speed of convergence. We obtained reasonable times in Table I. On the contrary, in [START_REF] Neugebauer | Method for the optimization of kinematic and dynamic properties of parallel kinematic machines[END_REF], they obtained optimization times of several days and weeks. Even if they optimized a more complex problem of a 9-links parallel robot modeled with 3D FE elements on a trajectory, we hope our approach with gradients computation would allow for faster computation.

VI. Conclusions and future works

A. Conclusions

We presented the general problem of shape optimization of robots, and a simple method to obtain a problem that can be solved with non-linear optimization algorithms. We used beam structural model that can be applied to optimize the shape of robots composed of elongated bodies approxi-mated with piece-wise uniform beam. The use of OpenSees FE software allows for gradient computation for efficient and robust optimization. It also allows to program easily the optimization of new problems using a scripting language. We analyzed the problem and proposed a an easy-to-solve formulation that gives a good compromise between two criteria. We also obtained interesting results that show the need for optimization in the whole configuration-space. We finally showed that the approach can decrease dramatically the weight of the structure. However the method must still be assessed and developed in order to be more realistic and to be usable more widely.

B. Future Works

In the near future, we will consider other section shapes, investigate the inclusion of buckling constraints for nonuniform beams, and finally consider more general and realistic 3D structural models. We will also inverstigate if our compromise formulation can be extended for more than 2 criteria optimization problems. On a longer term, we will investigate the use of geometric and/or topology optimization methods, and consider dynamic robot model and vibration model.

ANNEXE: Demonstration of problem to solve to obtain the point on Pareto frontier that satisfy opposite relative variations of two criteria

Let's consider the Pareto frontier of problem with two criteria C 1 (x) > 0 and C 2 (x) > 0 to minimize in function of variables x. A point of this Pareto frontier for C 1 (x) = α can be obtained by solving the following problem:

min x C 2 (x) s.t. C 1 (x) < α (6)
Let's note x opt (α) the optimal parameter x obtained by solving [START_REF] Arora | Review of formulations for structural and mechanical system optimization[END_REF]. The Pareto frontier equation can then be written C 2 (x opt (α)). The desired point on Pareto frontier with opposite relative variations is given by dC1 C1 = -dC2 C2 . With previous definition of Pareto frontier, we obtain

∂C 2 (x opt (α)) ∂α = - C 2 (x opt (α)) α (7)
We will show that the problem:

min x ln(C 1 (x)) + ln(C 2 (x)) (8)
is giving as a solution the point of the Pareto frontier that satisfy [START_REF] Rees | Mechanics of Optimal Structural Design[END_REF]. For this, we should first notice that this problem will give us a solution on the Pareto frontier: by reductio ad absurdum, if optimal solution of (8) was not on Pareto frontier we would be able to decrease both criteria, which would mean we could decrease more the criterion of [START_REF] Arora | Optimization of Structural and Mechanical Systems[END_REF]. Then, let's consider the optimality condition of problem (8):

1 C 1 ∂C 1 ∂x + 1 C 2 ∂C 2 ∂x = 0 (9)
Finally replacing those last expressions in [START_REF] Bidault | Structural optimization of a spherical parallel manipulator using a two-level approach[END_REF] gives us the condition of opposite variations of the criteria [START_REF] Rees | Mechanics of Optimal Structural Design[END_REF].

Fig. 1 .

 1 Fig. 1. Analysis of echographic exams.

Fig. 2 .

 2 Fig. 2. Estele prototype.

Fig. 3 .

 3 Fig.3. Pareto frontier of structure mass with respect to displacement for aluminum and POM. The aluminum curve is the one below, aluminum allowing lighter structure for a same displacement. The aluminum Pareto between 15mm and 27.8mm correspond to a solution with active yield constraints. The curve end at 27.8mm since it is not possible to obtain lighter structure satisfying yield constraints (in the space of non-uniform tubes considered).

Fig. 4 .

 4 Fig. 4. Minimum mass shape of aluminum bodies with Von Mises Stress represented for θ 2 = 0. First link is on the left, second in the middle, third on the right.

Fig. 5 .

 5 Fig. 5. Von Mises stress for minimum mass aluminum structure for all configurations considered. The 8 configurations on the left correspond to the case of a vertical force of 20N on the end-effector. The 8 configurations on the right correspond to the case of no end-effector force, that is, only submitted to its own weight.

13thFig. 6 .

 6 Fig. 6. Von Mises stress for minimum mass aluminum structure optimized for all configurations considered. Maximum stress of a section is highlighted with white lines. Only configurations with maximum stress are represented.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Aluminum structure optimized with compromise criterion.

  13th World Congress in Mechanism and Machine Science, Guanajuato, México,19-25 June, 2011

	A23 294
	sign optimization problem is the following.
	min p∈R np C(p)
	subject to

TABLE I .

 I Results of structure mass minimization, with aluminum or POM, for one configuration or 8 configurations.

		8	34	3min 12.847g 101MPa	2.78cm
	Alu.	θ 2 = 0 • 41 θ 2 = 90 • 23	30s 16s	12.835g 106MPa 11.117g 117MPa	2.79cm 2.69cm
		8	177 34min 21.935g 17.8MPa	3cm
	POM	θ 2 = 0 • 86 1min30s 21.935g 17.48MPa θ 2 = 90 • 374 11min 21.228g 19.7MPa	3cm 3.31cm

Config. Iter. Time Weight σ V M max Disp. max

TABLE II

 II

		. Results of structure mass-displacement compromise, with alu-
	minum or POM.
		Config. Iter.	Time	Weight σ V M max Disp. max
	Alu.	8	109	41s	77.1g 2.96MPa	0.1mm
	POM	8	232 1min 11s 77.1g 1.78MPa	1.2mm

TABLE III .

 III Comparison of studies on structural optimization of robots. A static robot model with a dynamic FE model means FE dynamic computations are valid only for small displacements. A trajectory for the Configuration/Load means that some Criteria/Constraints are defined on a trajectory. The crosses "X" for the Criteria/Constraints indicate which type of Criteria/Constraints were considered. SQP stands for the Sequential Quadratic Programming optimization algorithm, and GA for the Genetic Algorithm.

								This paper	[10]	[11]	[12]	[13]	[14]	[15]
	FE model	type size					static 1D	static 3D	dynamic 1D	static 1D	dynamic dynamic dynamic 3D 1D 1D
		Robot model						static	static	dynamic	dynamic dynamic static	dynamic
	Config.×Load space			8 × 2	max×1	traj.	traj.	traj.	10 × 2	traj.
		Shape					non-uniform non-uniform non-uniform non-uniform uniform uniform non-uniform
			displ.					X	X	X	X
	Crit./Constr.	vibration freq.		X	X
			stress					X	X
			weight				X	X	X	X
		Optimization						SQP	Pro/Mechanica	SQP	GA	SQP	by hand	GA
	Solution of (8) being on Pareto frontier, we can perform a
	scalar product of optimality condition (9) with	∂xopt(α) ∂α	,
	1 C 1	∂C 1 ∂x	∂α	+	1 C 2	∂C 2 ∂x
		∂α ∂C 2 (x opt (α)) ∂α	= =	∂C 1 ∂x ∂C 2 ∂x	∂α	= 1

T ∂x opt (α)

T ∂x opt (α) ∂α = 0

(10)

where α = C 1 (x opt (α)). By deriving C 1 (x opt (α)) and C 2 (x opt (α)) with respect to α we obtain ∂C 1 (x opt (α))

T ∂x opt (α)

T ∂x opt (α) ∂α

13th World Congress in Mechanism and Machine Science, Guanajuato, México, 19-25 June, 2011 A23 294

13th World Congress in Mechanism and Machine Science, Guanajuato, México,19-25 June, 2011