E H Elhafsi

N Mitton
email: mitton@lifl.fr

B Pavkovic

D Simplot-Ryl
email: simplot-ryl@lifl.fr

Energy-aware Georouting with Guaranteed Delivery in Wireless Sensor Networks with Obstacles

We propose, EtE, a novel end-to-end localized routing protocol for wireless sensor networks that is energy-efficient and guarantees delivery. To forward a packet, a node s in graph G computes the cost of the energy weighted shortest path between s and each of its neighbors in the forward direction towards the destination which minimizes the ratio of the cost of the shortest path to the progress (reduction in distance towards the destination). It then sends the message to the first node on the shortest path from s to x: say node x ′ . Node x ′ restarts the same greedy routing process until the destination is reached or an obstacle is encountered and the routing fails. To recover from the latter scenario, local minima trap, our algorithm invokes an energy-aware Face routing that guarantees delivery. Our work is the first to optimize energy consumption of Face routing. It works as follows. First, it builds a connected dominating set from graph G, second it computes its Gabriel graph to obtain the planar graph G ′ . Face routing is invoked and applied to G ′ only to determine which edges to follow in the recovery process. On each edge, greedy routing is applied. This two-phase (greedy-Face) End-to-End routing process (EtE) reiterates until the final destination is reached. Simulation results show that EtE outperforms several existing geographical routing on energy consumption metric and delivery rate. Moreover, we prove that the computed path length and the total energy of the path are constant factors of the optimal for dense networks.

Introduction

Routing in WSN is a very challenging task due to the inherent characteristics that differentiates these networks from other networks like mobile ad hoc net-1 works or traditional IP-based networks. In sensor networks, a large number of sensors are generally deployed and because almost all applications of sensor networks require the flow of sensed data from at least one source to a particular base station or sink. Moreover sensor nodes are constrained in terms of energy, storage and processing capabilities therefore they require careful resource management.

In this paper, we focus on designing routing protocols that are scalable, energy efficient and that guarantee delivery in general network topologies. Centralized solutions generally need global knowledge, including position and activity status of all network nodes, thus nodes need the dissemination of route discovery information and need to maintain routing tables. To avoid this communication overhead, we focus on localized algorithms where only local information such as the position of the current node holding a packet, the one of its neighbors and the one of the destination are required.

Several localized routing protocols [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF] with hop count as metric have been proposed to improve scalability. Each node has position information by using geographic positioning system (GPS) or other localization means [START_REF] Elhafsi | Cost over progress based energy efficient routing over virtual coordinates in wireless sensor networks[END_REF] and routing decisions are made at each node using only local neighborhood information. Within this framework, energy-aware routing schemes use power consumption as metric and have been proposed in [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF][START_REF] Elhafsi | Flattening the gap between sourcedestination paths in energy efficient greedy georouting in wireless sensor 5[END_REF][START_REF] Stojmenovic | Power and cost aware localized routing with guaranteed delivery in wireless networks[END_REF][START_REF] Simplot-Ryl | Energy efficient backbone construction, broadcasting, and area coverage in sensor networks[END_REF][START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF][START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF].

Guaranteed delivery is another routing concern in sensor networks. Most routing schemes do not guarantee delivery especially in networks where obstacles such as holes and buildings are present. Several recovery schemes have been proposed [START_REF] Frey | On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[END_REF] to overcome such a drawback.

Localized power aware routing algorithms that also guarantee delivery were proposed in [START_REF] Stojmenovic | Power and cost aware localized routing with guaranteed delivery in wireless networks[END_REF][START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF][START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF].

In this work, we propose an end-to-end geographic path discovery protocol (EtE). To the best of our knowledge, it is the first position-based algorithm which at the same time guarantees packet delivery and reduces the energy consumption of both greedy and recovery parts. It satisfies the above objectives and more. It has the following characteristics:

• Localized: In EtE, to make a routing decision, a node has to be aware only of its location, of its neighbors and of the final destination.

• Scalable: EtE is memoryless as no routing information need to be stored at the node leading to a scalable protocol where no information is embedded in the message.

• Loop free: EtE is loop-free since the greedy step always chooses among its neighbors in the forwarding direction of the destination (nodes closer to the destination than itself). This makes any sender node s on the path forward to a node closer to the destination than the sender node.

• Guarantees delivery: EtE has two routing phases. The first phase is a localized greedy protocol that is prone to routing failure. EtE guarantees delivery by invoking its second phase-Face routing when needed.

• Energy efficient: Our simulations show that every routing step EtE takes is energy aware. To avoid expensive long edges, EtE computes an energy weighted localized shortest path (SP) from the relaying node to all its neighbors in the forward direction and selects the one that minimizes the cost of the SP to the progress towards the destination. To avoid expensive short edges, EtE runs Face routing over a connected dominating set (CDS) on which it computes a SP once again.

We prove that the total Euclidean length of the path found in greedy phase is within a constant factor of the optimum. For dense uniform networks, we also prove that the total energy of a computed path is constant factor of the optimal.

This paper is organized as follows. We introduce the network model and state our assumptions in Section 2. Then we briefly cover related work in Section 3. In Section 4, we introduce our protocol EtE. We compare EtE performance to existing protocols in Section 5 and conclude in Section 6.

Preliminaries

Network Model

While the network model can be arbitrary, the simulations are based on the widely adopted unit disk graph (UDG) model [START_REF] Clark | Unit disk graphs[END_REF]. UDG is defined by G = (V, E), where V represents the set of sensor nodes in the network and there is an edge e = (u, v) ∈ E between nodes u and v if and only if the Euclidean distance between them |uv| ≤ R, where R is the transmission radius, equal for all nodes. Let N (u) be the set of neighbors of node u. Let N x (u) be the set of nodes from N (u) which are closer to x that is:

N x (u) = N(u) ∩ {{v} s.t. |xv| < |xu|} .
We define the density of the network as the average number of neighbors per node, also called the degree of a node noted δ: δ(u) = |N x (u)|. We assume that each node is aware of its position and the one of its neighbors. This may be achieved through the use of a positioning device such as GPS1 or Galileo2 . We assume that every node is aware of the position of the destination. This can be achieved thanks to the use of a location system such as in [START_REF] Li | A scalable location service for geographic ad hoc routing[END_REF][START_REF] Stojmenovic | Location updates for efficient routing in ad hoc networks[END_REF].

Energy Model

The most common energy model is proposed in [START_REF] Rodoplu | Minimizing energy mobile wireless networks[END_REF].

power = r α + c if r = 0, 0 otherwise. ( 1
)
where r is the distance separating two neighboring nodes (a forwarding and a receiving node); c is the overhead due to signal processing; α is a real constant (≥ 2) that represents the signal attenuation. This energy model implies that following only short edges may be as expensive as following long edges because of c. Note that, in reality, this needs to be multiplied with a constant that includes, for example, the message length. The optimal transmission radius, r * , that minimizes the total power consumption for a routing task is equal to: r * = α c α-1 . We thus assume that nodes can adjust their range. The range adjustment may be performed by the link layer. 33 Literature review

Routing

We briefly describe position based routing schemes relevant to this work. We distinguish between two routing metrics: hop count and power consumption.

Hop count based routing

In the greedy method [START_REF] Finn | Routing and addressing problems in large metropolitan-scale[END_REF], a node holding a packet forwards it to its neighbor a that is closest to the destination. Though this greedy routing works well in dense networks, it fails if a node a is closer to the destination than any of its neighbors. A routing algorithm that guarantees delivery in 2-D UDG is described in [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF]. It applies greedy routing until either the message is delivered or the routing fails. In the latter case, Face routing is applied to recover from failure. Face routing requires the network topology to be a planar graph (i.e., no edges intersect each other). To planarize a graph, several algorithms can be used [START_REF] Li | Hybrid greedy/Face routing for ad-hoc sensor network[END_REF][START_REF] Toussaint | The relative neighborhood graph of a finite planar set[END_REF]. Gabriel Graph (GG), for instance, contains edges between nodes u and v if and only if no other nodes are located inside the circle centered in the middle of edge (u, v) and with diameter |uv|. GG has some desirable properties when used for routing in wireless networks such as localized message, free computation, planarity, and preserving connectivity [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF]. GG divides the network into faces. The face that contains the line (sd), where s is the failure node, and d is the destination node, is traversed by right-hand or left-hand rule (placing a virtual hand on the wall of the face) until a node a closer to destination than s is encountered. It has been shown in [START_REF] Frey | On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[END_REF] that Face routing guarantees recovery traversing the first face. Greedy routing continues from a until delivery or another failure node is encountered.

Power consumption based routing

Cost over Progress based routing [START_REF] Stojmenovic | Localized network layer protocols in sensor networks based on optimizing cost over progress ratio[END_REF][START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF] is a localized metric aware greedy routing scheme. A node forwards a packet to the neighbor closer to d such that the ratio of the energy consumed (any cost metric can be applied) to the progress made (measured as the reduction in distance to d) is minimized. Though energy efficient, this algorithm does not guarantee delivery.

The first power aware localized routing algorithms were described in [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF]. Cost-over-progress framework with power as the cost has been applied in [START_REF] Kuruvila | Progress and location based localized power aware routing for ah hoc sensor wireless networks[END_REF]. It was applied only in greedy phase and had similar performance to previous methods while enjoying simplicity in the design.The Iterative Power Progress algorithm, proposed in [START_REF] Kuruvila | Progress and location based localized power aware routing for ah hoc sensor wireless networks[END_REF], is an improvement of the basic Power over Progress algorithm described in [START_REF] Kuruvila | Progress and location based localized power aware routing for ah hoc sensor wireless networks[END_REF] as well. It works as follows. As in Power Progress, a node s,currently holding a message destined to d, first finds a neighbor a that minimizes power(r)/(|ds| -|da|). Then, the search continues for an intermediate node b which is: closer to d than s, is neighbor to both s and a, satisfies power(|sb|) + power(|ba|) < power(|sa|) and has the minimum power(|sb|) + power(|ba|) measure. If found, such node b replaces a as selected neighbor, and the search for a better intermediate node repeats. This process is iteratively repeated until no improvement is possible and node s forwards the message to the selected neighbor, which then applies the same scheme for its own forwarding. The first article to address guaranteed delivery in power aware localized routing is [START_REF] Stojmenovic | Power and cost aware localized routing with guaranteed delivery in wireless networks[END_REF]. It is a Greedy-Face-Greedy (GFG) approach where greedy routing is the same as in [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF] while Face routing is similar to the one in [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF]. One of the drawbacks of Face routing is that it is likely to follow short edges of GG that may be power inefficient.

