Guang Tan
email: guang.tan@irisa.fr

Marin Bertier
email: marin.bertier@irisa.fr

Anne-Marie Kermarrec
email: anne-marie.kermarrec@irisa.fr

Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks

We study the problem of shortest-path geographic routing in a static sensor network. Existing algorithms often make routing decisions based on node information in local neighborhoods. However, it is shown by Kuhn et al. that such a design constraint results in a highly undesirable lower bound for routing performance: if a best route has length c, then in the worst case a route produced by any localized algorithm has length Ω(c 2 ), which can be arbitrarily worse than the optimal. We present VIGOR, a VIsibility-Graph-based rOuting pRotocol that produces routes of length Θ(c). Our design is based on the construction of a much reduced visibility graph, which guides nodes to find near-optimal paths. The per-node protocol overheads in terms of state information and message transmission depend only on the complexity of the field's large topological features, rather than on the network size. Simulation results show that our protocol dramatically outperforms localized protocols such as GPSR and GOAFR+ in both average and worst cases, with reasonable extra overheads.

I. INTRODUCTION

Geographic forwarding has been widely studied as a routing strategy for large wireless networks, mainly due to its simplicity and scalability. Typically, the routing algorithm greedily advance to nodes that are progressively closer to the destination. When reaching a local minimum, a face (or perimeter) routing method is employed to overcome the local minimum, and then the algorithm resumes greedy forwarding. For a network with uniform and dense sensor deployment in a regular region, such a method produces almost shortest paths with little overhead [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF].

Such geographical algorithms, however, have serious efficiency problems in sensor fields with complex topologies. In many of the real-world environments the sensor field naturally has many obstacles/holes of arbitrary shape and size, causing the algorithm to run into local minima frequently. Yet the algorithms are often satisfied with only being able to escape those local minima, without regard to the efficiency of face routing. For instance, the GPSR protocol [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF] always uses a right-hand rule to route around a hole, ignoring the possibility that there could be a much shorter face boundary path in the opposite direction. A series of subsequent work [START_REF] Kuhn | Geometric ad-hoc routing: Of theory and practice[END_REF]- [START_REF] Kuhn | Worst-case optimal and average-case efficient geometric ad-hoc routing[END_REF] has extended this strategy to offer shorter worst-case paths than GPSR. Unfortunately, as shown in [START_REF] Kuhn | A Asymptotically Optimal Geometric Mobile Ad Hoc Routing[END_REF], in the worst case a route produced by any localized algorithm has length Ω(c 2 ), c being the shortest possible path length. In a largescale network where c can be at the order of tens or hundreds, the multiplicative factor c clearly means an excessive waste of energy and, very possibly, an unacceptable latency. . Illustration for VIGOR. The overlay network VON runs a distance vector algorithm to find shortest Euclidean distance paths, while in the physical network, a face algorithm VIG-FACE (or its greedy variant VIG-GREEDY) realizes the routing between two overlay nodes. The face algorithm is designed in such a way that the hop count between two (visible) nodes u and v is within a constant factor of their Euclidean distance |uv| on the plane.

To improve this situation, a variety of optimization techniques have been proposed that use a limited amount of non-local information, for example by exploiting local face information [START_REF] Fang | Locating and Bypassing Routing Holes in Sensor Networks[END_REF], [START_REF] Leong | Path vector face routing: Geographic routing with local face information[END_REF], or by using some kind of abstract representation of the field topology [START_REF] Bruck | MAP: Medial Axis Based Geometric Routing in Sensor Networks[END_REF], [START_REF] Fang | GLIDER: Gradient landmark-based distributed routing for sensor networks[END_REF], [START_REF] Jiang | An information model for geographic greedy forwarding in wireless ad-hoc sensor networks[END_REF]. However, none of these heuristics provides any constant bound on path stretch. In this context, a natural question arises: Is it possible for the protocol to achieve Θ(c) performance while remaining scalable? Being scalable requires that the protocol's per-node overhead must be independent of, or grow very slowly with, the increase in network size N . This paper presents the first protocol that achieves this goal.

The protocol, called VIGOR, is based on visibility graphs (VGs), a structure in computational geometry that is often used to find shortest paths in an environment with obstacles. Using the information of detected hole boundaries, we develop techniques to construct a much reduced VG, which captures the field's topology in a form of size proportional to the complexity of the field's large geometric features (e.g., the number of holes above a certain size). The fact that such features are usually very small compared with N allows us to build a small overlay network, called a Visibility-based Overlay Network (VON), on top of the physical network. In the VON, nodes run a distance-vector based protocol (e.g., DSDV [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[END_REF]) to route packets along paths of shortest Euclidean distance.

Within this framework, one of our major contributions is a face routing algorithm, called VIG-FACE, that routes between two visible VON nodes. (See Figure 1 for an illustration.) This algorithm is proved to produce paths with a constant hop stretch between two nodes that are visible to each other. In conjunction with the distance vector algorithm at the overlay level, it enables VIGOR to achieve Θ(c) routing performance between general communication pairs. The per-node overhead depends only on the complexity of the large geometric features, rather than on the network size.

To improve the average-case efficiency of the protocol, we also develop a greedy version of VIG-FACE, which leads to the protocol VIGOR-G. Simulation results show that VIGOR-G produces near-optimal-length routes and dramatically outperforms protocols such as GPSR and GOAFR+ in both average and worst cases (by up to an order of magnitude), at low extra message and memory overheads.

II. MODEL AND PRELIMINARIES

A. Model

We assume that a total of N nodes, each with a distinct ID, are placed in the Euclidean plane R 2 , forming a connected network. Every node knows its own location, and a source knows the location of a destination through some location management system [START_REF] Das | Performance Comparison of Scalable Location Services for Geographic Ad Hoc Routing[END_REF]. The network is planarized by some algorithm (e.g., CLDP [START_REF] Kim | Geographic Routing Made Practical[END_REF]), so that no two edges cross each other in the graph. There is a maximum radio range, normalized to be 1, for all the nodes. The radio model does not need to be regular. |uv| denotes the Euclidean length of the line segment uv; D G (u, v) denotes the shortest Euclidean path length between u and v on the graph G.

B. Visibility Graphs and Shortest Paths

It is shown [START_REF] Alt | Visibility graphs and obstacle-avoiding shortest paths[END_REF] that the path of shortest Euclidean length between two points s and t in the plane avoiding polygonal holes/obstacles is a connected series of line segments, whose inner vertices are vertices of the holes. Consequently, any edge of a shortest path is a straight line segment e between two vertices p and q of holes. Since e does not cross any hole, p and q are "visible" from each other. The graph formed by all the hole vertices and these "visibility segments" is called the Visibility Graph (VG) of the polygonal environment; see Figure 2(a) for an example. In such a graph, the set of vertices that can be seen by a certain vertex p is called p's visibility set, denoted Φ p . Likewise, a vertex p's edge visibility set is defined as the set of hole edges that can be seen by p, where an edge can be seen iff at least one point on that edge is visible. As such, the problem of finding shortest obstacle-avoiding path between two points reduces to how to construct the VG and how to search for the shortest path in the VG.

A Reduced Visibility Graph (RVG) technique can be used to reduce the number of edges in a VG. The line segment xy is a tangent segment iff its prolongation is tangent to the holes at both x and y. A RVG is a subset of VG that has all non-tangent segments removed (see Figure 2(b)). It can be proved that the RVG contains the shortest path between a pair of source and destination points as well [START_REF] Alt | Visibility graphs and obstacle-avoiding shortest paths[END_REF].

C. Visibility-Graph-based Routing

The basic idea of VG-based routing is to first identify the sensor nodes that represent the "hole vertices", and then organize those nodes into a Visibility-based Overlay Network (VON). If the VON is small enough in size, we can afford using a distance vector (e.g, the DSDV) protocol to maintain a shortest (Euclidean distance) overlay routing table at each VON node. When a source nodes wants to route to some destination node, it only needs to join the VON and route on the VON. The VON path can serve as a reference for finding a shortest path in the underlying network. Given the framework, we need to address two technical challenges: how to construct a small VON, and how to route between two VON nodes efficiently.

III. CONSTRUCTING A SMALL VON

A. Detecting Holes

In a planar graph, a face can be viewed as a closed (polygonal) region represented by a sequence of nodes and directed edges. In this sequence, a node can appear more than once but edges cannot. The size of a face is defined as the number of edges in such a sequence. A face is said to be a big face if its size is greater than η, where η is a system parameter, and a small face otherwise. A big face is also called a hole for its great impact on routing performance. An example of holes is given in Figure 3(a), where η = 15 and the hole boundary nodes are shown in blue (darker color).

Each node p has a set of adjacent faces. For each face F p in this set, p periodically routes a probing packet along F p 's boundary. This is done by routing to some fake point p within p's interior angle at F p and where no sensor node exists. Following the simple right-hand rule as widely used by geographic protocols such as GPSR and GOAFR+, such a packet will finally create a loop [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF], which can be detected by p when the packet first returns. All the face probing packets are piggybacked with existing keep-alive beacons so no extra messages will be occurred.

To reduce message length, the face probing packets are dropped at a node that has a larger ID than the packet source node. As a result, only the node with the highest ID on a face F p can receive its own packet. Such a node becomes F p 's header. The face probing packet can easily carry the number of hops it has completed, so that the face header can learn the face's size. If F p 's header finds that F p is a big face, then it sends a second packet around F notifying all the nodes en route of F p 's size. After this, F p 's header can start to generate a VON polygon for F p .

B. Constructing the VON Polygons

A hole's header node initially takes itself as the first VON node on its current hole, and then sends out a packet which will traverse the hole boundary in a clockwise direction. The packet has three fields: field 1 containing a sequence of locations of the VON nodes determined so far, field 2 containing a sequence of locations of all the nodes starting from last VON node up to current node, and field 3 containing a parameter ω > 0. Every time a node becomes a new VON node, it first appends its location to field 1 of the packet, and then replaces the content of field 2 with its location, and finally forwards the packet to the next node. Upon receiving the packet, a node first appends its location to field 2 of the packet, and then checks whether the following two conditions hold: (1) there exists a rectangle that covers all the locations contained in field 2. The rectangle, called a bounding bar, has a maximum width ω, and an unconstrained length (see Figure 3(a) for an illustration); (2) the sequence of locations in field 2 has a monotonic sequence of projection points on the length-unconstrained sides of the bounding bar. If these two conditions are met, then the packet proceeds to the next node on the boundary; otherwise the current node becomes a VON node. When the packet returns to the hole header node, the header node can construct a sequence of edges from the location sequence contained in field 1 of the packet, which forms a VON polygon.

It is possible that the VON polygon generated has intersecting edges. In this case we need to make a finer approximation of the original hole by creating more VON nodes. Suppose that the header node has found two intersecting edges v 1 v 2 and v 3 v 4 . (The case of more intersecting edges can be handled similarly.) It performs the above hole approximation procedure a second time, with two changes: (1) the locations of v 1 , v 2 , v 3 and v 4 are recorded in the packet as a new field, and ( 2) ω ← ω/2 in field 3. The newly added field tells that new VON nodes need be created only between v 1 and v 2 , and between v 3 and v 4 , so nodes outside the two ranges only need to forward the packet. The decreased ω makes a bounding bar less able to accommodate many nodes, so that a new VON edge spans fewer nodes, and new VON nodes can be created. Note that as ω tends to zero, the created VON polygon tends to overlap with the original hole boundary.

The intersection avoiding procedure is repeated until there is no intersection between the VON edges in the ranges (v 1 , v 2 ) and (v 3 , v 4 ). Finally, an intersection-free polygon will be created at the hole header node. This intersection-free property can be guaranteed since in the extreme case where the VON polygon reduces to the original hole boundary, the VON polygon will be free of intersection, because of the planar property of the underlying network graph. Our experiments show that self-intersection happens rarely when the initial ω is appropriately chosen (e.g., ω = 0.5).

After determining a locally intersection-free VON polygon, a hole header node can broadcast the polygon (i.e., the sequence of its vertices) to the network. Note that the hole header node only needs to remember the VON nodes, rather than all the nodes, on its face. The broadcast at this stage, however, is not yet for constructing the final VON; instead it is only for detecting possible intersections between VON polygons created from nearby holes. Every hole header node periodically broadcasts its VON polygon information, and at the same time collects the broadcast messages from the network and checks if there are inter-hole intersections. Every time an intersection has been found, the hole header node performs the intersection avoiding procedure described earlier.

The broadcast stops when a hole header node can find no intersection on its own VON polygon.

After all the above procedures, the hole header nodes can start broadcasting the VON polygons to the network -this time for completing the construction of the VON. Every node (not only the VON nodes) in the network maintains an edge set containing all the edges it can see, and updates the set each time it receives a broadcast message. From this edge set, a node can determine the set of VON nodes it can see, that is, its visibility set Φ. The visibility relationship between VON nodes directly translates to VON edges, which, along with the VON polygons already identified, constitute the VON. An example of VON is given in Figure 3(b).

C. Reducing the Number of VON Edges

In order to lower the message overhead of the distance vector protocol, we use Yao graph [START_REF] Yao | On constructing minimum spanning trees in k-dimensional spaces and related problems[END_REF] to reduce the number of VON edges from O(N 2 von ) to O(N von ), where N von denotes the number of nodes in the VON. The Yao graph with an integer parameter k > 6 is defined as follows. At each node v, draw k equally-separated rays from v which define k cones. In each cone, remove all edges, if there is any, except the shortest one incident on v; ties being broken arbitrarily. The resulting graph is known to be a spanner subgraph of the original graph [START_REF] Yao | On constructing minimum spanning trees in k-dimensional spaces and related problems[END_REF].

Using the idea of Yao graph, we propose an algorithm called VON-SPARSIFY to reduce the number of VON edges. In this algorithm, when a node v picks a neighbor in a certain cone C v , it first checks whether C v contains a visible node u such that vu is a tangent edge. Only when this condition holds does v establish a link to the nearest visible node u in C v (here vu need not be tangent). Since non-tangent edges never appear in a shortest path in the VG, their removal will not affect the spanner property of the generated subgraph.

The Yao graph technique is also applied to non-VON nodes. For each non-VON node s, this will select at most k nodes out of s's visibility set Φ s for establishing (virtual) links. These nodes define s's selective visibility set, denoted Φ s .

D. Reducing the Number of VON Polygons

Increasing the parameter η can reduce the number of VON polygons generated, yielding a smaller VON. For example, in Figure 3, increasing η = 15 to 40 will result in a smaller VON without the smaller triangular hole. No doubt there is a tradeoff between the size of VON and routing performance, which will be analyzed in the next section.

IV. THE VIGOR ROUTING PROTOCOL

The VIGOR protocol integrates two components: the distance vector algorithm which is responsible of shortest path (in terms of Euclidean distance) routing on the VON, and a face algorithm that routes between two VON nodes in the physical network. Given a source node s and a destination node t, VIGOR first needs a procedure to determine whether the route needs to go through the VON, and if it does, at which node s the route enters the VON and at which node t it exits the VON.

A. Establishment of VON Routes

The node s first checks whether t is visible. It is easy to verify that t is visible to s iff st does not intersect any edge from s's edge visibility set. If t is found to be visible, then s = s and t = t, which means that the route does not need to go through the VON; otherwise s needs some extra communication to determine s and t .

First, s sends its visibility set Φ s (piggyback with its first packet) to t. Since a shortest path between s and t (or stpath for short) has not yet been established, the packet has to follow a sub-optimal path. This path can be generated using a simple existing algorithm such as GPSR or GOAFR+. We adopt the latter in the paper.

When t receives the packet containing Φ s , it forwards the set to each member of t's selective visibility set

Φ t . (Note that |Φ t | ≤ k.) Next, each v ∈ Φ t uses its VON routing table to select a VON node u ∈ Φ s such that D v = |su| + D von (u, v) + |vt|
is the smallest. Here D von (u, v) means the shortest distance between u and v in the VON. Each v then sends a packet containing the chosen u and calculated D v back to t. All these communications use the GOAFR+ algorithm. Now, t picks the v such that D v is the smallest, lets t = v and s be the node u chosen by v, records t and s to a packet, and sends it to s -this time along the VON path. After receiving this packet, s knows s and t . In future transmissions, every packet from s will contain the nodes s 4. The H-distance set that covers the nodes visited by VIG-FACE's routing between two visible VON nodes u and v. F 1 and F 2 are small faces and F 3 is a big face, B is a bounding bar of F 3 , and B is a rectangular sub-area of B that contains a path between p and q. The small oval-shaped area is Ψ(p , q, ω). and t . This information will be used by the distance vector algorithm for routing on the VON.

B. Routing Between Two Visible Nodes

VIGOR uses a pure face routing algorithm to route from two visible nodes u and v. Here u and v can be the communication source/destination nodes or VON nodes. The algorithm uses a concept called the H-Distance Set. An H-Distance Set of a line segment uv on the plane, denoted Ψ(u, v, H), is the set of points whose distance from uv is no greater than H. Here the distance of a point from uv is the smallest distance between that point and all points on uv. Geometrically, Ψ(u, v, H) corresponds to an oval-shaped area as illustrated in Figure 4.

The face routing algorithm of VIGOR, referred to as VIG-FACE, consists of the following steps.

Algorithm VIG-FACE (u, v)

Let p be the currently visited node; pnearest be the closest point to v the route has met so far on uv; Fp be p's current face (i.e., p's adjacent face intersected by pnearestv); pnext be the next node to visit on Fp. While v is not directly reachable, repeat the following face routing process (in the clockwise direction by default):

1) If Fp is a big face, then start exploring the boundary of Fp.

At each node, check whether the route will a) encounter a VON node other than v and p, or b) go beyond the boundary of Ψ(u, v, ω), or c) cross uv at a point that is farther from v than pnearest. If so, turn back and explore the boundary of Fp in the opposite direction. Continue until reaching a node q such that qqnext intersects uv at a point p closer to v than pnearest. Let p ← q if qnext does not lie on uv, or p ← qnext otherwise; let pnearest ← p .

2) If Fp is not a big face, then explore the whole boundary of Fp, at the same time updating pnearest; after returning to p, advance to the node q such that qqnext intersects line uv at pnearest. Let p ← q if qnext does not lie on uv, or p ← qnext otherwise.

Figure 4 gives an example of the algorithm routing through three consecutive faces.

C. VIGOR is Correct

We examine VIG-FACE(u,v)'s behavior on the two types of faces. We first assume that the VON is correctly constructed; the handling of exceptions will be discussed later. When the current face F p is not a big face, the algorithm ensures that a positive progress will be made toward v after routing on F p . When F p is a big face, the following lemma shows that the algorithm will also make a progress toward v. (The proofs of all lemmas and theorems can be found in [START_REF] Tan | Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks[END_REF]).

Lemma 1: Suppose p and q are two neighboring intersection points between the VON edge uv and a big face F b p . Then there exists at least one p q-path on F b p 's boundary that does not contain an intermediate VON node.

Suppose VIG-FACE(u,v) starts traversing the big face F b p from a node adjacent to p , that is, from a node p such that pp next crosses uv at p (or from p itself if p is a real node). Lemma 1 suggests that there must be a pq-path that does not contain an intermediate VON node, thus justifying the turning-back operation of VIG-FACE when it encounters a VON node other than v and p. Lemma 1 also implies that both p and q are covered by the same bounding bar B. Because the boundary nodes in B have monotonic projections on B's length-unconstrained edges, this further means that there exists a p q-path whose nodes are all covered by a shorter bar B , which is intersected by uv at p and q, shown as a shaded area in Figure 4. It is possible to verify that B ⊂ Ψ(p , q, ω) ⊂ Ψ(u, v, ω). Hence, there exists a p q-path on F b p 's boundary whose nodes are all covered by Ψ(u, v, ω). This explains why VIG-FACE turns back when it hits the boundary of Ψ(u, v, ω). Now that a path leading to q is guaranteed to be found in the region scoped by Ψ(u, v, ω), VIG-FACE can finally make its way to q, making a positive progress toward v.

In summary, VIG-FACE makes a positive progress toward v every time it completes executing on a face. This ensures that v will be finally reached because there are a finite number of faces in the network. Together with the correctness of the distance vector algorithm (e.g., [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[END_REF]) this establishes the correctness of VIGOR.

VIGOR's correctness is robust to network dynamics. In normal cases, for VIG-FACE(u, v) the two nodes u and v are visible. When nodes fail or new nodes are added to the network, v may be no longer visible to u, or may lose its role as a VON node. This will by no means affect the correctness of VIG-FACE, since the algorithm will still follow the principle of face routing -traverse a face, make a progress, traverse the next face, and so on. The only thing affected is the direction chosen for face routing, which may mislead the packet into longer (but viable) face boundary paths and result in suboptimal performance.

In the case that the node v fails or becomes unreachable, the algorithm can detect this by checking whether it has completed traversing a face without getting closer to v. The routing error will be reported to u, which can find an alternative VON route in its routing table and try routing again.

D. VIGOR Has Constant Stretch

In this section we analyze the performance of VIGOR. We adopt the widely used unit disk graph (UDG) model [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF] to represent the network. (This assumption is needed only in this section.) To avoid pathologic network topologies (e.g., one in which a node has O(N ) degree), we employ an alternative planarization algorithm developed by Wang and Li [START_REF] Wang | Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks[END_REF] that guarantees a bounded degree χ for every node. Such a localized algorithm also generates a spanner, meaning that for any two nodes, their shortest path length in the subgraph is within a constant factor δ, called the stretch factor, of their shortest path length in the original graph. The resulting graph is referred to as a WL graph. The main result is the following theorem (see a complete proof in [START_REF] Tan | Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks[END_REF]).

Theorem 1: Let L V IG (s, t) be the hop count needed by VIGOR to route from node s to node t, and L OP T (s, t) be the hop count of a shortest possible path between s and t in the network, then

L V IG (s, t) ≤ 64δ(χ + 1)(H + 1)(H + 1 + 2/π) 1 -2 sin(π/k) L OP T (s, t),
where H = max{ω, η/2}. Proof: (Sketch) We first consider the case where both s and t are not within any VON polygons, which suffices to show the main idea of the proof. Consider the non-trivial case in which |st| > 1.

First, we look at the algorithm's behavior between two adjacent VON nodes (or between an endpoint and a VON node). Again consider the non-trivial case |uv| > 1. For a big face F b , we already know from the correctness analysis that the algorithm can route around it without going beyond the region scoped by Ψ(u, v, ω). For a small face F s , which has at most η boundary edges (and hence a perimeter at most η), the algorithm can go at most η/2 far away from uv, because otherwise F s would have a perimeter greater than η. Thus, Ψ(u, v, η/2) suffices to bound the region visited by the algorithm when exploring a small face. Combining these two cases gives that the nodes visited by the algorithm while it routes between u and v are bounded by the Hdistance set of uv, where H = max{ω, η/2}. Now we use a technique due to Kuhn et al. [START_REF] Kuhn | Geometric ad-hoc routing: Of theory and practice[END_REF] (Lemma 4.1) to bound the number of nodes within that region. Applying this result to Ψ(u, v, max{ω, η/2}) yields an upper bound of the number of nodes visited by VIG-FACE:

N V IG (u, v) ≤ 16(χ + 1)(H + 1) H + 1 + 2 π |uv|,
where H = max{ω, η/2}. From the description of VIG-FACE, we can see that the algorithm visits any node of a small face at most twice. Also, the p nearest has the effect of preventing the algorithm from traversing any edge of a big face more than twice. Thus for any particular face, the algorithm visits any node at most two times. Considering the fact that a node can belong to at most two adjacent faces that are intersected by the line uv, we can conclude that a node in the region Ψ(u, v, max{ω, η/2}) will be visited at most four times by the algorithm. Therefore, the hop count needed by VIG-FACE(u, v) is:

L V IG (u, v) ≤ 4N V IG (u, v)
where H = max{ω, η/2}.

Next, consider an st-path that avoids the VON polygons; that is, does not contain a point lying inside any VON polygons (but can touch the boundary of the VON polygons). We denote its minimum Euclidean length by D R 2 (s, t). Let G von be the graph corresponding to the VON as defined in Section III, G von+ be G von augmented by adding s and t, as well as the edges determined by the visibility relationship between s, t and all the VON nodes, to G von . Applying the VON-SPARSIFY algorithm to G von and G von+ generates two subgraphs, Y G von and Y G von+ , respectively. By combining Clarkson's induction technique [START_REF] Clarkson | Approximation Algorithms for Shortest Path Motion Planning[END_REF] with Lukovszki's result [START_REF] Lukovszki | New Results on Geometric Spanners and Their Applications[END_REF] (Lemma 2.2), we can prove that D Y Gvon+ (s, t)

≤ 1 1-2 sin(π/k) D R 2 (s, t).
When VIGOR determines s's VON entry and exit nodes , it actually finds a shortest st-path via the edges in the union of Y G von+ 's edge set and the set of visibility edges between s and all nodes in Φ s , which is a superset of Y G von+ 's edge set. Since the addition of edges to a graph does not increase the shortest path length between any two nodes in that graph, the shortest st-path length found by VIGOR, denoted D V IG (s, t), is no greater than the shortest st-path in Y G von+ . Hence,

D V IG (s, t) ≤ D Y Gvon+ (s, t) ≤ 1 1-2 sin(π/k) D R 2 (s, t).
Let P(s, t) be the edge set of the VON path from s to t, then we have

L V IG (s, t) = (u,v)∈P(s,t) L V IG (u, v) ≤ 64(χ + 1)(H + 1)(H + 1 + 2/π) (u,v)∈P(s,t) |uv| = 64(χ + 1)(H + 1)(H + 1 + 2/π)D V IG (s, t) ≤ 64(χ + 1)(H + 1)(H + 1 + 2/π) 1 -2 sin(π/k) D R 2 (s, t), ( 1
)
where H = max{ω, η/2}. Last, consider a shortest st-path on the WL-graph, whose Euclidean length is denoted by D W L (s, t). We can prove that D R 2 (s, t) ≤ D W L (s, t). Denote the minimum length of an st-path on the UDG by D UDG (s, t). Then we have

D R 2 (s, t) ≤ D W L (s, t) ≤ δD UDG (s, t) ≤ δL OP T (s, t)
where δ is the stretch factor of the WL-graph. Combined with (1), this proves the theorem.

If either s or t is within some VON polygon, the VON routing needs to be slightly modified in order to ensure optimality. The details and proof are omitted here.

The stretch result presents a salient feature of our protocol. To the best of our knowledge, no prior geographic routing algorithm has achieved a constant bound (even in a UDG graph). Note that the correctness of our protocol does not need this UDG assumption.

V. VIGOR-G: A GREEDY+FACE PROTOCOL

In this section, we present a protocol, named VIGOR-G, that combines greedy routing and face routing. This protocol also runs on a planar (not necessarily a UDG) network.

VIGOR-G works in the same way as VIGOR except that VIGOR-G incorporates a greedy algorithm, referred to as VIG-GREEDY, to route between two visible VON nodes. This algorithm tries to route greedily toward the destination v whenever possible, that is, by forwarding the message to the neighbor located closest to v. When reaching a local minimum with respect to v, the algorithm employs a face routing to overcome the local minimum.

When VIG-GREEDY reaches a local minimum at a node p, it uses the following two rules to determine the "right" face routing direction based on the information of p's associated VON edge P ccw P cw , where P ccw and P cw represent p's VON node neighbors counter-clockwise and clockwise on the face, respectively. (If more than one such edges exist in the case of a complex VON polygon, then one is picked randomly.) Note that P ccw and P cw both belong to p's visibility set.

1) Direction Rule 1: If p is not a VON node, then calculate its projection point p on the line P ccw P cw . If pv is angularly closer to p P ccw than to p P cw , then take the counter-clockwise direction, otherwise take the clockwise direction. In Figure 5(a), the grey half disk represents the angular range for pv to choose a counterclockwise direction. 2) Direction Rule 2: If p is a VON node, then if pv is angularly closer to pP ccw than to pP cw (Figure 5(b)), take the counter-clockwise direction; otherwise take the clockwise direction. It is possible that the line pv crosses a VON polygon (Figure 5(c)), which may lead the packet into the wrong direction and create a big detour. VIG-GREEDY determines whether this is happening by checking whether pv intersects any of p's associated VON edges. For a particular VON edge P ccw P cw , if p is on the right of this edge, it means that p is inside the VON polygon that contains P ccw P cw ; in this case the algorithm first calculates p's projection p on P ccw P cw and then checks whether p v intersects P ccw P cw . The above procedure is performed every time the algorithm hits a big face boundary node except during the face routing. The rule for choosing a direction in this case is as follows:

Direction Rule 3: If pv (or p v in the case that p is within the VON polygon that contains P ccw P cw ) intersects P ccw P cw , then take a counter-clockwise direction if p is on the left of the line uv, otherwise take a clockwise direction.

After determining the face routing direction, the algorithm routes along the face boundary until a node q such that qq next intersect pv at some point closer to v than p.

When VIG-GREEDY starts face routing at node p, the next face to traverse is the face intersected by pv, where v is next VON node on the path. This guarantees that a positive progress toward v is made after every face routing procedure. According to Frey and Stojmenovic's result (Theorem 4) [START_REF] Frey | On Delivery Guarantees of Face and Combined Greedy-Face Routing in Ad Hoc and Sensor Networks[END_REF], the face routing procedure along with the greedy steps' progressive forwarding can guarantee delivery in a planar graph. Together with the correctness of the distance vector algorithm, this means that VIGOR-G is correct in general planar graphs. VIGOR-G handles network dynamics or routing exceptions in the same way as VIGOR. Executed with an incorrect VON, it behaves like a traditional greedy+face protocol with face routing directions chosen in a sub-optimal way.

VI. SIMULATIONS

In this section we evaluate the performance of VIGOR-G through simulations. We focus on the algorithm's behavior on the topological level. Comparisons are made with GPSR [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF], GOAFR+ [START_REF] Kuhn | Geometric ad-hoc routing: Of theory and practice[END_REF], and a centralized shortest-path algorithm, which serves as a baseline. The sensor network is deployed in a 1000m × 1000m square field with irregular holes. Figure 6 shows four example field layouts. The number of sensors ranges from 2958-3732. Sensor nodes are placed on a grid and then perturbed with a random shift following a normal distribution [START_REF] Bruck | MAP: Medial Axis Based Geometric Routing in Sensor Networks[END_REF]. The generated networks remain connected. For the construction of VONs, the Yao-graph parameter k is set to 7. The maximum width of a bounding bar ω is 30 meters. The threshold size for a face to be a hole, η, is set to 15 by default. Each sensor has a communication range of 60 meters. We have considered both UDG and quasi-UDG radio models. Since the advantage of VIGOR/VIGOR-G comes from its capturing large topological features, local variation in connectivity has little effect on its global behavior, and thus does not fundamentally change the comparative results. We therefore only report on the case of UDG radio model.

Hop Stretch

We randomly pick 3000 pairs of source and destination nodes in the network and run the four routing algorithms for those pairs. For each pair, the path length in terms of hop count produced by the centralized algorithm is taken as the baseline, and the other three algorithms are compared in terms of path stretch, that is, the ratio of a path's length to the baseline value. Figure 7 plots the stretch value distributions of the algorithms under the four field layouts in Figure 6.

All the four plots show that VIGOR-G has a significant smaller stretch than GPSR and GOAFR+. For instance, in Figure 7(b), VIGOR-G has a mean stretch of 1.05, in contrast with GPSR's 4.10 and GOAFR+'s 5.26. This indicates that VIGOR-G achieves near-optimal performance in average case, and considerably outperforms the other two representative algorithms.

The worse-case behavior of the algorithms can be observed from the maximum stretch values. With this metric, an even bigger difference can be found between these algorithms. Throughout the experiments, the stretch of VIGOR-G remains below 2.0, while the other two have a stretch varying widely. For instance, in Figure 7(b), GPSR produces a stretch as high as 56.17, nearly 30 times that of VIGOR-G's peak value of 1.91. In other cases, GPSR and GOAFR+ consistently produce a maximum stretch nearly an order of magnitude higher than that of VIGOR-G. The great advantage of VIGOR-G in the worst case also suggests that our heuristics are successful.

Protocol Message Overhead In addition to the keep-alive beacons between neighbors, the VIGOR-G protocol requires extra messages to (re)construct the VON, broadcast the VON polygons, and to run the distance vector algorithm on the VON. Assuming an inter-node beacon interval of b = 1 second [START_REF] Broch | A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols[END_REF], [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF] and taking the beacon message overhead as a baseline, we simulate the maintenance of VON and compare the protocol's overhead with the baseline.

The maintenance of VON involves all the boundary nodes of holes. Since face probing packets are all piggybacked with the keep-alive beacons, we only need to consider the packet issued by hole header nodes. We assume that a hole header reconstructs its VON polygon and broadcast the polygon every b 1 time, where b 1 is adjustable. For the message overhead of the distance vector algorithm running on the VON, we take the DSDV protocol [START_REF] Perkins | Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[END_REF] as a running example and borrow the experimental setting from [START_REF] Broch | A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols[END_REF]. In [START_REF] Broch | A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols[END_REF], the periodic route update interval for DSDV is set to 15 seconds. Taking into account the triggered updates, the effective rate of protocol message transmission is one update per node per second. We let the update messages be transmitted over the VON edges, which correspond to the paths generated by VIGOR-G in the underlying network.

Table I shows the protocol overhead measured in number of messages per second for varying b 1 ; the baseline overhead is given in the parenthesis. It can be seen that for all the settings, VIGOR-G has an overhead within a moderate factor of the baseline. For instance, for the field topology Figure 6(a) with b 1 = 15 (the same as the VON route update interval), the protocol overhead is 4849 messages per second, which translates to 1.4 messages per node per second. We believe this is a reasonable overhead for a single node.

It should also be noted that the settings in [START_REF] Broch | A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols[END_REF] are for a dynamic network with high node mobility. In a static setting, the update of the VON structure and the VON routing tables can be performed at a much lower frequency, which leads to an even smaller protocol overhead.

Memory Requirement VIGOR-G requires every VON node to maintain a routing table, which is of size O(N von ).

In our experiments, the sizes of VONs are at the order of tens. Every non-VON node in the network is also required to remember an edge visibility set (which also contains its node visibility information). Theoretically, this set is of size O(N von ); in practice, it is usually much smaller than N von . For instance, in our experiments, a non-VON node needs to remember at most 21 visible edges, each represented by two points, in the four field layouts in Figure 6. These requirements are unlikely to be a concern for current sensor hardware.

Effect of the Parameter η

The parameter η determines whether a face is a hole, thus needs to participate in the VON.

Intuitively, the smaller η is, the more VON polygons there will be in the VON, and the closer the generated path length will be to the optimal. On the other hand, the larger VON requires more messages transmission and memory to maintain. Figure 8 shows the VON constructed for the field layout Figure 6(c) under different η. When η = 15, the VON has a size of 92; increasing η to 55 yields a much sparser VON of only 49 nodes; see Figure 8(b).

We vary η to examine the tradeoff between path quality and protocol overhead in terms of N von and the total number of VON maintenance messages. The trend agrees well with the intuition discussed above. For example, when η = 25, the average stretch is 1.083; for η = 100, the average stretch increases slightly to 1.130. For these two cases, the message overhead is 8162 and 7136 messages per second, respectively. The results suggest that allowing only a small extra overhead can significantly improve routing performance as compared with a localized algorithm.

VII. DISCUSSION

Scaling Issues

The per-node protocol overhead of VIGOR(-G) is O(N von ), where N von is the number of VON nodes. N von indeed reflects the field's geometric complexity, embodied by the number, size, and shape of holes above a certain size. What justifies the VIGOR protocol is the fact that in real-world environments, the geometric complexity is often low enough compared with the network size, allowing the protocol to run without overloading sensor nodes. For example, the number of buildings, or the number of boundary edges of buildings, in a factory or a campus, is usually very small compared with the number of sensors that could be deployed in such environments. For even more geometrically complex fields and larger systems, choosing suitable parameters η and ω provides a convenient way to tradeoff between protocol overheads and path quality.

Network Dynamics We expect that in a static sensor network, topology changes are usually local and happen infrequently (due to, e.g., depletion of energy or external damages), so salient, global features like large holes in the communication graph are rather stable under those local changes. This justifies a low-frequency update of the visibility graph which leads to low overheads. Even if the VON becomes very inaccurate due to massive network errors, only the performance will be affected; the protocol will remain correct.

VIII. RELATED WORK

Many efforts have been made to improve the performance of localized face routing algorithms or their greedy variants. Kuhn et al. [START_REF] Kuhn | A Asymptotically Optimal Geometric Mobile Ad Hoc Routing[END_REF] propose a localized algorithm that can achieve asymptotically optimal performance in a UDG network. In [START_REF] Kuhn | Geometric ad-hoc routing: Of theory and practice[END_REF], they further propose GOAFR+, a protocol that achieves good average-case performance while preserving worst-case optimality. In [START_REF] Kuhn | A Asymptotically Optimal Geometric Mobile Ad Hoc Routing[END_REF], Kuhn et al. prove that any localized algorithm can produce path length quadratic of the optimal, which is undesirable in a large-scale network. Thus, in order to guarantee finding a reasonably short path, using a certain amount of non-local information is inevitable. In this direction, Leong et al. [START_REF] Leong | Path vector face routing: Geographic routing with local face information[END_REF] have proposed Path Vector Face Routing, which achieves superior performance to GPSR by having nodes remember some information about their local faces. A similar approach has also been suggested in [START_REF] Fang | Locating and Bypassing Routing Holes in Sensor Networks[END_REF] to support "path migration" and improve path quality. Both sets of research, however, only consider optimization on local faces. When it comes to a network with faces of arbitrarily complex shape and large size, the limited horizon makes them unable to find a globally short path.

In [START_REF] Arad | Minimizing recovery state in geographic ad-hoc routing[END_REF], Arad et al. present a Node Elevation Ad-hoc Routing (NEAR) scheme that assigns virtual coordinates to nodes so that local minima can be avoided more efficiently. Very recently, Jiang et al. [START_REF] Jiang | An information model for geographic greedy forwarding in wireless ad-hoc sensor networks[END_REF] propose a novel information model in which a hole and its affected nodes are identified as an unsafe area. In so doing the algorithm can save many steps by avoiding entering an area that does not contain a path to the destination. While these heuristics are shown to be very beneficial for routing performance, neither is proved to provide a bound on path stretch.

Bruck et al. [START_REF] Bruck | MAP: Medial Axis Based Geometric Routing in Sensor Networks[END_REF] propose MAP, a naming and geographic routing protocol that produces globally short paths using medial axis graphs (MAGs). After a preprocessing stage, a MAG is stored at each node in the network. With MAG, routing is first planned on the abstract medial axis graph, and then realized in each canonical region. In [START_REF] Fang | GLIDER: Gradient landmark-based distributed routing for sensor networks[END_REF], a protocol called GLIDER with a similar principle to that of MAP is proposed. MAP and GLIDER share several features with VIGOR: they all try to capture the field's large geometric and topological features in a succinct form, and the routing is performed at two levels: the abstraction level, and the level of underlying networks. One major difference is that VIGOR focuses on shortest path routing and has provable performance, whereas MAP and GLIDER have other focuses and provide no guarantee in this regard.

IX. CONCLUSIONS

We have presented visibility-graph-based geographic protocols for shortest path routing in sensor networks. VGs facilitate routing through topologically complex environments along paths with shortest Euclidean lengths. The proposed protocols show excellent performance with low extra overheads in addition to the requirement by basic geographic routing protocols such as GPSR.

Fig. 1

 1 Fig.1. Illustration for VIGOR. The overlay network VON runs a distance vector algorithm to find shortest Euclidean distance paths, while in the physical network, a face algorithm VIG-FACE (or its greedy variant VIG-GREEDY) realizes the routing between two overlay nodes. The face algorithm is designed in such a way that the hop count between two (visible) nodes u and v is within a constant factor of their Euclidean distance |uv| on the plane.

Fig. 2 .

 2 Fig. 2. An example of (a) visibility graph and (b) reduced visibility graph on a 2D plane. The gray regions are holes. The thick line segments (in red) represent the shortest path between s and t.

Fig. 3 .

 3 Fig. 3. The construction of a VON for a network. With η = 15, the VON has 9 nodes, in contrast with the original network size of 2658. The darker circles and squares represent hole boundary nodes and VON nodes, respectively. For clarity the out boundary nodes and their associated VON edges are not shown.

  Fig.[START_REF] Bruck | MAP: Medial Axis Based Geometric Routing in Sensor Networks[END_REF]. The H-distance set that covers the nodes visited by VIG-FACE's routing between two visible VON nodes u and v. F 1 and F 2 are small faces and F 3 is a big face, B is a bounding bar of F 3 , and B is a rectangular sub-area of B that contains a path between p and q. The small oval-shaped area is Ψ(p , q, ω).

Fig. 5 .

 5 Fig. 5. Heuristics for determining face routing direction in VIG-GREEDY. The squares represent VON nodes. u and v are the source and destination nodes, p is the current node, p is the projection node of p on the line P ccw P cw .

Fig. 6 .Fig. 7 .

 67 Fig. 6. Four 1000m×1000m sensor fields with holes. The red and blue lines show several examples of paths generated by GPSR and VIGOR-G, respectively.

Fig. 8 .

 8 Fig. 8. Effect of η on the VON.

TABLE I NUMBER

 I OF PROTOCOL MESSAGES PER SECOND AS COMPARED WITH THE BASELINE BEACON MESSAGE OVERHEAD (IN PARENTHESIS).

ACKNOWLEDGMENT

We would like to thank Davide Frey and Cigdem Sengul for comments on early drafts of the paper. We also thank the anonymous reviewers for their helpful feedback.


Assistant Professor, Zam-Zam Abdirahman
email: zam-zam.abdirahman@lasalle-beauvais.fr

Professor, Leslie D Bourquin
email: bourqui1@msu.edu

Professor, Loïc Sauvée
email: loic.sauvee@lasalle-beauvais.fr

Deepa Thiagarajan
email: thiagara@msu.edu

Collective initiatives for the implementation of food safety management system standards in the USA and France

Introduction

In modern agrifood systems, the development and effective implementation of food safety and quality management system standards (hereafter FSMS) such as ISO 22000, BRC, IFS and other similar standards is crucial. The food sector, mainly composed of SMEs, frequently faces difficulties in implementing these standards. Indeed, there are many barriers to appropriation of quality management standards which make effective implementation difficult for SMEs, such as limited access to information, lack of financing and cognitive resources, food hazard perception, and insufficient access to adequately trained personnel. Consequently, one fundamental objective for practitioners such as managers, public bodies and development agencies is to help these food SMEs in improving their implementation capacity, which is usually done through the launch of different forms of collective initiatives such as associations, clubs, learning platforms, regional actions and other forms of collaboration. Globally speaking, the objective of these initiatives typically is to develop a step by step approach to identify the benefits of engaging its members in food quality management programs and providing guidance on good practices associated with the implementation of these systems. More specifically, these initiatives are aiming to address the following tasks: the enhancement of the awareness in food quality management principles; the selection of adequate and competent partners such as consultants and coaches; the mobilization of the relevant services; the efficiency of the overall coordination over time; and the implementation of some global managerial recommendations. Nevertheless, the underlying hypothesis of these collective initiatives is rarely adressed, nor is it analyzed and compared in an systematic way. This hypothesis is rooted in a general idea of "network learning": the capacity of SMEs to adopt new food quality management schemes is seen as a whole and necessitates mobilizing, at the same time, 1) formal innovation networks, which bring cognitive resources and institutional credibility, and 2) the practice by managers of informal network activities through interactive exchanges of information, benchmarking, knowledge transfer and translation, and experiential learning.

In this context, the aim of this communication is three-fold. Firstly, it is to craft an original analytical framework in line with the literature on innovation networks, managerial innovation, network learning and related learning effects, specifically devoted to the study of quality management standards appropriation and implementation. This first part is mainly devoted to the identification of three categories of so called "network effects" that are provided by collective initiatives. Secondly, the objective of the communication is to apply this framework to specific collective initiatives conducted in two countries (e.g. USA and France) in order to identify and compare the key relevant network effects induced at SME level by these collective initiatives which occur during the process of FSMS implementation. Thus, the research will identify strengths and weaknesses of these initiatives using a common grid based upon sound theoretical foundations. Indeed, a better understanding of learning processes at the individual as well as collective levels, both in informal (interpersonal) and in formal (organizational) relationships, will provide insights into the major relevant learning principles and their possible adaptation to specific agrifood system sectors and to different national or regional contexts. Thirdly, we propose some concluding comments about the managerial implications derived from this analysis.

1-Network effects in FSMS implementation: emphasizing the interests of collective initiatives Based upon a literature review, we will consider successively three categories of network effects that are relevant for the topic.. These effects are categorized in three categories: (i) The structural effect category finds its roots mainly in the structural analysis of networks; (ii) The interactive effects question more specifically the idea of a networking activity that will support the implementation process; (iii) The cognitive effect focuses on the impact of the time dimension on any networking activity, leading to irreversibility, to path dependency and to the accumulation of new and specific knowledge useful for implementation of FSMS. A synthesis follows.