GOAFR+ [START_REF]Geometric ad-hoc routing: Of theory and practice[END_REF] (Greedy Other Adaptive Face Routing Plus) is a combination of greedy routing and face routing. GOAFR+ presents two mechanisms of early fallback and boundary circle. Early fallback mechanism is to return from face routing mode to greedy forwarding mode as soon as possible. And the boundary circle is used to restrict a searching area in similar way as OAFR (Other Adaptive Face Routing) [START_REF] Simplot-Ryl | Energy efficient backbone construction, broadcasting, and area coverage in sensor networks[END_REF]. It reduces exploring a boundary of faces far away from the destination. These two mechanisms make GOAFR+ achieve optimal result in the worst-case. Then, some variants have been proposed to improve to find adapt circles boundary circles by using the location information of neighbors [START_REF]GOAFR plus-ABC: Geographic routing based on adaptive boundary circle in manets[END_REF].

In [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF], a GFG energy aware routing with guaranteed delivery has been proposed. The energy awareness is introduced at the greedy phase where the path to the selected neighbor is enhanced by following the energy weighted SP (with power consumption as weights). The algorithm works as follows. Node s currently holding a packet selects neighbor a closest to d as its temporary destination node. Instead of transmitting directly to a, s computes the energy weighted SP to a. This path is followed until a node b closer to d than s is reached. To reach node b, the SP has to be embedded in the message, creating more overhead and making the protocol less energy efficient. Node b then recursively applies the same protocol. Face routing [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF] is applied to recover from failure points. In this work, we will refer to this protocol as SPFSP.

In LEARN [START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF], a localized energy aware routing is proposed. A node s selects neighbor b inside a restricted neighborhood ( bsd ≤ α for a parameter α < π/3) that has the largest energy mileage, determined as the ratio |sb|/power(|sb|). If no such neighbor exists inside the restricted neighborhood, LEARN fails. In the variant LEARN-G, a node switches to greedy routing [START_REF] Finn | Routing and addressing problems in large metropolitan-scale[END_REF] in case of failure and selects the neighbor closest to the destination. Finally, in the variant LEARN-GFG, a node invokes Face routing when a failure occurs.

Clearly, all existing algorithms use an energy unaware Face routing as a recovery routing scheme. To the best of our knowledge, this is the first work to combine Face routing with a power consumption metric.

Connected dominating sets

Dominating sets are defined as follows. Each node in a graph either belongs to a dominating set (DS) or has a neighbor in the DS. The problem of computing the smallest CDS is known to be NP-complete even if knowledge of the global topology is available. Dai and Wu [START_REF] Dai | An extended localized algorithm for connected dominating set formation in ad hoc wireless networks[END_REF] introduced a generalized DS concept, where coverage can be provided by an arbitrary number of connected one-hop neighbors. The definition was modified by [START_REF] Simplot-Ryl | Energy efficient backbone construction, broadcasting, and area coverage in sensor networks[END_REF], to avoid message exchanges between neighbors, to the following form. Node a is covered by its one-hop neighbors b, c, . . . if these neighbors b, c, . . . are connected (any neighbor of a is a neighbor of at least one node among b, c, . . . and key(a) < min(key(b), key(c), . . .)). It is then further simplified in [START_REF] Carle | Energy efficient area monitoring by sensor networks[END_REF] as follows. First, each node checks if it is an intermediate node. Then each intermediate node a constructs a subgraph G ′ of its neighbors with higher key values. If G ′ is empty or disconnected then a is in the DS. If G ′ is connected but there exists a neighbor of a which is not a neighbor of any node of G ′ then a is in the CDS. If position information of 1-hop neighbors is available, nodes can decide whether or not they belong to a so defined CDS without exchanging any message with their neighbors. Note that these algorithms are local and do not induce any additional message overhead.

Motivation

In this paper, we aim at proposing a novel position-based algorithm which guarantees the packet delivery by reducing the energy consumption in both greedy and recovery steps.

New Routing Approach -EtE Algorithm

We describe a novel energy efficient georouting EtE with guaranteed delivery. It is based on a GFG routing in which both steps (greedy and Face) are energy aware. 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000

Greedy Routing

The greedy step of EtE is based on the SP computation as in [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF] but with important differences: first, in the choice of the temporary destination and second, in the computation of the SP. In [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF], to send a message, a node s first selects its neighbor node in its neighborhood which is the closest to the destination (node b in Figure 1). Then it computes the SP between itself and the selected node. When node s computes the energy weighted shortest path towards b, it considers all the nodes in its neighborhood (including nodes in backward direction c, e and nodes in forward direction b, f, j, k in Figure 1). In this example, the SP found goes through node c which is not neighbor of the destination node b and thus would not be able to compute the SP from itself to b. Therefore, the SP needs to be embedded in the message for the latter to reach node b and avoid loops. In [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF] the SP forwarding from s to selected neighbor b is truncated at node f , first node in the SP closer to d than s.

In EtE, and contrarily to [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF], the SP is computed only over nodes in the neighborhood of s in forward direction (nodes closer to d than to s). In Figure 1, s considers only nodes in the grey shaded and striped area: nodes b, f , j and k. Since each node on the SP that receives the message locally computes the next hop, EtE does not need to embed the SP in the message as in [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF]. The message contains only the addresses of the source, destination and next hop selected neighbor of s. Since every node considers only nodes in the forwarding direction, there is no loop possible. As we show in our simulations, this is a major advantage of EtE over the method in [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF] especially when the SP is long. Moreover, since at each step we get closer to the destination, it is clear that EtE is loop-free.

Let F(s, d) be a function that defines the selection criteria of s's neighbor b on the path to d. Node s selects node b which minimizes F(s, d). Our greedy routing step differs from the one in [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF] in the choice of F. In [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF], node s selects its neighbor b which is closest to the the destination d, i.e. F(s, d) = min u∈N d (s) |ud| which is satisfied for |bd| = F(s, d).

To be more energy efficient, we propose to select this node in a cost-over progress fashion [START_REF] Kuruvila | Progress and location based localized power aware routing for ah hoc sensor wireless networks[END_REF] where we define our cost as the SP cost. Let ||sd|-|ud|| . In Figure 1, the neighbor that would be selected by the algorithm proposed in [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF] is b while EtE would select node k. Note that in the given example, the SP from a to k is that link itself, which may happen frequently because of cost-over-progress optimality criteria for selecting neighbors. In other examples, intermediate nodes may be used on the SP to reduce the overall energy. In such a case, node s will send the message to the first node a on the SP towards the selected node b, and a will apply the same procedure which is formally described in Algorithm 1.