Exploring the structural dimensions of collective initiatives For [START_REF] Conway | Managing and Shaping Innovation[END_REF] the network perspective applied to innovation research has considerably renewed and extended our knowledge on innovation processes. The starting point of the process of structural analysis is to consider any collective initiative, seen as a network, as a combination of actors and relationships (Burt, 1999[START_REF] Burt | The network structure of social capital[END_REF][START_REF] Borgatti | On social network analysis in a supply chain context[END_REF]. In the structural analysis of networks, the actors are not independent but rather interdependent and influence each other. To take into account the unique situation of each member and the network structure as such, the structural approach combines two complementary perspectives: the global network, that is to say its density, the average distance between each of its members, the existence of subsets more or less structured; and the ego network, that is to say the situation of an actor (an individual, a SME) in its environment and its degree of inclusion, its mode of insertion into the global network (Borgatti and[START_REF] Borgatti | On social network analysis in a supply chain context[END_REF][START_REF] Coulon | The use of social network analysis in innovation research: a literature review[END_REF]. Actors are considered as nodes, and relationships between them as ties. Thus, research on innovation mobilizing the structural analysis of networks [START_REF] Coulon | The use of social network analysis in innovation research: a literature review[END_REF] produces representation of innovation processes as maps [START_REF] Conway | Realizing The Potential Of The Network Perspective, In Social Interaction and Organizational Change: Aston Perspectives on Innovation Networks[END_REF] or charts of nodes and relationships.

Consequently and in considering the FSMS context, two families of components must first be identified: actors and relations. The identification of relationships that these actors have with one another is the second component. In line with social network theorists, these relationships can be of several types: continuous (similarities, relationships, interactions) or discrete (financial flows, knowledge flows), directed or not, measured by value or not, formal or informal [START_REF] Borgatti | On social network analysis in a supply chain context[END_REF]. The process of implementing management system standards such as FSMS systematically typically involves two groups of major actors [START_REF] Abdirahman | France: Case studies 3D Network, ARI Picardie and BioBourgogne[END_REF][START_REF] Hatanaka | Third-party certification in the global agrifood system[END_REF]: individuals (managers, consultants etc.) and organizations (SMEs, standardization bodies such as ISO, the International Organization for Standardization, consular agencies, auditors, governmental bodies, banks etc.). Finally the network reveals itself, by its structural properties, as facilitating (or hindering) the implementation.

Networking activity within collective initiatives

In the context of the implementation of FSMS principles, knowledge transfer to the organization necessitates the mobilization of new cognitive resources and the activation of formal structures. An analytical approach applied to the implementation of FSMS is, therefore, assumed to provide a better understanding of the necessary learning processes. For [START_REF] Berthon | Réseaux sociaux et processus d'apprentissage, une relation complexe et ambivalente[END_REF], the mechanistic perspective is an essential step in that "the transfer of knowledge, considered as the dependent variable, proceeds from an optimal layout between the nature of network and the types of knowledge. The question is often that of a systematic identification of structural and relational properties of the network, as brakes or levers of the knowledge transfer." But this structural determinism cannot explain alone the implementation process. Implementing FSMS implies a set of interdependencies and a permanent adjustment between the actors, their objectives and the context in question. Thus emerges a vision of co-constructed knowledge. In the end, a more complete representation of the relationship between network and organizational learning should show that the network is a "channel for learning but, recursively, that the network is transformed by the learning taking place. In other words, the network is at least partly constructed by the learning processes, dynamically, deliberately and in an emergent manner" [START_REF] Berthon | Réseaux sociaux et processus d'apprentissage, une relation complexe et ambivalente[END_REF].

The ambivalent dimension of the network in the phenomena of innovation is demonstrated by Owen-Smith and Powell (2004), Powell et al. (1996[START_REF] Powell | Network dynamics and field evolution: The growth of interorganizational collaboration in the life sciences[END_REF] and [START_REF] Conway | Managing and Shaping Innovation[END_REF]. By distinguishing the network itself from the networking event, they show that the study of the innovation process involves taking into account both the structural dimension and interactivity. For [START_REF] Conway | Managing and Shaping Innovation[END_REF], there is an interaction between the network as a structure and the networking event taking place in this network, with "on the one hand, the network may constrain or liberate the patterns of interaction and exchanges between network members; on the other, networking behavior may serve either to ossify (i.e. fix) the existing network membership and relationships, or create a dynamic in the membership and relationships within the network" [START_REF] Conway | Managing and Shaping Innovation[END_REF]. In the context of FSMS mobilizing transfers of knowledge, social networks and learning processes are involved. Thus, "the formal structure of network, but also the quality and relational characteristics that are played out, have a role on the nature of the learning that occurs there" [START_REF] Berthon | Réseaux sociaux et processus d'apprentissage, une relation complexe et ambivalente[END_REF]. Simultaneous consideration of structural and relational dimensions are necessary in part according to these authors due to the fact that the individual is demanding of both resources and information but also demands a sense of belonging and social ties.

Collective initiatives as drivers of cognitive resources

The implementation of a FSMS goes through qualitatively distinct stages [START_REF] Henson | The impacts of private food safety standards on the food chain and on public standard-setting processes[END_REF]Humphrey, 2009, 2010) with an evolutionary perimeter of actors involved in the process. These steps are mostly a reflection of the types of actors mobilized and of their changing status or role from one phase to another. It is therefore necessary to consider explicitly the time dimension and its corollary, namely its influence over the types of actors involved, and over the process of adopting the FSMS. This reflects the fact that the implementation is done in the long run and differentially mobilizes actors and resources.

The corollary of such a time dimension in the long run is the impact of knowledge creation and accumulation. Consequently the implementation of an FSMS within a company, with its deep impacts on organizational structures and management procedures, thus requests an original view of the combination between the implementation process and learning phenomena. Change in organization related to learning is an important body of literature, stemming mainly from the seminal works of [START_REF] Argyris | Organizational Learning II. Theory, Method, and Practice[END_REF], and [START_REF] Levitt | Organizational Learning[END_REF]. According to [START_REF] Pawlowsky | The Treatment of Organizational Learning in Management Science[END_REF] and his extensive survey of literature on learning, it is clear that "there are distinct perspectives on organizational learning that differ in respect to certain basic assumptions", nevertheless this author suggests that it is possible "to see outlines of a picture that visualizes basic building stones of an integrative model of organizational learning". His review suggests four different dimensions of learning: system-levels (from individual to network); learning modes (cognitive, cultural, action); learning types (single-loop, double-loop, deutero), and phases.

Following Podolny (1999), and authors in social capital theory (Burt, 1997[START_REF] Burt | The network structure of social capital[END_REF][START_REF] Inkpen | Social capital, networks, and knowledge transfer[END_REF][START_REF] Nahapiet | Social capital, intellectual capital, and the organizational advantage[END_REF], we will identify some characteristics of these cognitive effects that are paramount in the understanding of FSMS implementation. The basic idea for these effects is the fact that at a certain period of its development, learning processes lead to different forms of institutionalization within a formal network, which thus become a kind of "institution", producing its own rules, norms, values and culture, aspects themselves embedded in idiosyncratic resources and skills. In the terms of Powell et al. (1996), the network becomes progressively the "locus of innovation".

Network effects in FSMS implementation: synthesis and managerial implications from a collective initiative point of view

The approach developed of FSMS implementation is the delineation of the structural characteristics of network, of the characteristics of the networking activity and of the network seen as a source of specific cognitive resources. We have seen that this idea of three categories of network effects finds its source in the social capital theory (Burt, 197, 2000;[START_REF] Nahapiet | Social capital, intellectual capital, and the organizational advantage[END_REF][START_REF] Inkpen | Social capital, networks, and knowledge transfer[END_REF] and has already been developed in the context of innovation in general (Zheng, 2010) and managerial innovations in particular (Agarwal et al., 2012). [START_REF] Nahapiet | Social capital, intellectual capital, and the organizational advantage[END_REF] for instance define social capital as 'the sum of the actual and potential resources embedded within, available through, and derived from the network of relationships possessed by an individual of a social unit, it comprises both the network and the assets that may be mobilized though that network". As suggested by Pittaway et al. (2001) and [START_REF] Conway | Managing and Shaping Innovation[END_REF], the connection has been made between the benefits of network and innovation. But the literature on the role and functions of networks on innovation can be approached through at least two interpretations [START_REF] Conway | Managing and Shaping Innovation[END_REF]. In the first one the network is seen as a new way of organizing innovation activities, between market and hierarchy: it is thus the governance aspect that is emphasized. In the second one the network is not considered per se as a specific mode of organizing activities benefiting (or not) to innovation. Instead it is viewed as a new analytical lens interesting to focus on because it produces a wide range of effects, of externalities, that will influence the innovation processes. Doing so, the network is tracked via the effects it may produce, as a phenomenon affecting any economic life.

Interaction effects between individuals for instance will be probably more important at early stages of the implementation processes, while structural dimensions are more predominant in well-established network relationships. Finally, cognitive effects will be mainly related to the institutionalization of a formal innovation network, especially when it becomes formalized into rules, routines and procedures which also tend to create path dependency, organizational memory and common resources. Through two examples in the USA and in France we will show the nature of these effects and the necessary conditions under which these collective initiatives may be beneficial to SMEs.

2-Case study of collective initiatives for FSMS implementation in the USA and France

In the USA (with global implementation): the Food Safety Knowledge Network developed by MSU Beginning in 2008 and in collaboration with several international partners, Michigan State University launched the Food Safety Knowledge Network (FSKN) initiative [START_REF] Geith | Designing corporate training in developing economies using open educational resources[END_REF]. The overall objectives of the FSKN initiative are to 1) develop internationally recognized competences in relation to food safety for individuals at all levels and in all sectors of the food supply chain, and 2) promote knowledge transfer within the food safety community. The FSKN achieves these aims by harmonizing existing technical food safety training schemes through the development of the competencies of food safety professionals, recognized by international stakeholders, both from the public and the private sectors.

The FSKN is a collaborative platform that provides free access to high-quality, standardized learning resources in a highly scalable manner. To that end, all content (cognitive resources) is shared on the internet as Open Educational Resources (OER) under Creative Commons licensing via the FSKN web portals. The FSKN uses open source tools and openly-licensed materials encouraging development of derivative works that only require attribution to source and sharing under similar license as standardized FSKN content. This approach enables other users to customize, translate, and localize content for specific audiences or sectors of the food industry, and share these derivative works through either the MSU FSKN portals or their own web sites.

The FSKN approach has been pilot-tested in a number of countries in collaboration with numerous partners from the food industry (individual companies and associations), development agencies, academic institutions and other service providers. The specific approach has varied somewhat from country to country, but in general the target audience for capacity development has been small-and medium-scale suppliers (both primary producers and food processors) who are seeking to execute sales contracts with multi-national food retailers or other highvalue markets within their country, or to engage in regional or distant trade of their products to more discriminating markets. Gaining access to these higher-value markets (both domestic and export) requires the suppliers to reach a much higher level of sophistication with respect to food safety and quality management systems, and ultimately the execution of sustainable contracts in these markets requires certification of the food safety management systems that are being implemented by these suppliers against recognized international standards.

Organizational level

The FSKN project engages are wide variety of organizations in accomplishing its mission. As the leader of the FSKN initiative, Michigan State University (MSU) and the faculty leading the effort are principally focused on the creation and transmission of knowledge to improve the competitiveness of primary producers (i.e. farmers) and SMEs in less-developed countries. Beyond improving food safety systems implemented by these suppliers, another long-range objective of these efforts is to improve the livelihoods of farm families and front-line workers in these less developed businesses.

Content development in the FSKN initiative is guided by international standards, with programs being delivered on international food safety guidelines adopted by the Codex Alimentarius Commission managed by the Food and Agricultural Organization of the United Nations (which are recognized as the de minimis food standards in member countries of the World Trade Organization) and other programs focused on helping suppliers meet the expectations of international private food safety standards such as those benchmarked by the Global Food Safety Initiative (GFSI). Individuals from several GFSI-member companies have participated in content development for the FSKN since its inception, whereas engagement with public sector food standards representatives (e.g. Codex or individual governments) has been more sporadic.

Content delivery in the FSKN project typically has been conducted by MSU researchers in partnership with academic institutions based in the countries where training is occurring. The partner academic institutions are essential to the effective delivery of the content for local clientele because of the ability to deliver the training and mentoring in local language(s) and also because of their capabilities to localize the content with respect to local practices and cultural norms. It is preferable for MSU to work with local academic institutions in this manner as they share a similar culture of academic inquiry and knowledge dissemination. These collaborations also have a high likelihood of sustainability over the longer term.

The beneficiaries of the capacity development (e.g. farmers or processing establishments and their employees) may self-select for participation in these capacity development programs, but more commonly they are identified as potential or existing suppliers for multinational companies (either for the domestic market or export) who are in need of training and mentoring on the development and implementation of internationally-recognized food safety management systems. Many of the participating beneficiary farmers or manufacturers also are members of cooperatives or other food industry associations, which often work collectively to address key challenges such as compliance with food safety and quality standards. The multinational companies are motivated to identify suppliers for participation in these programs for a variety of reasons, but chiefly it is to help ensure the overall safety and quality of products sourced from these suppliers and, therefore, serves to protect the brand of these multinationals.

A variety of service providers also have engaged in the FSKN project since its inception. These have included third-party certification bodies who provide food safety certification, organizations offering food traceability support, equipment suppliers, sanitation services organizations, chemical suppliers, and providers of other ancillary services to farms or food processors.

Finally, several donor organizations, UN organizations and other NGOs have participated in or contributed to the FSKN initiative since its inception. Donor organizations such as the United States Agency for International Development (USAID) and the World Bank have provided financial support for FSKN development and delivery of programs. In addition, organizations such as the United Nations Industrial Development Organization (UNIDO) and the International Finance Corporation (IFC) of the World Bank Group have utilized FSKN-created materials in their own development projects that are focused on food safety capacity development in a number of countries. For the FSKN initiative, organizations such as UNIDO and IFC have been continuously engaged throughout the program. These collaborations have been critical to the successful implementation of FSKN and its dissemination to several economies outside the US.

Clearly, the FSKN initiative has engaged with and benefitted from this large number and variety of international partners. Each has been critical to the successful implementation of FSKN and dissemination of its content to beneficiaries in several economies.

Individual level

At the individual level, there has been are tremendous amount of networking among key individuals working for FSKN partner organizations. Although some of this networking and collaboration has occurred through events organized explicitly for FSKN development and implementation, a considerable amount of networking has occurred through other fora such as the Global Food Safety Initiative of the Consumer Goods Forum (http://www.mygfsi.com), the Partnership Training Institute Network of the Asia Pacific Economic Cooperation Forum (http://fscf-ptin.apec.org), and the World Bank-organized Global Food Safety Partnership (http://www.worldbank.org/en/topic/agriculture/brief/global-food-safety-partnership).

This networking has involved a relatively small, yet highly influential, group of individuals who collaborate on FSKN and similar globally-focused initiatives in the area of food safety standards and food safety management systems implementation. This core network interacts less directly with beneficiary groups such as farmers or SME food processors, who typically have been identified for participation in the programs by their buying companies (e.g. multinational food corporations) or donor organizations such as UNIDO or IFC. Content delivery in FSKNrelated projects has been conducted by a select group of highly-qualified experts working in academia (e.g. MSU), the food industry, or as consultants. In many cases, the same experts have been enlisted to implement training and capacity development programs by multiple food industry companies, associations or donor agencies. This highlights the need for engagement of more experts in networks such as FSKN, but also speaks to a relative dearth of recognized international experts in this specific discipline.

In France: the ISO 22000 club launched by CCI Picardie In spring 2007, the Chamber of Commerce and Industry (CCI) decided to launch, for ten regional food companies (including Paris Caramel) an informal 'ISO 22000 club', a regional program to support ISO 22000 standards. This ISO 22000 program has consisted of business leader coaching along with accompanying collective actions for all participating companies. The Paris Caramel's management decided to embark on the process of certification because of new customers' requirements and changes in the business environment. The certification was not an absolute necessity for this healthy company but appears as a possible supplementary marketing asset in accordance with the policy of sustainable customer satisfaction ensuring the safety of products sold. It would also eliminate the different and heterogeneous customers' specifications and create differentiation towards competitors. Ultimately, Paris Caramel attained ISO 22000 certification in October 2008.

Founded in 1957, Paris Caramel is a food SME located in the Picardie region in Northern France and manufactures chocolate and confectionery products. The company manufactures three main types of products of the highest quality: caramel, fruit pulp and chocolate, for a turnover of 900 000 Euros per year. Their customers are pastry confectioners, delicatessens and shops selling local products. The company has forty employees, mainly makers of caramels, fruit jellies and chocolate candies. In year 2000, the company decided to develop the certification of various stages of the production process, starting with HACCP. As a small family-owned company with mostly self-educated staff, Paris Caramel is very cost-efficient with a short decision process. Another important characteristic of the company is its human dimension: human capital is more important than financial returns, and the managers put more emphasis on training their employees and on maintaining employment than on profits.

Organizational level

Continuous ties such as spatial (the location in the Picardie region, the role of the Regional Council) and cultural ties have been acknowledged by the company as important features, as they provide trust and easy communication. The tacit knowledge dimension of the standard is also to be considered: for that type of knowledge, considered as soft information, organizational proximity is sufficient. For the responsible in charge of the implementation at Paris Caramel, the institutional embeddedness of the initiative, promoted both by AFNOR and by the Chamber of Commerce, has played a crucial function in providing seriousness and credibility. The congruence of goals between all the stakeholders of the initiative, creating a specific relationship and a sense of responsibility, provided an environment for mechanisms such as emulation and mimicry. Indeed these effects can be considered as learning effects as well, in reinforcing/auto-promoting the exchange of skills and information.

The learning by doing effects have been identified mainly between the consultancy firm and Paris Caramel: the role at that organizational level is significant at the initiation stage (establishment of a first contact and of a formal tripartite contract between the CCI, the consultancy firm and the company), but the main interaction effects have occurred at the individual level.

Organizations involved in the process of standard adoption are: AFNOR, CCI, consultancy firms, other SMEs.

-AFNOR, the French ISO affiliated organization, has a central role in the definition of ISO 22000 standards. But this role can be qualified as highly differentiated, according to the phase of innovation. In the initial phase of creation, AFNOR has a leading role, but it is interesting to note that Paris Caramel is not involved at all. In the phase of initiation, AFNOR has played a more contrasted role: thanks to its leadership and size, AFNOR always plays a central role in awareness of companies. But its actions are mainly oriented towards large companies. In the adoption phase AFNOR has no specific role. During the implementation phase, AFNOR provides its expertise and acts as a training entity both for companies and for consultants.

-The CCI (Chamber of Commerce and Industry) had no role in the definition phase. Its action is crucial in the adoption phase: the organization has acted as a pivotal organization between AFNOR, consultancy firms and SMEs, through the program funding and the set up of the tripartite contracts.

-Consultancy firms: Protechnic, a consulting firm had a central role in the adoption stricto sensu phase. It is difficult to separate its role as a company and as a person. Indeed the manager of the company has been largely convinced by the consultant to adopt the standard. But the company has also a very good experience and reputation at working with SMEs. The specific expertise is at the basis of the successful interaction process. -ISO 22000 club for SMEs: this club is the heir of another previous club devoted to HACCP. Its role has been to connect companies from different industries (thus not in competition) to exchange views and questions about the standard and its consequences. Its role is both formal (membership) and informal (interpersonal relations, cf. below).

-Third party certifier: the certification body Bureau Veritas has conducted the certification process and has been the main player, with Paris Caramel, during the conformity assessment phase.

Individual level

The inter-individual aspects of the network learning effects are more difficult to evaluate for confidentiality reasons. Nevertheless, there is a clear complementarity of the continuous ties between the two levels, leading to strong coupling effects. The managers from Paris Caramel (the CEO, the quality responsible) are part of a coherent community of leaders in the Picardie region and everybody knows each other quite well. This fact has played an important role in the decision to adopt. However, the individual level is also of tremendous importance for learning in terms of discrete ties and interactions (mainly with the consultant, but also with other food managers during the period of the CCI initiative as well as with some customers).

Informal contacts and exchanges may occur at any time and for confidentiality and privacy reasons interviewees are reluctant to answer. Nevertheless interpersonal contacts seem to play an important role especially with one consultant and with all the managers from the ISO 22000 group. According to the analytical framework, the learning effects are different from one phase to another. We will consider successively the five main phases, namely standard setting (antecedents), decision of adoption, implementation stricto sensu, conformity assesment (certification), and enforcement (post certification). During the standard setting phase, only limited network learning phenomena occurred, at the individual level, in the form of previous personal experiences of the quality manager of Paris Caramel in similar fields. Indeed, no formal contacts between the company and AFNOR has existed, showing that during its definition, the ISO 22000 standard does not include all potential users such food SMEs.

The adoption decision is reached thanks to contact between the company and CCI: the learning effect can be defined as the rise of awareness of the company leaders involved in the initiative in the development of the standard and soft information exchange for the establishment of the tripartite contract.

The implementation phase is obviously the period of time (almost 2 years) that has witnessed important learning phenomena. The most important learning phenomena has occurred at the interindividual level, in the form of a strong interaction between the quality manager and the consultant in charge of the program. The formal explicit knowledge included in the ISO standard specifications necessitates adaptations and translations in the real world of the Paris Caramel specificities. On the contrary, formal contacts between organizations are limited during this period of time. Another significant network learning effect is the permanent contact between the food managers involved in the initiative, in terms on comparisons, informal exchange and emulation.

The conformity assessment phase is more formal: this is the recognition of the compliance with specification, done through a certification audit. The process of learning is done through an exchange of explicit information (such as files, information control procedures etc.) between the company and the certifying body.

The enforcement phase is the post certification period of continous improvement. Learning effects occur mainly in-house, with the practical involvement of the employees. Nevertheless, the informal contacts established during the implementation phase with other managers remain active, in the form of informal meetings, cross auditing practices and informal exchanges.

3-Discussion and concluding comments

The objective of the communication is twofold: (i) to propose an original framework for the analysis of the implementation of internationally-recognized food safety management systems (e.g. ISO 22000, GFSIbenchmarked food safety schemes), in using a network effect perspective; (ii) to apply this framework to two case studies. The major motivation is the fact that the implementation of a FSMS is a long and complex process strongly related to its organizational and individual context. Quality management standards are immaterial in nature and difficult to implement: food SMEs and their managers will inevitably rely heavily upon collective initiatives.

From this analysis it is possible to summarize a few key features. At the preliminary stages of the implementation process, the learning effects do not extend outside the organizations. These effects occur more clearly during the implementation phase. The dynamic approach shows an interesting phenomena: in the latter phases of the implementation process (i.e. conformity and assessment phases), new types of partners emerge and their roles are of tremendous importance for the success of the ISO 22000 adoption. It suggests that the position/relationships of the individual companies vis à vis these partners during that period of time must be clearly emphasized as a key component of the success of the initiative.

Preliminary results, still to be confirmed and extended to other cases, could have interesting managerial implications for food SMEs. First of all, the collective (i.e. network) dimension of the process is shown. No food SMEs in these initiatives could have decided in isolation to set up FSMS. Instead, the food companies of the case studies are strongly embedded in a web of partners, defining a networking activity for innovation. Within this network, the process of learning is doubly collective: at the institutional level, where institutions (e.g., Chamber of Commerce and Industry, academic institutions), consultancy firms and associations (e.g. AFNOR, GFSI) have worked together to promote the initiatives; at a micro-analytic level, with the SMEs building strong relationships with service providers (e.g. consultancy firms, certification bodies) and, at the same time with a broader community of food business leaders having its own dynamics, objectives and social interaction mechanisms.

A second idea is that of resources. The critical success factor in FSMS implementation by SMEs in these case studies seems not to be financial resources, but rather access to cognitive resources, (i.e. the ability to connect and to be connected through a web of relationships to the relevant people and organizations). Learning phenomena appear to be complex, multifaceted and done through several mechanisms and mediation. Consequently, an important managerial implication of the research, to be validated by other situations, would be to enhance these cognitive resources and mechanisms, to identify more precisely their nature, the partners involved and their roles for learning in relation with the requirements of the different phases of implementation.