x 0 -x 1 -... - x i -x i+1 -..x n ,
Algorithm 1 Localized Greedy Algorithm EtE Greedy (s, d) x ← s ok ← 1, min ← ∞ while x = d and ok = 1 do V ← N (x) {v s.t.|vd| < |sd|} if V = ∅ then ok ← 0 else for each node y ∈ V do C ← costSP (x,

Recovery Step Routing

Regular Face routing guarantees delivery, but is not energy efficient since it may use very long as well as very short edges compared to the energy optimal transmission length r * . To overcome this drawback, we introduce in this work an energy efficient variant to Face routing. From the original graph G = (V, E) (Figure 2(a)) we compute a CDS, V ′ of V . Since source s and destination d may not be in the CDS, we expand V ′ by adding them to this set. Let G ′ = (V ′ , E ′ ) ⊂ G where V ′ ⊂ V is the expanded set of dominant nodes and E ′ ⊂ E is the set of edges between nodes in V ′ . We use the CDS election protocol introduced in [START_REF] Carle | Energy efficient area monitoring by sensor networks[END_REF], however other election protocol may be applied. Since Face routing must be applied on a planarized graph, we generate the GG, G ′′ = (V ′ , E ′′ ), from G ′ where E ′′ ⊂ E ′ is the set of edges remaining in the planarized graph (Figure 2(c)). Note that the computation of a GG is totally local. We then run Face routing over G ′′ . Face routing guarantees delivery in the constructed subset since it contains source and destination nodes and preserves connectivity. Moreover, by considering only edges connecting two dominating nodes, the routing process avoids to choose too short edges. Each node needs to know its neighbors that are in the CDS. This may come from 2-hop position knowledge, or by adding a bit in any message sent by nodes to their neighbors. However, the former approach will increase the communication overhead significantly, and such strong assumptions are not used in competing algorithms. The later approach will have minor impact on the overall overhead, and can function with 1-hop positional knowledge. Alternatively, one can rely on beaconless routing that guarantees delivery [START_REF] Kalosha | Select and protest based beaconless georouting with guaranteed delivery in wireless sensor networks[END_REF]. We will not elaborate on the details of the protocol. In brief, current node s that is in recovery mode will send a request to its neighbors to continue face traversals. Only neighbors that belong to the constructed CDS may respond. In the simple solution, all neighbors respond to allow s to select the proper edge in GG of dominant nodes. Such messages use short packets that consume negligible energy compared to messages needed to transmit a full message that is being relayed, therefore they are ignored in our analysis. Solutions with reduced number of responses are described in [START_REF] Kalosha | Select and protest based beaconless georouting with guaranteed delivery in wireless sensor networks[END_REF][START_REF] Chawla | Beaconless position-based routing with guaranteed delivery for wireless ad hoc and sensor networks[END_REF]. Application of Face routing on G ′′ only decides on which edge (s, b) to follow to reach the destination node from a given node s. However, that edge does not need to be selected since it may be too long (|sb| > r * ). Therefore, we apply once again an energy weighted SP to reach node b. It is the greedy algorithm described in Algorithm 1, where final destination node d is replaced by temporary destination b. That is, EtE Greedy (s, b) is invoked. Once node b is reached, we follow the EtE routing heuristic. If b is closer to the destination node than the node which has initiated Face routing step, node b selects the next hop in the routing path following the greedy routing described above. Otherwise, it determines the node following Face routing over CDS nodes and computes the energy based shortest path to reach it. This process reiterates until the destination is reached. This procedure is formally described in Algorithm 2.

Algorithm 2 Routing Protocol Algorithm EtE(G, s, d) G ′ ← DS(G) ∪ {s, d} G ′′ ← GG(G ′ ) ok = 1 {flag for greedy phase; ok = 0 for recovery phase} u ← s while u = d do [u, ok] ← ET E Greedy(u,d) if ok = 0 then u ′ ← u end if while ok = 0 do {Greedy routing failed on node u. Face Routing is invoked.} v ← FACE(u ′ , d) {v is the next node on the proper face} [u ′ , success] ← EtE Greedy (u ′ , v) {v is reached via an SP. Note that u ′ = v at exit.} if |u ′ d| < |ud| then ok = 1; u ← u ′ end if end while end while
Figure 3 illustrates a sample execution of EtE algorithm. Greedy routing proceeds from node 1 which first computes the cost of SP towards nodes 2, 19 and 21 (node 23 is not included in the selection since it is further from the destination than node 1). Node 1 selects node 19 as temporary destination since it provides the lowest cost over progress and sends the packet to node 21, the first node on the SP towards 19. Node 21 finds node 20 as its best forwarder and in this case SP is that link. Node 20 selects node 18 by following a SP through node 16 to which it sends the message. The latter then forwards to node 18 where greedy routing fails. Face routing is then invoked to follow edges 18-16 (directly), 16-15 and 15-11 (which are replaced by paths 16-14-15 and 15-13-11 respectively for energy efficiency). Greedy routing then continues till delivery to 11 selecting 10 via 9, 9 selecting 7 via 10, and 10 selecting destination 8 and delivering via node 7.

We now prove more properties of EtE algorithm. Definition 1 A path meets angular constraints if every hop is within an angle θ ≤ α < π 3 toward the destination node.

Theorem 1 Any path from source node s to destination node d that meets angular constraint has length that is constant length of the optimum |sd|.

Proof 1 The proof is the same as in [START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF] where it was restricted specifically to the protocol LEARN. Since that proof does not include any cost function, and is based solely on geometric arguments, it is generally valid for a family of protocols respecting the angular constraint.

Theorem 2 When EtE routing finds a path from source s to destination d in dense graphs, the total energy consumption of the path is within a constant factor of the optimum.

Proof 2 For any intermediate node s with packet to forward, EtE routing protocol selects the neighbor u such that powers,u |sd|-|du| is minimized. In [START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF], the neighbor v is selected such that Therefore EtE consumes less energy than LEARN. Since LEARN was proven in [START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF] to require constant factor of the optimum power for sufficiently dense networks, the theorem follows. Note that the argument is in fact probabilistic with details given in [START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF].

Performance Evaluation

We compare several protocols via simulation. We use WSNet/Worldsens [START_REF] Fraboulet | Worldsens: Development and prototyping tools for application specific wireless sensors networks[END_REF] event-driven simulator for large scale wireless sensor networks, that assumes 802.11 DCF MAC layer, free space propagation model and packet collisions. For the purpose of the simulation we have created 20 different networks which can be described as follows. Nodes are randomly deployed in a 1000 × 1000 square using a Poisson Point Process (node positions are independent) with different mean node degree δ4 . These nodes have the same maximum transmission range, R = 200 but can adapt their transmission range between 0 and R. We compare the performance of EtE to existing geographic routings GFG [START_REF] Frey | On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[END_REF], SPFSP [START_REF] Sanchez | Exploiting local knowledge to enhance energy-efficient geographic routing[END_REF] and LEARN-G [START_REF] Wang | Learn: Localized energy aware restricted neighborhood routing for ad hoc networks[END_REF]. We run the simulator for the same samples of node distribution, same source node and destination node, both randomly chosen. For every of 20 different network topologies we run around 150 depending on network size. We evaluate the energy consumption of each algorithm based on the energy model described in Section 2. As in [START_REF] Rodoplu | Minimizing energy mobile wireless networks[END_REF], we use c = 3•10 7 and α = 4, which leads to an optimal routing edge length of 100 [START_REF] Kuruvila | Progress and location based localized power aware routing for ah hoc sensor wireless networks[END_REF]. The results obtained are within a 95% -confidence interval. To further evaluate the routing protocols, we computed their energy overhead using as reference the optimal centralized energy weighted SP (Dijkstra algorithm [START_REF] Dijkstra | Solution of a problem in concurrent programming control[END_REF]). We let e i and e * be the energy consumed to route a packet from s to d using any one of the described protocol that guarantees delivery and the centralized SP protocol, respectively. We define the energy overhead as the ratio ei-e * e * . Since one of the novelty of EtE is the use of a CDS, we compare it to its variant EtE' that uses the basic Face phase as in SPFSP. We evaluate the performance of each phase of the protocols independently for better insights on the behavior of the routing schemes. Finally, to insure that Face routing is invoked, we evaluate the performance of the routing schemes on a homogeneous network (no holes and no obstacles) and on a topology with a crescent hole (see Fig. 2(a)).

Routing paths power consumption

Figs. 4 and5 show that our algorithms EtE and EtE' outperform existing solutions. They consume only 4% more energy than the optimal centralized algorithm in a homogeneous environment (Fig. 4) and only 12% more energy in a topology with a hole (Fig. 4). The next best performing algorithm is LEARN-G followed by SPFSP. The worse results are achieved by GFG which consumes 55% more energy than the optimal solution. Since EtE and EtE' perform the same greedy algorithm, EtE outperforms EtE' only when Face routing is usedin networks with low density and/or with obstacles. In dense networks greedy routing almost always succeeds (see Section 5.2).

Greedy routing performance evaluation

Our simulations show that greedy routing achieves almost 100% success rate in a homogeneous network when the density is higher than 15. For the topologies with a hole the success rate is slightly below 100% for mean node degree lower than 30. Figs. 6 and 7 plot the energy overhead for both topologies (with and without a hole). The overhead is computed only for successful routings. Our simulations show that our proposed greedy routing algorithm outperforms existing solutions. Moreover, privileging nodes within an angular sector toward the destination and favoring the one with the better energy to distance ratio as in LEARN is more efficient than computing a SP toward the node that minimizes the remaining distance to the destination. GFG is the solution which offers the worst performing greedy algorithm, followed by SPFSP and LEARN.

Face routing performance evaluation

We evaluate four variants of Face routing algorithm independently of the greedy phase: (1) Face used by GFG, run on a GG issued from the entire set of nodes in the network; (2) SPFACE, used by EtE' and SPFSP which selects the next node using Face and reaches it by performing an energy weighted SP; (3) DSFACE, used by LEARN-G, run over a GG issued from the CDS; and (4) SPDSFACE, used by EtE, which selects the next node using DSFACE and reaches it by performing an energy weighted SP. Our results are given in Fig. 8. It is interesting to notice that by using a CDS, we achieve better energy saving. This can be explained by the fact that when extracting a GG from the entire set of nodes in the network, we keep only short edges, often smaller than the optimal hop length. So, there is no need to perform an energy weighted SP. When extracting a GG from a CDS, we keep edges which may easily be longer or equal to the optimal hop length. In this case, performing an energy weighted SP is of interest. Fig. 10 plots face edges average length for the different GGs and the length of the edges followed by the various Face routing algorithms. We notice that SPFACE and Face obtain exactly the same results. It is interesting to note that introducing a CDS before planarizing the graph allows the computation of more energy efficient routes for any node density and range values. However, edge length of the planarized graph depends on the maximum radius R (see Fig. 9). Clearly, for a node density of 10, R < 150 and using a CDS, Fig. 9 shows that face edges are smaller than R opt . Therefore, there is no need to use the SP on Face routing. Fig. 10 shows that face edges length in the GG extracted from the DS are independent of δ. However, this is not true for the GG issued from the entire network. The figure supports our previous claim. It plots, for a given δ, the range of R values for which it is worth using a CDS. Moreover, Fig. 11 shows that energy savings are achieved for values of face edges length lower than R opt . The plot is for δ = 30, but the same results are obtained for various values of δ.

Enlarging the network

So far, we evaluated and compared several routing algorithms on a fixed network size while varying the network density. In this section, we focus on studying the effect of the network size on the performance of the various protocols. We fix Clearly, as the network size increases, so does the computed path length. For homogeneous networks, we notice that the energy overhead consumed by each protocol is pretty constant which makes it independent of the network size. This can be explained by the fact that for dense networks, greedy routing almost always succeeds and Face routing is rarely invoked. On the other hand, we notice that for network topology with obstacles, the energy overhead tends to slightly increase as the network size increases. This is due to the fact that the larger the network (and the longer the paths), the higher the chances for greedy routing to encounter a dead end and invoke Face routing. Moreover, Face routing has an energy overhead higher than greedy routing energy overhead (see Sections 5.2 and 5.3).

We also compared GOAFR+ performance to EtE via simulation. Our results confirm that EtE outperforms GOAFR+. The latter applies standard greedy phase and a variation of FACE recovery phase and makes use of several parameters which impact its performances. For instance, the parameter σ affects directly the behavior of the recovery phase. In fact for small values of σ-e.g. 1/3 as recommended by the authors-, the recovery phase is very similar to the original FACE. GOAFR+ is efficient when the considered network has big holes. However, our simulation results, with a value of σ = 1/100 (like used by the authors in their simulations), show that EtE is 28% more energy efficient than GOAFR+ for sparse networks (10 nodes per communication area). For dense networks, the energy consumption of GOAFR+ is similar to GFG presented in previously.

Conclusion

We propose a novel routing protocol, EtE, that is both energy efficient and guarantees delivery. EtE is general enough to be efficiently deployed in a network with arbitrary topology (networks with obstacles and holes). It is a two-phase routing protocol that uses an energy optimized greedy routing followed by an energy efficient Face routing scheme when a local minima is encountered. To the best of our knowledge, EtE is the first and only algorithm that uses an energy efficient Face routing. It is achieved by the integration of the dominating set to optimize the paths edge length used in the routing process. Based on our intensive simulations, EtE outperforms various energy-aware routing schemes. EtE considers a well-used energy cost model but it is worth noting that this cost computation can be replaced by any metric cost that one wishes to optimize. For instance, the cost of a link may be the delay introduced by using that link. Yet, EtE is also a general algorithm that can be used to enhance any metric.

Next steps of this work will be the analysis of the energy cost for maintaining the Face graph.

Figure 1 :

 1 Figure 1: Greedy routing from node s to d. In [8] s selects b and the truncated SP is scef . EtE algorithm follows a path via node k.

  be the nodes on the SP from s to b with x 0 = s and x n = b. We define the cost cost SP (s, b) of the SP from s to b as cost SP (s, b) = n-1 i=0 power(|x i x i+1 |). Node s then selects node b which minimizes the cost of the SP from s to b divided by the progress it makes towards destination node d. F(s, d) is then expressed as F(s, d) = min u∈N d (s) costSP (s,u)

  G ′′ = GG from G ′

Figure 2 :

 2 Figure 2: When using regular Face routing over Graph G (a), messages follow GG edges of G (b). Edges of G" (c) are used instead when applying our energyefficient Face routing.

Figure 3 :

 3 Figure 3: Illustrative example of EtE algorithm on a sample network.

  powers,v |sv| is minimized.Comparing the cost to progress provided by both choices it then follows that powers,u |sd|-|du| ≤ powers,v |sd|-|dv| . The expected number of hops by both algorithms are |sd| |sd|-|du| and |sd| |sd|-|dv| respectively. The expected energy consumption of the respective paths are then equal to {power s,u • |sd| |sd|-|du| } and {power s,v • |sd| |sd|-|dv| } which is equivalent to multiplying both sides of the above inequality by |sd|. Thus we get {power s,u • |sd| |sd|-|du| } ≤ {power s,v • |sd| |sd|-|dv| }.

Figure 4 :

 4 Figure 4: Energy consumption in a homogeneous network.

Figure 5 :

 5 Figure 5: Energy consumption in a topology with obstacles.

Figure 6 :

 6 Figure 6: Greedy energy consumption in a homogeneous network.

Figure 7 :

 7 Figure 7: Greedy energy consumption in a network with obstacles.

Figure 8 :

 8 Figure 8: Face routing features of the different routing protocols.

Figure 9 :

 9 Figure 9: Relationship between face edges length and R for the GGs, when δ = 10 and 30.

Figure 10 :

 10 Figure 10: Edges length for face in both GGs and for the routing paths.

Figure 11 :

 11 Figure 11: Energy consumption as a function of R.

Figure 12 :

 12 Figure 12: Energy consumption overhead in a homogeneous network when R max = 200 and δ = 15. The x-axis represents the network size multiplicative factor.

Figure 13 :

 13 Figure 13: Energy consumption in a network with obstacles when R max = 200 and δ = 15. The x-axis represents the network size multiplicative factor.

http://www.gps.gov/index.html

http://ec.europa.eu/transport/galileo/index en.htm

The link layer may raise to the network layer the information which is necessary for the computation of the cost for each neighbor. Basically, the transmission power is sufficient to perform this cost. The evaluation of the required transmission power to reach a given neighbor is the difficult part of this task. Based on RSSI (received signal strength indicator) and LQI (link quality indicator) it is possible to perform this as shown in recent works[START_REF] Khadar | From theory to practice: topology control in wireless sensor networks[END_REF].

In such a Poisson Point Process, the total number of nodes is probabilistic and is obtained from a Poisson Law of intensity λ with λ = δ πR 2 .

Acknowledgments

This research was partially supported by NSERC Canada, a grant from CPER Nord-Pas-de-Calais/FEDER TAC COMDOM, from an INRIA ARC program CARMA and from the French National Research Agency RNRT SVP (Supervise and Protect) 5 .


Une note sur l'utilisation des attaques par rejeu pour compromettre la confidentialité dans les protocoles de vote électronique

Résumé : Dans un résultat précédent, nous avons montré que le protocole de vote électronique Helios 2.0 ne garantissait pas l'indépendance des votes et que cela pouvait être utilisé pour compromettre la confidentialité des votes. Cette attaque repose en particulier sur le fait que le protocole Helios est vulnérable aux attaques par rejeu. Dans cette note, nous examinons le cas de deux autres protocoles de vote de la littérature -les protocoles Sako & Kilian et Schoenmakers -qui sont connus pour ne pas garantir l'indépendance des votes. Nous montrons comment cette vulnérabilité peut être à nouveau exploitée pour compromettre la confidentialité.

Mots-clés : vote électronique, indépendance des bulletins, confidentialité des votes, attaque par rejeu

Introduction

Paper-based elections derive ballot independence from physical characteristics of the real-world, for example, ballots are constructed in isolation inside polling booths and complete ballots are deposited into locked ballot boxes. By comparison, in a digital setting, ballots are sent using publicly readable communications channels and, in end-to-end verifiable elections, stored on a publicly readable bulletin board. Nevertheless, the provision of ballot independence is important to ensure privacy, as demonstrated in our earlier work [START_REF] Smyth | Attacking and fixing helios: An analysis of ballot secrecy[END_REF][START_REF] Cortier | Attacking and fixing Helios: An analysis of ballot secrecy[END_REF] who exploit the lack of ballot independence in Helios 2.0 [START_REF] Adida | Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios[END_REF] to violate ballot secrecy.

Informally, ballot independence is characterised by Gennaro [Gen95, ➜1.1] as follows.

Ballot independence. Observing another voter's interaction with the election system does not allow a voter to cast a related vote.

In addition to the apparent relationship between ballot independence and privacy, ballot independence is important because it prohibits the voting system from influencing a voter's behaviour; more formally, this requires that observation of the voting system (that is, observing interaction between participants) does not leak information that may affect a voter's vote. The concept of privacy for electronic voting systems has been informally defined by the following properties [KR05, BHM08, DKR09]. Ballot secrecy. A voter's vote is not revealed to anyone.

Receipt freeness. A voter cannot gain information which can be used to prove, to a coercer, how she voted.

Coercion resistance. A voter cannot collaborate, with a coercer, to gain information which can be used to prove how she voted.

Other desirable properties of electronic voting systems include verifiability [JCJ02, Par07, KRS10].

Individual verifiability. A voter can check that her own ballot is published

on the election's bulletin board.

Universal verifiability. Anyone can check that all the votes in the election outcome correspond to ballots published on the election's bulletin board.

Eligibility verifiability. Anyone can check that each ballot published on the bulletin board was cast by a registered voter and at most one ballot is tallied per voter.

The verifiability properties (also called end-to-end verifiability [JCJ02, CRS05, Adi06]) allow voters and election observers to verify -independently of the hardware and software running the election -that votes have been recorded, tallied and declared correctly.

We [START_REF] Smyth | Attacking and fixing helios: An analysis of ballot secrecy[END_REF][START_REF] Cortier | Attacking and fixing Helios: An analysis of ballot secrecy[END_REF] have shown in Helios 2.0 it is possible to replay a voter's ballot (without knowing the vote contained within that ballot). This immediately violates ballot secrecy in an election with three voters. For example, consider the electorate Alice, Bob, and Mallory; if Mallory replays Alice's ballot, then Mallory can reveal Alice's vote by observing the election outcome and checking which candidate obtained at least two votes.

Contribution. We take two schemes presented at CRYPTO -namely, the protocols due to Sako & Kilian [START_REF] Sako | Secure Voting Using Partially Compatible Homomorphisms[END_REF] and Schoenmakers [START_REF] Schoenmakers | A simple publicly verifiable secret sharing scheme and its application to electronic voting[END_REF] -that are known not to satisfy ballot independence and show that these protocols are both vulnerable to replay attacks that violate privacy.

The study of Sako & Kilian [START_REF] Sako | Secure Voting Using Partially Compatible Homomorphisms[END_REF] is interesting because it was one of the first electronic voting protocols to adopt the Fiat-Shamir heuristic to derive non-interactive proofs (this evolution was key for the development of end-toend verifiable electronic voting systems). However, we will show that the application of the Fiat-Shamir heuristic compromises ballot secrecy. In particular, the interactive nature of zero-knowledge proofs guarantees ballot independence; whereas, non-interactive proofs, derived using the Fiat-Shamir heuristic, do not assure independence. This can be exploited by a replay attack to violate ballot secrecy.

In earlier work [START_REF] Smyth | Attacking and fixing helios: An analysis of ballot secrecy[END_REF][START_REF] Cortier | Attacking and fixing Helios: An analysis of ballot secrecy[END_REF], we acknowledge that our attack against Helios may not be practical in large-scale elections, but it is particularly well suited to small-scale elections. The scheme by Schoenmakers [START_REF] Schoenmakers | A simple publicly verifiable secret sharing scheme and its application to electronic voting[END_REF] was explicitly designed for small-scale elections (for example, boardroom elections) and, hence, we find it interesting to study the possibility of violating ballot secrecy in this setting. Once again, we violate privacy using a replay attack.

Related work. The concept of independence was introduced by Chor et al.

[CGMA85] and the possibility of compromising security properties due to lack of independence has been considered, for example, by Chor & Rabin [CR87], Dolev, Dwork & Naor [DDN91, DDN00] and Gennaro [START_REF] Gennaro | Achieving independence efficiently and securely[END_REF][START_REF] Gennaro | A Protocol to Achieve Independence in Constant Rounds[END_REF]. In the context of electronic voting, Gennaro [START_REF] Gennaro | Achieving independence efficiently and securely[END_REF] demonstrates that the application of the Fiat-Shamir heuristic in the Sako-Kilian electronic voting protocol [START_REF] Sako | Secure Voting Using Partially Compatible Homomorphisms[END_REF] violates ballot independence, and Wikström [START_REF] Wikström | Simplified Submission of Inputs to Protocols[END_REF][START_REF] Wikström | Simplified Submission of Inputs to Protocols[END_REF] studies non-malleability for mixnets to achieve ballot independence. By comparison, we focus on the violation of ballot secrecy rather than ballot independence.

Sako-Kilian voting protocol

The Sako & Kilian [SK94] electronic voting scheme capitalises upon advances in cryptography to improve the Banaloh & Yung protocol [START_REF] Cohen | Distributing the Power of a Government to Enhance the Privacy of Voters[END_REF]. In particular, the Fiat-Shamir heuristic is adopted to derive non-interactive proofs of knowledge.

INRIA

Protocol description

The scheme is based upon a pair of partially compatible homomorphic encryption functions, that is, a pair of functions f 1 , f 2 over Z q , where q is prime, such that for all i, j ∈ {1, 2} the following properties are satisfied:

❼ f i (x + y) = f i (x) • f i (y), where x, y ∈ Z q ❼ Distributions (f i (x), f j (y)) and (f i (x), f j (x)) are computationally indis-
tinguishable, where x and y are chosen uniformly in Z q .

The Sako-Kilian voting protocol is defined for m ∈ N voters as follows.

Setup. Talliers T and T ′ publish public keys k and k ′ for a public key encryption scheme E (which need not be homomorphic).

Voting. Given vote v i ∈ {-1, 1}, the voter generates nonces

x i , x ′ i ∈ Z q such that v i = x i + x ′
i and constructs her ballot as follows:

Y i = f 1 (x i ) Y ′ i = f 2 (x ′ i ) Z i = E(k, x i ) Z ′ i = E(k ′ , x ′ i )
In addition, the voter is required to prove x i + x ′ i ∈ {1, -1} in zero-knowledge. However, to avoid an interactive proof, the Fiat-Shamir heuristic is applied to derive a signature of knowledge σ i . (For brevity we omit the construction of σ i , see [SK94, Figure 1] for details.)

Tallying. Given ballots Y 1 , Y ′ 1 , Z 1 , Z ′ 1 , σ 1 , . . . , Y n , Y ′ n , Z n , Z ′ n , σ n , tallier T de- crypts each Z i to recover xi and checks Y i = f 1 (x i ), similarly, tallier T ′ decrypts Z ′ i to recover x′ i and checks Y ′ i = f 1 (x ′ i )
; the talliers also check the signature of knowledge σ i . The talliers publish V = m i=1 xi and V ′ = m i=1 x′ i , and the result is

T = V + V ′ , which can be verified by checking f 1 (V ) = m i=1 Y i and f 2 (V ′ ) = m i=1 Y ′ i .

Attacking ballot secrecy

Ballot secrecy means a voter's vote is not revealed to anyone. We show that Sako-Kilian voting protocol does not satisfy this definition of ballot secrecy, by presenting a replay attack which allows an adversary to reveal a voter's vote.

Intuitively, an adversary may observe the ballot posted by a particular voter and recast this ballot by corrupting dishonest voters. The multiple occurrences of the voter's ballot will leak information in the tally and the adversary can exploit this knowledge to violate the voter's privacy. An informal description of the attack will now be presented in the case of three eligible voters.

Attack description.

Let us consider an election with three eligible voters who have identities id 1 , id 2 and id 3 . Suppose that voters id 1 , id 2 are honest and id 3 is a dishonest voter controlled by the adversary. Further assume that the adversary has observed the ballot

Y k , Y ′ k , Z k , Z ′ k , σ k being cast
by the voter whose privacy will be compromised.

Exploiting the absence of ballot independence. As shown by Gennaro [START_REF] Gennaro | Achieving independence efficiently and securely[END_REF], an adversary can replay the ballot Y k , Y ′ k , Z k , Z ′ k , σ k , thereby violating ballot independence. (The violation of ballot independence is due to the adversary's ability to cast the same vote as the honest voter.) Since the ballot was constructed by an honest voter, it is trivial to see that it will be considered valid by the talliers. We will now show how the lack of ballot independence can be exploited to violate privacy.

Violating privacy. The bulletin board will be constructed as follows

Y 1 , Y ′ 1 , Z 1 , Z ′ 1 , σ 1 , Y 2 , Y ′ 2 , Z 2 , Z ′ 2 , σ 2 , Y k , Y ′ k , Z k , Z ′ k , σ k , V, V ′ where k ∈ {1, 2}, V = x 1 + x 2 + x k and V ′ = x ′ 1 + x ′ 2 + x ′ k .
It follows from the protocol description that v i = x i + x ′ i , where i ∈ {1, 2, k}, and the result T = V +V ′ = v 1 +v 2 +v k . Since there will be at least two votes for the candidate voter id k voted for, the voter's vote can be revealed: if T ≥ 2, then v k = 1; otherwise v k = -1. It follows that the voter's privacy has been compromised; moreover, the vote of the remaining honest voter is T -2 • v k .

Schoenmakers's voting protocol

The electronic voting scheme by Schoenmakers [START_REF] Schoenmakers | A simple publicly verifiable secret sharing scheme and its application to electronic voting[END_REF] is based upon [START_REF] Cramer | Multi-Autority Secret-Ballot Elections with Linear Work[END_REF][START_REF] Cramer | A Secure and Optimally Efficient Multi-Authority Election Scheme[END_REF] and aims to provide efficient small-scale elections. Ballot independence is explicitly not provided [Sch99, ➜5].

Protocol description

Given cryptographic parameters (G q , g, h) and hash function H, where G q is a group of prime order q such that computing discrete logarithms is infeasible and g, h are distinct generators of G q , let us recall the scheme for n ∈ N talliers and m ∈ N voters using some threshold t ≤ n.

Setup. Each tallier i ∈ n selects a private key x i ∈ R Z * q and computes the public part y i = h xi .

INRIA

Voting. The voter selects coefficients α 0 , . . . , α t-1 ∈ R Z * q and constructs the polynomial ρ:

ρ(x) = α 0 • x 0 + • • • + α t-1 • x t-1
Given vote v ∈ {0, 1}, the ballot consists of the following components:

❼ Vote: U = h α0+v .
❼ Commitments: C j = g αj , where 0 ≤ j ≤ t -1.

❼ Random shares:

Y i = y ρ(i) i
, where 1 ≤ i ≤ n.

In addition, the ballot includes a signature proof of knowledge [START_REF] Torben | A Threshold Cryptosystem without a Trusted Party[END_REF][START_REF] Chaum | Wallet Databases with Observers[END_REF] demonstrating the correct construction of encrypted shares and a signature proof of knowledge [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF] demonstrating that v ∈ {0, 1}:

❼ Proof of correct construction. Let X i = t-1 j=0 (C j ) i j , where 1 ≤ i ≤ n. For all 1 ≤ i ≤ n, select a random nonce w i ∈ R Z * q and com- pute witnesses a i = g wi , b i = y wi i . Derive the common challenge c = H(X 1 , Y 1 , a 1 , b 1 , . . . , X n , Y n , a n , b n ), and for all 1 ≤ i ≤ n compute re- sponse r i = w i -c • ρ(i). ❼ Proof of valid vote. Compute challenge ĉ1-v ∈ R Z * q , response r1-v ∈ R Z * q and witnesses â1-v = g r1-v •C ĉ1-v 0 and b 1-v = h r1-v •(U/h 1-v ) ĉ1-v . Select a random nonce ŵ ∈ R Z * q .
Compute witnesses âv = g w and bv = h w , challenge ĉv = H(â 0 , b0 , r0 , â1 , b1 , r1 ) -ĉ1-v and response r v = w -α 0 • ĉv .

To prevent a voter casting multiple ballots, the ballots are assumed to be associated with the voter's identity on the bulletin board.

Verification. For each ballot U, C 0 , . . . , C t-1 , Y 1 , . . . , Y n and associated proofs a 1 , b 1 , r 1 . . . , a n , b n , r n and â1 , b1 , ĉ1 , r1 , â2 , b2 , ĉ2 , r2 , check for all 1 ≤ i ≤ n and v ∈ {0, 1} that

a i = g ri • X c i b i = y ri i • Y c i âv = g rv • C ĉv 0 bv = h rv • (U/h v ) ĉv ĉ0 + ĉ1 = H(â 0 , b0 , â1 , b1 )
where

X i = t-1 j=0 (C j ) i j and c = H(X 1 , Y 1 , a 1 , b 1 , . . . , X n , Y n , a n , b n ). (Observe X i = g P t-1 j=0 αj •i j = g ρ(i) .) Tallying. Given encrypted shares Y 1,1 , . . . , Y 1,n , • • • , Y m,1 , . . . , Y m,n of m vot- ers, the homomorphic combination of encrypted shares Y * i is derived, where 1 ≤ i ≤ n: Y * i = m j=1 Y j,i
Let ρ j denotes the jth voter's secret polynomial. For all 1 ≤ i ≤ n, each tallier derives the partial decryption

V i = (Y * i ) 1/xi ; since Y * i = y P m j=1 ρj (i) i = RR n➦ 7643 h xi• P m j=1 ρj (i) , it follows that V i = h P m j=1 ρj (i)
. The talliers must also prove correctness of decryption; it is sufficient to prove equality between discrete logarithms log h y i and log Vi Y * i , we omit these details. Given partial decryptions V 1 , . . . , V t from t talliers, we can compute V = h P m j=1 αj,0 as shown below, where α j,0 is the jth voter's first coefficient and, for simplicity, t = n. Let Lagrange coefficient λ i = l∈{1,...,i-1,i+1,...,n} l l-i , where

1 ≤ i ≤ n. n i=1 V λi i = n i=1 h P m j=1 ρj (i) λi = h P m j=1 ( P n i=1 ρj (i)•λi) = h P m j=1 ρj (0) = V
The result T = m j=1 v j can be derived as follows, where v j is the jth voter's vote.

log h m j=1 U j -log h V = log h h P m j=1 αj,0+vj -log h h P m j=1 αj,0 = log h h P m j=1 vj = T
Although the computation of discrete logarithms is hard in general, given the restricted domain [0, m], the result T can be computed efficiently; for example, the complexity is O(m) by linear search or O( √ m) using the baby-step giantstep algorithm [START_REF] Shanks | Class number, a theory of factorization and genera[END_REF] (see also [LL90, ➜3.1]).

Attacking ballot secrecy

We show that Schoenmakers's voting protocol does not satisfy ballot secrecy, by presenting a replay attack which allows an adversary to reveal a voter's vote. Intuitively, an adversary may identify a voter's ballot on the bulletin board (since it is linked to the voter's identity) and recast this ballot by corrupting dishonest voters. As previously discussed, the multiple occurrences of the voter's ballot will leak information in the tally and the adversary can exploit this knowledge to violate the voter's privacy. An informal description of the attack will now be presented in the case of three eligible voters.

Attack description.

Let us consider an election with n talliers and three eligible voters who have identities id 1 , id 2 and id 3 . Suppose that voters id 1 , id 2 are honest and id 3 is a dishonest voter controlled by the adversary. Further assume that the honest voters have cast their ballots. The bulletin board entries are as follows:

id 1 , e 1 , spk 1 , spk ′ 1 id 2 , e 2 , spk 2 , spk ′ 2
where for i ∈ {1, 2} we have

e i = U i , C i,0 , . . . , C i,t-1 , Y i,1 , . . . , Y i,n spk i = a i,1 , b i,1 , r i,1 . . . , a i,n , b i,n , r i,n spk ′ i = a i,1 , bi,1 , ĉi,1 , ri,1 , âi,2 , bi,2 , ĉi,2 , ri,2

INRIA

That is, e i contains the ith voter's vote U i , commitments C i,0 , . . . , C i,t-1 and random shares Y i,1 , . . . , Y i,n ; spk i demonstrates that the random shares are correctly formed; and spk ′ i demonstrates that U i contains either 0 or 1.

Exploiting the absence of ballot independence. The adversary observes the bulletin board and selects e k , spk k , spk ′ k where k ∈ {1, 2} and id k is the voter whose privacy will be compromised. The adversary submits the ballot e k , spk k , spk ′ k and it immediately follows that the bulletin board is composed as follows:

id 1 , e 1 , spk 1 , spk are all valid signatures of knowledge. We have shown that the protocol does not satisfy ballot independence (observing another voter's interaction with the election system allows a voter to cast the same vote), and this will now be exploited to violate privacy.

Violating privacy. The partial decryptions of the homomorphic combination of encrypted shares can be used to reveal the result T = log h h v1+v2+v k , where k ∈ {1, 2} and v 1 , v 2 are the votes of honest voters. Since there will be at least two votes for the candidate voter id k voted for, the voter's vote can be revealed: if T ≥ 2, then v k = 1; otherwise v k = 0. It follows that the voter's privacy has been compromised; moreover, the vote of the remaining honest voter is T -2•v k .

Discussion

We have informally shown that the protocols due to Sako & Kilian [START_REF] Sako | Secure Voting Using Partially Compatible Homomorphisms[END_REF] and Schoenmakers [START_REF] Schoenmakers | A simple publicly verifiable secret sharing scheme and its application to electronic voting[END_REF] are vulnerable to a replay attack which violates ballot secrecy. In this section we briefly discuss how application of the Fiat-Shamir heuristic may erode privacy, examine how the attacks can be extended beyond the three voter setting, and explore the attacks in the context of standard security definitions.

Independence and the Fiat-Shamir heuristic. The interactive nature of zero-knowledge proofs guarantees independence; by comparison, non-interactive proofs, derived using the Fiat-Shamir heuristic, do not assure independence. As a consequence, application of the Fiat-Shamir heuristic may compromise the security of cryptographic protocols and this paper has shown how ballot secrecy in electronic voting schemes can be violated.

Generalised attacks against ballot secrecy. Our attacks demonstrate that the ballot of an arbitrary voter can be replayed by any other voter. In general, this does not reveal the voter's vote. However, some information is leaked, and colluding voters can replay sufficiently many ballots to leak the voter's vote. Moreover, we have previously shown that there is a realistic threat from a small coalition of dishonest voters [START_REF] Smyth | Attacking and fixing helios: An analysis of ballot secrecy[END_REF][START_REF] Cortier | Attacking and fixing Helios: An analysis of ballot secrecy[END_REF].

Violating standard definitions of ballot secrecy. Intuitively, it should follow that the protocols due to Sako & Kilian [START_REF] Sako | Secure Voting Using Partially Compatible Homomorphisms[END_REF] and Schoenmakers [START_REF] Schoenmakers | A simple publicly verifiable secret sharing scheme and its application to electronic voting[END_REF] cannot satisfy ballot secrecy in formal settings defined by Kremer et al. [START_REF] Kremer | Analysis of an Electronic Voting Protocol in the Applied Pi Calculus[END_REF][START_REF] Delaune | Verifying privacy-type properties of electronic voting protocols[END_REF] and Backes, Hrit ¸cu & Maffei [START_REF] Backes | Automated Verification of Remote Electronic Voting Protocols in the Applied Pi-calculus[END_REF]. These privacy definitions consider two voters A, B and two candidates t, t ′ . Ballot secrecy is captured by the assertion that an adversary (controlling arbitrary many dishonest voters) cannot distinguish between a situation in which voter A votes for candidate t and voter B votes for candidate t ′ , from another one in which A votes t ′ and B votes t. This can be expressed by the following equivalence.

A(t) | B(t ′ ) ≈ A(t ′ ) | B(t)
Formally proving that these protocols do not satisfy these definitions is beyond the scope of this paper. However, informally this result can be trivially witnessed and we deduce either: these definitions are too strong, or there are indeed weaknesses in the protocols we have studied.

  It is trivial to see that each bulletin board entry is valid; that is,spk 1 , spk ′ 1 , spk 2 , spk ′ 2 , spk k , spk ′ k

	′ 1 id 2 , e 2 , spk 2 , spk ′ 2 id 3 , e k , spk k , spk ′ k

RR n➦ 7643


Zhenhui Qi
email: zhenhuiqi@gmail.com

Christoph A Schalley
email: christoph@schalley-lab.de

Host-guest chemistry of dendrimers in the gas phase

Keywords: host-guest chemistry, dendrimers, gas-phase chemistry, mass spectrometry, supramolecular chemistry host-guest chemistry, supramolecular chemistry, dendrimers, mass spectrometry, gas-phase chemistry, molecular mobility

Dedicated to the memory of Dmitry Rudkevich, who died much too early

Introduction

The field of host-guest chemistry of dendritic molecules has grown into a special area of supramolecular chemistry during the last decades (1)(2). The highly branched architectures of dendrimers endow them with unique recognition properties, which are appreciated for constructing diverse supramolecular host-guest systems. Insight into these systems opens up new opportunities not only to understand the fundamental principles in biological process (3)(4), but also to develop functional materials (5)(6)(7). Some ten to fifteen years ago, there was still a debate, whether dendrimers would form specific host-guest complexes at all. Meanwhile it is well known that they do: POPAM dendrimers have not only shown to bind metal ions, but even exhibit an interesting kinetic behaviour in that metal ions quickly complex to the periphery and then need significantly longer to enter the dendrimer core (8). Dendrimers have also been equipped with specific binding sites in their peripheries, e.g. crown ethers (9), urea units (10), ferrocenyl (11) and carbohydrate groups (12). For drug delivery, coreshell particles are under intense investigation (13)(14)(15). However, with the growing complexity of these systems, the dendritic hostguest complexes are often large in size and molecular mass, and often display a highly symmetrical arrangement of building blocks. Therefore it is often rather difficult to characterize their exact structures and to determine the stoichiometries of the hosts and guests involved. For a convincing analysis and characterization, usually a number of different instrumental methods need to be applied (16)(17). Moreover, many researchers became aware of the often quite significant influence of the environment on the formation of dendritic host-guest complexes (18). They can be strongly affected by the presence of the solvent or counter-ions. Stability constants and thermodynamic parameters determined in solution are always influenced by solvent For a long time, mass spectrometry was only considered as an important analytical method in dendrimer chemistry. In most laboratory research, mass spectrometry merely served as an excellent routine analytical tool to determine the purity and to analyze the defects of dendrimers in higher generations (19)(20)(21).

However, increasing evidence indicates the utility of mass spectrometry to go far beyond the mere analytical characterization. The gas phase inside the mass spectrometrer has proved to be particularly beneficial for the analysis of weakly bound host-guest complexes [START_REF] Schalley | Mass Spectrometry and Gas-Phase Chemistry of Non-Covalent Complexes[END_REF][START_REF] Baytekin | [END_REF](24)(25)(26). The high vacuum inside a mass spectrometer provides an efficient means to isolate the complexes and to suppress the highly dynamic guest exchange equilibria in solution. Once the desired complex ions are generated, mass selection becomes possible and a large variety of tandem MS (MS/MS) experiments is available which enable the dendrimer chemist to examine the ions under environment-free conditions. Valuable information of the intrinsic features of the complexes as well as the reactivity of non-covalent species can be obtained. A comparison of these data from the gas phase, i.e. the intrinsic properties, with results from condensed phase, i.e. the properties as influenced by the environment, can consequently contribute significantly to the understanding of noncovalent bonds, and in return to guide the design of supramolecular host-guest system.

The objective of this mini-review is to highlight an emerging area by discussing studies which use tandem mass spectrometry to investigate dendrimerguest complexes. It advertises the great potential of gas-phase studies for dendrimer host-guest chemistry of dendrimers. We will focus on three different aspects: The first part will discuss a gas-phase approach to screen the relative binding strengths of multiple small molecule guests that can bind to the dendrimer periphery in a dynamic library. These gas-phase studies elegantly allow to compare different guests each of which is bound in a multivalent fashion to more than one binding site in the dendrimer. In the second example, dendritic viologen-tweezer complexes represent another type of dendrimer host-guest structure in which the complexation occurred at the core. In contrast to the solution behaviour, a quite pronounced dendritic effect is observed which has a major effect on the stability and on the fragment mechanisms of the viologen dications in the dendrimer core. The differences in the gas-phase behaviour of dendrimers of different generation can be traced back to backfolding of the dendrimer branches. Finally, we will discuss a "spacewalk" at molecular level.

Crown ethers are able to walk along the periphery of POPAM dendrimers without intermediate dissociation. A quite simple hydrogen/deuterium exchange (H/D exchange) in the gas phase is capable of monitoring this highly dynamic intramolecular movement in the gas phase.

Multivalency in the gas phase: multiple guest binding to urea-terminated POPAM dendrimers

Recently, dendrimers are gaining popularity as frameworks for the study of multivalent interactions in biological systems (4,27). A particularly interesting example is the third generation POPAM dendrimer D (Figure 1), which carries 16 peripheral adamantylurea groups (28). As shown in Figure 2, dendrimer D can serve as the host scaffold for guests that can be bound through multivalent interaction. After an initial proton transfer from the guest acid group to the dendrimer's tertiary amines, strong electrostatic interactions exist between the acid anion of the guest molecule and bonds between the urea units of guest and host support binding. Therefore, host D enables a variety of guest molecules based on urea-acid structures to attach on its surface, even including some oligopeptides such as T (29). The most intriguing feature of such a multivalent system is the non-covalent decoration of dendrimer surface, giving rise to a dynamic binding equilibrium in solution, in which the guests can compete with each other and the guest with the optimal binding motif can easily be detected. Moreover, due to the multibranched structures of dendrimers, a dynamic combinatorial library of different complexes with various stoichiometries can consequently form when at least two different guests compete for binding to the dendrimer. Consequently, the multivalency of dendrimers surface is capable of attaching multiple drug molecules, targeting groups and solubilizing moieties coordinately (30).

Although the concept to dynamically modify the periphery of dendrimers is very attractive, the characterization of such a system seems to be a quite challenging task. Because up to eight of guests can bind to the same dendrimer in a dynamic manner, the determination of binding stoichiometries for complexes, in particular in a dynamic library with more than one type of guest is rather difficult. ( 28 and a series of guest molecules by mass spectrometry (31)(32). The transfer of dendrimer D and its host-guest complexes into gas phase is easily achieved by electrospray ionization mass spectrometry (ESI-MS). A small amount of acetic acid is added to the sample solution to achieve a net protonation of the dendrimer complexes. Once the desired complex ions are transferred successfully into the gas phase, the stability of the ions of interest can be probed with tandem MS techniques, for example by fragmenting them in collision-induced dissociation (CID) experiments.

After mass selection of the desired ions, the ions are accelerated, and subsequently collided with a neutral gas in the analyzer cell of a Fourier-transform ion-cyclotronresonance (FTICR) mass spectrometer. During the collision, part of the kinetic energy of the ions is converted into rovibrational excitation, which eventually gives rise to the fragmentation with the weakest bond to represent the most probably cleavage site. In the experiments described so far, all guests in the complexes under study were identical. No drastic change of the dissociation energies is thus expected, unless the guests interact with each other. However, when mixed complexes are treated the same way, a ranking of binding strengths in the gas phase can be obtained. Detailed insight into the influence of the guest structure on the binding strength may provide information about the binding mode. All guests in Figure 1 form complexes except for C2 (32), which lacks both the urea units and a strongly acidic end group. The fact that the urea groups are not mandatory for complex formation indicates that the attractive electrostatic interactions between the guests' phosphonate or sulphonate groups and the tertiary ammonium in the dendrimer's binding pockets are strong enough to generate host-guest complexes with D. For the weaker carboxylic acid guests, the urea group is nevertheless required. This might indicate that no ion pair is formed between host and guest. Instead, hydrogen bonding is likely responsible for guest binding.

Competition experiments are possible, when heterocomplexes are mass-selected and fragmented in the gas phase. The guest which is more readily expelled from the complex is the more weakly bound guest. Such CID experiments can be performed with all possible guest pairs. The result is that guests are bound significantly more strongly when they contain the urea groups. Consequently, hydrogen bonding contributes its share to the binding energy. This finding is in excellent agreement with the trend in solution-phase association constants gained for model systems in chloroform and thus we conclude that binding mode to be the same in solution and in the gas phase.

Finally, the binding strengths of a set of oligopetides with BOC protected amino termini to the dendrimer were also examined. Already, slight structure differences in the tripeptides lead to significant changes the binding strengths. For Ala-Ala-Ala. In the corresponding CID spectra, the initial loss of the latter tripeptide is much more pronounced than that of the triglycine.

The studies discussed here demonstrate the utility of tandem mass spectrometry for a fast screening of guest molecule binding to large molecules. Since dendrimers are multibranched structures, the effects of multivalent binding can thus be examined in the gas phase. Moreover, the examples also nicely show how an analysis of the gas-phase chemistry of dendrimer-guest complexes elegantly contributes to a more profound understanding of both the binding motif (a structural issue) and the binding strengths (a thermochemical issue).

A remarkable dendritic effect: complexes of a molecular tweezer and dendritic viologen dications

Viologens are doubly charged bipyridinium ions which possess a quite electrondeficient dicationic core. They are known to be good guests for molecular tweezer Tw (33) with its extended aromatic systems (Figure 3). In dichloromethane, viologentweezer complexes are quite stable, which is also true when the viologen is decorated with Fréchet's benzylether dendrons on both sides. The tweezer is located at the central core and thus additional interactions of the aromatic rings within the dendrons with the outer convex side of the tweezer may occur particularly in larger generations.

Upon electrospray ionization of the G0 viologen salt in the absence of the tweezer, no bare G0 2+ dications could be detected. Only singly and doubly charged clusters are observed in which the positive charges are counterbalanced by a sufficiently high number of counterions. Density functional calculations for a simple When one equivalent of the tweezer Tw is added to the sample solutions, the mass spectra change dramatically (34). Even for the least stable G0 2+ , quite intense signals correspond to the intact doubly charged 1:1 complexes are observed. The complexes also form as singly charged ions carrying one counterion. However, the mere existence of the complex dication shows the tweezer to stabilize the dications significantly through charge-transfer interaction. Simultaneously, this reduces the strong charge-repulsion effects and thus renders the complex detectable as a free dication. Similarly, dicationic tweezer-dendrimer complexes can be obtained for the larger generations.

For an analysis of the fragmentation behavior of the viologen-tweezer complexes, the desired ions were mass-selected and subjected to a CID experiment.

When monoisotopic tweezer-G0 2+ dications were isolated and examined, one would probably expected to see an initial loss of the tweezer followed by an immediate consecutive fragmentation of the remaining metastable dication (bottom pathway in Figure 4). Indeed, the two expected fingerprint fragments from G0 2+ are observed (Figure 5). However, an additional fragment at m/z 1059 corresponds to a singly charged tweezer-bipyrindium ion and clearly indicates the loss of a di-t-butylbenyzl cation from the complete complex to be operative in the fragmentation of [Tw•G0] 2+ . Clearly, it is also possible that the supramolecular interaction is stronger than the covalent N-benzyl bond. This finding raises the question, which of the two pathways shown in Figure 4 shows that almost all of the bipyridinium cations at m/z 359 vanish in the double resonance experiment and thus must be due to a consecutive fragmentation through the intermediate complex at m/z 1059. Instead, loss of tweezer followed by Coulomb explosion of the G0 2+ dication contributes at best a few percent to the bipyridinium fragment at m/z 359. This experiment clearly identifies the upper fragmentation channel in Figure 4 to the major one in the dissociation of the [Tw•G0] 2+ complex.

The covalent benzylic C-N bond is thus weaker in this complex than the supramolecular interaction between host and guest. The same reactivity pattern was also observed for the tweezer complex with G1 2+ . However, the fragmentation behavior reversed for the complex with the G2 2+ viologen guest. Here, the loss of tweezer represents the first step and generates the bare G2 dication at m/z 1005, which can undergo further fragmentation by benzyl cation loss. The benzyl loss intermediate, however is not observed at all. Consequently, the size of the dendrons plays an important role for the change in fragmentation behavior. dendrons which leads to self-solvation in the gas phase (Figure 6). For G0 2+ , the relatively small benzyl substituents are unable to backfold into the vicinity of the dicationic viologen core. Consequently no self-solvation occurs and the cation remains unstabilized causing the instability of the benzyl-N bond. In G1 2+ , the naphtyl methyl end groups can fold to approach the central viologen in a geometrically favorable manner. However, only a minor stabilization of the dication is achieved, since the naphthalene moieties are not very electron-rich. In contrast, G2 2+ is not only more flexible, but also provides the electron-rich, dihydroxybenzyl branching units which provide efficient internal solvation through the formation of intramolecular charge-transfer-complexes. The backfolding of dendrimer branches not only explains the dication stability order, but also the reversed fragmentation sequence of [Tw•G2] 2+ . The tweezer competes with the backfolded branches of the larger dendrons for the binding to the viologen. Consequently, the supramolecular interaction between tweezer and viologen decreases with increasing the dendron size.

At the same time, the reduced charge repulsion stabilizes the covalent benzyl-N bond with increasing dendron size. For the complex of G2 2+ , the covalent bond is finally stronger than the non-covalent interaction between host and guest.

The gas-phase experiments with the tweezer-dendrimer host-guest complexes add valuable insight into the reactivity of such species which cannot be gained from solution studies. In solution, not only solvent molecules change the properties of the complexes. Even more important, the counterions significantly stabilize the dications and reduce charge repulsion. Also, reversible binding which constantly leads to an exchange of the guest hampers the analysis of such a reaction. Such an exchange is not possible in the gas phase, because the complexes are isolated from each other in the high vacuum of a mass spectrometer.

A molecular spacewalk: 18-Crown-6 walks along the periphery of POPAM dendrimers

Molecular mobility has attracted considerable attention in supramolecular chemistry and biochemistry. Recently, a simple but challenging question (Figure 7) has been answered: Can 18-crown-6 travel on the surface of a POPAM dendrimer? Can they walk from binding site to binding site without intermediate dissociation (35)(36)?

Answering this question is difficult, if not impossible in solution, because the guest is always involved in dissociation/reassociation equilibria and intercomplex exchange.

The critical issue of detecting such an intracomplex movement is to isolate the complexes from each other and from their free components. From the two preceding parts, one might assume the high vacuum of a mass spectrometry to be a good choice, since the gas phase is ideally suitable for studying the isolated complex. However, a simple mass analysis is obviously unable to provide direct evidence, as the intramolecular movement will not cause any mass change. Therefore, a gas-phase reaction is required as a probe, which must meet the following criteria: (1) It has to proceed energetically below the complex dissociation energy (for 18-crown-6 ammonium complexes ca. 180 -200 kJ/mol), (2) must cause a mass change, and (3) needs to be directly linked to the guest movement. These requirements are met by a gas-phase H/D exchange reaction (37). 18-crown-6 (18C6) is well known to bind to primary ammonium ions in solution (38) as well as in the gas phase (39). Furthermore, it efficiently protects the ammonium group to which it is attached against H/D exchange in the gas phase (40)(41). Consequently, one would expect that a complete exchange of all labile hydrogen atoms in the dendrimer periphery is possible, if the crown ether moves around. Instead, 3n hydrogen atoms should be protected against exchange in a dendrimer-crown complex containing n crown ethers, when the crown ether is positionally fixed. Dendritic crown ether/ammonium complexes can easily be generated by ESI when a mixture of host and guest in methanol with 1% formic or acetic acid is sprayed. A broad charge state distribution (up to z = +8 for G5) with various stoichiometries of crown molecule bound to dendrimer (up to n = 5 for G5) is observed. The H/D exchange experiments were carried out with complexes of G1 to G5 POPAM dendrimers. Figure 8a shows the H/D exchange results from G1. When there is no crown bound to singly protonated G1, all labile hydrogen atoms are rapidly exchanged. The exchange is almost complete after ca. 50 ms. A doubly charged 1:1 complex which parallels the singly protonated POPAM since it also bears one free ammonium site, undergoes a similarly fast exchange. Already after 50 ms, the whole isotope pattern has moved behind the threshold at which is would be expected to come to a halt when three protons were protected against exchange.

Instead, a special case is encountered, when both ammonium sites are occupied by crown ethers: The exchange is almost completely suppressed. The last experiment shows that the exchange proceeds through a so-called (40-41) relay mechanism (Figure 8b). One ammonium site must remain unoccupied in order to permit a fast H/D-exchange process.

The same scenario is found up to G5 POPAM dendrimer complexes. The results for G2 are shown in Figure 8c, those obtained with G3 and G4 in Figure 9.

The following G2 experiment further confirmed the exchange behavior observed in G1 (Figure 8c). These results clearly demonstrate the crown ethers to move quite rapidly along the dendrimer periphery.

Mechanistically, the crown ether spacewalk must proceed stepwise: A new hydrogen bridge is formed with a neighboring amine followed by the release of one to the old binding site. Then the next new hydrogen bond is formed and so on. A dissociation-reassociation mechanism can safely be excluded, because the crown ether would not return to the dendrimer once it has dissociated in the high vacuum inside the mass spectrometer. Similarly, a back-side attack mechanism with an intermediate in which both binding sites are fully bound is unlikely. This would require much longer alkyl chains between the two binding sites. So far, the mechanism is quite clear. One question, however, remains: Does the crown ether move as a neutral crown from one ammonium site to another ammonium site or does it move together with a proton from an ammonium to a neutral amino group? These two scenarios are shown in Figures 10a,b Now, the doubly protonated 1:1 complex bears two ammonium groups, one of which is bound to the crown ether. This corresponds to the situation in Figure 10a. An exchange of all six protons would clearly show that a crown movement between two ammonium ions is indeed possible. The singly protonated 1:1 complex, instead, has one ammonium group carrying the crown ether and a free ammonium group and thus corresponds to the situation in Figure 10b. Exchange of only two protons would again indicate the crown to be fixed at the ammonium ion and would rule out the ammonium-to-amine scenario, while the exchange of all five protons would provide evidence for the transfer of a protonated crown ether. The result is clearcut: The doubly charged complex only exchanges three hydrogen atoms, while all five can be exchanged in the singly protonated complex. This clearly indicates a protonated crown ether to move from the ammonium to the amine terminus of the DAD chain.

Likely, charge repulsion prohibits the ammonium-to-ammonium scenario.

  intrinsic interaction between host and guest is thus inevitably challenging to unravel.

  ions incorporated in host D. In addition, multiple hydrogen

Figure 1 .

 1 Figure 1. Top left: Third-generation POPAM dendrimer D with 16 peripheral admantylurea groups. Top right: The postulated binding mode of a dendrimer host with (a) a urea-substituted phosphonate; (b) an N-terminal Boc-protected tripeptide. Bottom: A variety of guests including urea-containing guests U1, U2, C1, P1, and S1. The three guests C2, P2, and S2 lack the urea group and thus serve as reference compounds for examining the binding mode. The Boc-protected tripeptides T (Boc-GGG, Boc-GGA, Boc-AAA, Boc-FGG, Boc-FFF, and Boc-GVV) were also investigated in the gas phase (G = glycine, A = alanine, F = phenylalanine, V= valine, Boc = tert-butoxycarbonyl).

Figure 2 .

 2 Figure 2. (a) ESI-FTICR mass spectrum of a sample of dendrimer D with six equivalents of guest U2. Two species ions of host-guest complexes with 4+ and 3+ charge states are observed respectively. (b) The deconvoluted mass spectrum shows complexes [D•(U2) n ] with n = 0 -8. The mass differences of ∆m = 244 correspond to individual guests U2. (c) CID mass spectrum of mass-selected [D•(U2) 4 ] 3+ . At increasing collision energies, the guest molecules are successively removed as neutral molecules, finally only bare dendrimer ions are left. Reproduced from ref. 31 with kind permission from Wiley-VCH and the authors.

  have studied the multivalent interaction between host D

Figure

  Figure2ashows the ESI spectrum of, for example, a mixture of dendrimer D with six

Figure

  Figure 2c shows the detailed fragmentation picture of the [D•(U2) 4 ] 3+ complex. At

  D shows a clear preference for BOC-Gly-Gly-Gly over BOC-

  compound indeed predict the C-N bond in the viologen dication to dissociate due to the strong charge repulsion once the dication is formed in free form. Therefore, the G0 2+ dication might be a short-lived metastable ion, which decomposes before it can be detected on the timescale of the FTICR mass spectrometric experiments. The two product ions, i.e. a singly substituted, singly charged bipyridinium ion and the corresponding benzyl cation, are indeed observed in the ESI mass spectrum. Besides cluster formation and fragmentation, G0 2+ has two other modes of avoiding being a naked dication: Deprotonation which occurs presumably at the benzylic position and one-electron reduction at the ESI spray capillary to yield the cation-radical.

Figure 3 .

 3 Figure 3. The detailed structures of the molecular tweezer Tw (inset) and dendronsubstituted viologens G0 2+ , G1 2+ , and G2 2+ .

  contributes to what extent. A double resonance experiment provides the answer: In this experiment, the ions with m/z 1059 are constantly removed from the FTICR analyzer cell during the whole duration of the MS/MS all consecutive fragments formed through this ion as an intermediate should vanish as well. The comparison of Figures 5a and 5b clearly

Figure 4 .

 4 Figure 4. Two possible pathways for the fragmentation of the tweezer-viologen complexes. The reactivity switches from the upper to the lower pathway depending on the dendron sizes.

Figure 5 .

 5 Figure 5. (a) Collision-induced decomposition (CID) of mass-selected tweezer-G0 2+ complex. (b) Double-resonance experiment with the same ions, in which the fragment at m/z 1059 was ejected from the reaction cell during the whole experiment. (c) CID experiment with the tweezer-G1 2+ complex. (d) CID experiment with the tweezer-G2 2+ complex revealing a complete change in reactivity. Tweezer loss is the major fragmentation pathway giving rise to dicationic G2 2+ at m/z 1005.

Figure 6 .

 6 Figure 6. Lowest-energy conformations of the viologen derivatives substituted by two 3,5-di-t-butylbenzyl groups (G0 2+ ), by methyl and the G1 dendron (G1' 2+ ), and by methyl and the G2 dendron (G2' 2+ ) calculated by Monte-Carlo conformer search using the MMFF force field implemented in SPARTAN 04. For the two larger structures, one dendron was replaced by methyl in order to reduce the necessary computer time.

Figure 7 .

 7 Figure 7. Schematic representation of crown ether movement along a G4 POPAM dendrimer.

  and can be resolved by H/D exchange experiments on 1,12diaminododecane as a model compound mimicking the dendrimer (Figure10c).

20 Figure 8 .

 208 Figure 8. (a) Left: Left: H/D exchange experiment with singly protonated G1 (0 and 50 ms reaction time).Center: H/D exchange of all ten NH protons of the doubly protonated 1:1 18-crown-6/G1 complex (0 and 50 ms). Right: An extremely slow H/D exchange is observed for the doubly charged 2:1 18-crown-6/G1 complex (0 and 1000 ms). (b) A "relay" mechanism for the gas-phase H/D exchange at protonated POPAM dendrimers explains why the exchange is so slow in [18C6 2 @G1+2H] 2+ . (c) The same scenario is observed for higher generation dendrimers.

21 Figure 9 .

 219 Figure 9. H/D exchange experiments conducted with 18-crown-6 complexes of (a) G3 and (b) G4 POPAM dendrimers. Already after 50 ms, the exchange has proceeded beyond the positions at which it would be expected to stop, if the crown ethers would protect the ammonium protons against exchange (vertical solid arrows). Minor signals in the spectra are due to the typical defects in the dendrimer structure which unavoidably accumulate in the higher generations.

  three hydrogen atoms from the free ammonium ion would indicate the crown to be positionally fixed and rule out the ammonium-ammonium scenario.

Figure 10 .

 10 Figure 10. Two possible mechanisms for crown' spacewalk: (a) ammonium-toammonium scenario; (b) ammonium-to-amine scenario. (c) The model compound 1,12-diaminododecane (DAD).

Conclusions

  Three applications of tandem mass spectrometry in dendrimer host-guest chemistryshow the versatility and the potential of this method: Stoichiometries can be determined. In competition experiments, the binding strengths of different guest can be compared and yield information on the binding mode. Comparison with the solution binding parameters may allow to draw conclusions on the similarities and the solvation-mediated differences. In particular, however, it is interesting to investigate the reactivity in the gas phase, because all dynamic host-guest exchange processes are suppressed in the gas phase. Consequently, only direct dissociation reactions or intramolecular processes can occur providing insight into a completely new reactivity which cannot easily be examined in solution. In our examples, the energetic issues are closely related to structural aspects as well as reactivity. Through a detailed analysis of fragmentation reactions and their relative energies, indications for backfolding could be obtained. With the help of bimolecular reactions, i.e. the H/D exchange with methanol-OD, insight into the intramolecular dynamics and molecular mobility in dendrimer guest complexes could be obtained.

  :/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.great pleasure to give permission and many thanks for taking our work into account.With best regards, BertFrom: Prof. Dr. Christoph Schalley [mailto:christoph@schalley-lab.de] Sent: maandag 15 maart 2010 14:59 To: Meijer, E.W. Cc: z.qi@schalley-lab.de Subject: Copyright permission Dear Bert, Supramolecular Chemistry is organizing a memorial issue for Dmitry Rudkevich. We have put together a mini-review on dendrimer host-guest chemistry in the gas phase (manuscript is attached) highlighting your nice work "multivalency in the gas phase" in Angewandte. May we use the Figure again (Figure2in the manuscript)? Some time ago, you already permitted me to use it in a book, but I wanted to be sure that it is ok, if we use it again.Best wishes, Chris-------------------------Prof. Dr. Christoph A. Schalley Institut für Chemie und Biochemie der Freien Universität Berlin Takustr. 3 14195 Berlin Germany phone: +49-(0)30 838-52639 fax: +49-(0)30 838-55817 email: christoph@schalley-lab.de http://www.chemie.fu-berlin.de/~schalley Page 38 of 38 URL: http:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.edu Supramolecular Chemistry

URL: http:/mc.manuscriptcentral.com/tandf/gsch Email: suprachem@mail.cm.utexas.edu Supramolecular Chemistry

Dear Customer, Thank you for your email. -We hereby grant permission for the requested use expected that due credit is given to th e original source.

-For material published before 2007 additionally: Please note that the (co-)author's permission is also required. If material appears within our work with credit to another source, authorisation from that source must be obtained. Credit must include the following components: