Teck Aguilar

Syue-Ju Syue

Vincent Gauthier

Hossam Afifi

Chin - Liang

Chin-Liang Wang

CoopGeo : a beaconless geographic cross-layer protocol for cooperative wireless ad hoc networks

Keywords: Cooperative networks, wireless ad hoc networks, cross-layer, beaconless geographic routing, relay selection

published or not. The documents may come

I. INTRODUCTION

O VER the last decade, there has been a tremendous wave of interest in the study of cooperative communications for wireless networks. By taking advantage of the broadcast nature of the wireless medium, neighbors overhearing data packets are allowed to assist in the ongoing transmission. Such resource sharing (e.g., power, antennas, etc.) achieved by nodes cooperation is a fundamental idea of cooperative communications. In other words, the number of degrees of freedom (as introduced in [START_REF] Zheng | Diversity and multiplexing: A fundamental tradeoff in multiple-antenna channels[END_REF]) in wireless systems can be effectively increased by enabling collaboration between network nodes. Most attractively, without the requirement of equipping wireless terminals with multiple antennas to §This paper was accepted in part at the 2010 IEEE 71st Vehicular Technology Conference (VTC 2010-Spring), Taipei, Taiwan, May 2010. construct a multiple-input multiple-output (MIMO) system, cooperative techniques break the limitations of the physical size and hardware complexity and, dramatically, are capable to provide spatial diversity as well.

Most existing work on cooperative techniques focuses on physical-layer cooperative relaying schemes, where various diversity-oriented signaling strategies have been proposed and further demonstrated on the basis of information theory [START_REF] Nosratinia | Cooperative communication in wireless networks[END_REF]- [START_REF] Sadek | Multinode cooperative communications in wireless networks[END_REF]. However, to achieve efficient communications while gaining full benefits from nodes cooperation, more interactions at higher layers of the protocol stack, in particular the MAC (Medium Access Control) and network layers, are indispensably required. Furthermore, an efficient cooperation-based MAC (or cooperative MAC) scheme should be not only payloadoriented but also channel-adaptive to improve the network throughput and diversity gain simultaneously; otherwise, an inefficient MAC scheme may even make cooperation gain disappear [START_REF] Shan | Distributed cooperative mac for multihop wireless networks[END_REF].

Two major questions related to cooperative MAC design need to be answered: 1) when to cooperate? 2) whom to cooperate with and how to do selection? For the first question, intuitively there is no need to do cooperation if the direct link is of high quality. In addition, cooperation inevitably introduces inefficiency in some degree due to extra protocol overhead and limited payload length. Therefore a cooperative MAC protocol should be carefully designed to prevent unnecessary cooperation [START_REF] Shan | Distributed cooperative mac for multihop wireless networks[END_REF]. In [START_REF] Ibrahim | Cooperative communications with relay selection: when to cooperate and whom to cooperate with?[END_REF], the authors proposed a cooperation metric that is related to the instantaneous source-relay and relay-destination channel measurements to decide if cooperation is needed. The use of automatic repeat request (ARQ) and hybrid-ARQ schemes in cooperative networks has been discussed in [START_REF] Zhao | Practical relay networks: A generalization of hybrid-ARQ[END_REF], [START_REF] Dianati | A node-cooperative ARQ scheme for wireless ad hoc networks[END_REF]. In [START_REF] Laneman | Cooperative diversity in wireless networks: efficient protocols and outage behavior[END_REF], an incremental relaying protocol using limited feedback from the destination was proposed, and it can be viewed as an extension of ARQ in the relaying context. The second question about cooperative MAC design addresses the typical relay selection problem. There may exist a group of available relays around the source; however, some are beneficial and some not. How to find the optimal one(s) efficiently and effectively is of vital importance to a practical MAC protocol.

Recent years have seen growing interest in the subject of relay selection [START_REF] Shan | Distributed cooperative mac for multihop wireless networks[END_REF]- [START_REF] Zhao | Practical relay networks: A generalization of hybrid-ARQ[END_REF], [START_REF] Ng | Joint optimization of relay strategies and resource allocations in cooperative cellular networks[END_REF]- [START_REF] Wei | Distributed optimal relay selection in wireless cooperative networks with finite-state markov channels[END_REF]. Some focus on the design of enhancing system reliability in a centralized manner [START_REF] Ibrahim | Cooperative communications with relay selection: when to cooperate and whom to cooperate with?[END_REF], [START_REF] Ng | Joint optimization of relay strategies and resource allocations in cooperative cellular networks[END_REF]- [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF], neglectful of the needs of overhead produced by nodes coordination, unmindful of the feasibility of capturing a lot of channel state information (CSI) among nodes, unsuitable for being used in resource-constrained networks. To make relay selection more efficient, the authors of [START_REF] Liu | Cooperative wireless communications: A cross-layer approach[END_REF] described how physical-layer cooperation can be integrated with the MAC layer to improve network performances. Other cross-layer issues are also included in [START_REF] Liu | Cooperative wireless communications: A cross-layer approach[END_REF]. In [START_REF] Beres | Selection cooperation in multi-source cooperative networks[END_REF], the authors presented the concept of selection diversity and demonstrated that the single best-relay selection can outperform distributed space-time coded relaying schemes in terms of outage probability. In [START_REF] Bletsas | A simple distributed method for relay selection in cooperative diversity wireless networks, based on reciprocity and channel measurements[END_REF]- [START_REF] Guo | Performance of a cooperative relay-based auto-rate mac protocol for wireless ad hoc networks[END_REF], distributed relay selection schemes based on the knowledge of local instantaneous channel conditions without requiring topology information are proposed. CoopMAC [START_REF] Liu | A cooperative mac protocol for wireless local area networks[END_REF] and rDCF [START_REF] Zhu | rDCF: A relay-enabled medium access control protocol for wireless ad hoc networks[END_REF] are similar cooperative MAC protocols, which alleviate the throughput hindrance caused by low-datarate nodes. The main idea is to select a high-datarate node helping the data delivery through two-hop transmission. In [START_REF] Zhao | Practical relay networks: A generalization of hybrid-ARQ[END_REF], a generalized concept of hybrid automatic repeat request scheme (hybrid-ARQ) is applied to relay networks, allowing that packet retransmissions could be performed at any relay that overhears and decodes earlier transmitted blocks when the negative acknowledgment (NACK) is received. In [START_REF] Shan | Crosslayer cooperative triple busy tone multiple access for wireless networks[END_REF], the authors proposed a busy-tone-based cross-layer cooperative MAC (CTBTMA) protocol, where busy tones are utilized to solve collisions in a cooperation scenario and address the optimal relay selection problem. In [START_REF] Gokturk | Cooperative mac protocol with distributed relay actuation[END_REF], the authors introduced an adaptive relay selection based on random access relay advertisements, by which each relay decides whether to participate in the cooperation. In [START_REF] Yu | Opportunistic relay selection with cooperative macro diversity[END_REF], the authors studied a fully opportunistic relay selection scheme under partial CSI for cellular networks, where macro and micro diversities are jointly considered. Considering the time-varying characteristic of some mobile environments in which the widely used memoryless channel assumption becomes unrealistic, [START_REF] Wei | Distributed optimal relay selection in wireless cooperative networks with finite-state markov channels[END_REF] addressed a relay selection problem under finite-state Markov channels. In [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF], we have proposed a geographic relay selection scheme based on the knowledge of location information of nodes. By jointly combining the source-relay and relay-destination distances, the optimal relay offering the best cooperative link can be efficiently determined. However, the selection process proposed by [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF] requires a central controller to decide which relay is most helpful, leading to more overhead and power consumption. One goal of this paper is to present a distributed relay selection protocol based on [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF], with MAC-physical cross-layer design.

Likewise, in view of the interaction between the MAC and network layers, we also incorporate routing issues in this paper as a properly designed MAC protocol can facilitate routing process at the network layer, in particular the beaconless geographic routing1 (BLGR) [START_REF] Sanchez | Beacon-less geographic routing made practical: challenges, design guidelines, and protocols[END_REF]- [START_REF] Sanchez | BOSS: Beaconless on demand strategy for geographic routing in wireless sensor networks[END_REF]. BLGR is one of the most efficient and scalable routing solutions for wireless ad hoc and sensor networks. The key advantage of BLGR is that it needs neither prior knowledge of network topology for making a route decision nor the periodic exchange of control messages (i.e., beacons) for acquiring neighbors' geographic locations. A current node can make its own routing decisions by using local information. In general, a BLGR protocol comprises two operating phases: forwarding phase and recovery phase. In the forwarding phase, routing decisions are made according to the greedy mechanism, a neighbor closest to the destination is chosen as the next hop of a current node. Greedy forwarding, however, fails when reaching a local minimum, i.e., a current node that has no neighbor closer to the destination. In this case, the recovery mode based on the well-known face routing algorithm is triggered to find another path to the destination.

It is worth noting that BLGR at the network layer is usually coupled with MAC protocols to offer better network throughput and preserve advantageous properties such as localized operation and high scalability. A paradigm of network-MAC cross-layered BLGR protocol is as follows: through a contention process at the MAC layer, each candidate forwarder sets a contention timer depending on the progress to the destination such that the optimal candidate (closest to the destination in greedy sense) responds first, as a result of time-out. Hence, cross-layer design between the network and MAC layers is quite significant. In [START_REF] Sanchez | BOSS: Beaconless on demand strategy for geographic routing in wireless sensor networks[END_REF], Sanchez et al proposed a cross-layered BLGR protocol called BOSS, which uses a threeway (DATA/RESPONSE/SELECTION) handshake and an area-based timer-assignment function to reduce collisions among responses during the forwarder selection phase. However, when operating in recovery mode, BOSS performs face routing by requiring the exchange of complete neighborhood information. To avoid this drawback, we present a fully beaconless protocol that does not require beacons in both the greedy forwarding and recovery modes.

Above, we have introduced the roles of interactions between the MAC and physical layers and between the network and MAC layers, in a cooperative scenario. In this paper 2 , we aim at integrating the network, MAC, and physical layers as a network-MAC-physical crosslayer design to enhance overall system performance. Two issues, routing and relay selection, are the two chief considerations. We assume that the channel changes quickly as a symbol-wise varying channel. The proposed novel cross-layer framework, called CoopGeo, consists of two joint cross-layer designs, a joint network-MAC design for next hop selection and a joint MAC-physical design for relay selection. In particular, both the routing and relay selection solutions in CoopGeo are geographic protocols using contention-based selection processes, providing a strongly practical multi-layer integration for cooperative networks.

The contributions of this article are as follows:

• We propose a distributed MAC-PHY cross-layer design for relay selection based on the geographic approach [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF], where the best relay is chosen as the one that provides the minimum average pointto-point SER.

• We present a fully beaconless approach to geographic routing with a MAC-NWK cross-layer design, where both the greedy forwarding and recovery modes are executed without periodic exchange of beacons and complete neighborhood information. • Based on the use of geographic information and contention processes, the framework of CoopGeo that supports localized operation as well as high scalability is considerably practical for cooperative wireless ad hoc networks.

The rest of the paper is organized as follows. The network model of cooperative multi-hop networks and the problem statement are described in section II. Section III details CoopGeo, i.e., the proposed cross-layer design for cooperative wireless ad hoc networks, in which beaconless geographic routing and relay selection, along with a feasible protocol, are included. In section IV, we give the numerical simulation results for CoopGeo and evaluate its performance by comparing with an existing protocol. Finally, the conclusions are presented in section V.

II. NETWORK MODEL AND PROBLEM STATEMENT

A. Network Model

We consider a wireless ad hoc network of k nodes randomly deployed in an area, represented as a dynamic graph G(V, E), where V = {v 1 , v 2 , . . . , v k } is a finite set of nodes and E = {e 1 , e 2 , . . . , e l } a finite set of links between the nodes. We denote a subset N (v i ) ⊂ V , i = 1, . . . , k, as the neighborhood of the node v i , defined as those nodes within the radio range of v i . Throughout this paper, we consider there is a single session in the network, where data delivery may cross over multiple hops.

Fig. 1(a) depicts the wireless ad hoc network model, in which the source S sends its data to the destination D in a multihop manner. In this figure the dashed circle centered at S illustrates the radio range of S, and so on. At the beginning of every data transmission, S broadcasts the data to its neighbors N (S). One of these neighbors N (S) is chosen as the next hop through a forwarder selection process, denoted as F 1 . Two transmission modes, namely direct and cooperative modes, are considered to operate in each hop. In the direct mode, a point-to-point communication is performed by direct transmission; in the cooperative mode, it is done by cooperative relaying. The cooperative mode operates only when F 1 cannot correctly decode the data from S. After having a correct version of the data packet, F 1 acts as the source node and repeats the same procedure, and so on until the data packet reaches the destination D.

Since the multihop transmission is realized by concatenating multiple single-hop schemes, as shown in Fig. 1(b), for convenience of notations we denote S as the current source in a current hop and F the forwarder, also called the next hop or the intermediate node in this paper. In addition, we represent R i , i = 1, . . . , |N (S)|, as the candidate relays of S, one of which is going to cooperate with S whenever needed. In the following we introduce the signal models for the direct and cooperative transmission modes, respectively.

In the direct mode, S broadcasts its symbol x at the time index i with transmission power P , where the average power of x is normalized to unity. The received signals at F can be expressed as

y (i) S,F = √ P h (i) S,F x + n (i) S,F , (1)
where h S,F is the channel coefficient from S to F and n S,F is the additive noise term. Throughout this paper, we assume that each node has a single antenna operating over frequency-flat Rayleigh fading channels and can only either transmit or receive data at any time slot. Moreover, the fading channels are assumed to be sufficiently fast-varying such that any channel coefficient, say h u,v , modeled as h u,v ∼ CN (0, σ 2 u,v ), is constant over a symbol duration and may change from a symbol to another as an i.i.d. random process. We also assume that all the channel coefficients among radio links are independent. Finally, we model all the noise terms as complex Gaussian random variables with zero mean and equal variance N 0 , where, without loss of generality, we assume N 0 = 1.

For the cooperative mode, it applies a two-phase decode-and-forward (DF) strategy with single-relay selection, described as follows. In the first phase, S broadcasts its symbol x with transmission power P x while the next hop F and a selected relay R (through a relay selection process) listen. The received signals at F and R can be respectively expressed as

y (i) S,F = P x h (i) S,F x + n (i) S,F , (2)
y (i) S,R = P x h (i) S,R x + n (i) S,R , (3)
where h S,R is the channel coefficient from S to R and n S,R is the additive noise term. In the second phase, with the simple adaptive DF strategy [START_REF] Herhold | A simple cooperative extension to wireless relaying[END_REF], the selected relay decides whether to forward the decoded symbol to the next hop. If the relay is able to decode the transmitted symbol correctly, it forwards the decoded symbol with identical transmission power P x to the next hop, and if not, it remains idle. For practical use of this adaptive mechanism, we consider that each relay is able to evaluate its own condition based on an SNR threshold.

If the received SNR at the relay is greater than a certain threshold, the relay forwards; otherwise, it remains idle.

I R = 1, if R decodes the symbol correctly, 0, otherwise. (4)
Then, the received signals at the the next hop in the second phase can be written as

y (j) R,F = P x I R h (j) R,F x + n (j) R,F , (j = i) (5)
where h R,F denotes the channel coefficient from R to F and n R,F denotes the AWGN. Finally, the next hop coherently combines the received signals from the current source and the selected relay, i.e., y

S,F and y

(j)
R,F , by using a maximum ratio combining (MRC) y (j)

F = P x h (i) * S,F y (i) S,F + P x I R h (j) * R,F y (j) R,F . (6)
Consequently, the decoded symbol x at the next hop is given by

x = arg min x∈A |y F -P x (|h (i) S,F | 2 + I R |h (j) R,F | 2 )x| 2 , ( 7
)
where |A| = Θ denotes the cardinality of Θ-ary constellation.

By invoking the performance analysis in [START_REF] Su | Cooperative communication protocols in wireless networks: Performance analysis and optimum power allocation[END_REF], the resulting symbol error rate (SER) at the next hop can be expressed as

P s ≈ 4N 2 0 b 2 P 2 x σ 2 S,F A 2 σ 2 S,R + B σ 2 R,F , (8)
which is a tight approximation in a high SNR regime, where b =

3 2(M -1) , A = M -1 2M + (1-1/ √ M ) 2 π
, and B =

3(M -1) 8M + (1-1/ √ M ) 2 π
in the case of M -QAM modulation. Moreover, we make the following assumptions in the network model: 1) the network is dynamic and the network topology, including the cardinality of a node's neighborhood, the location of nodes, and the linkage between nodes, changes over time due to wireless environments, duty circles, and node failures, etc.; 2) each node is aware of its own location; 3) in addition to itself's location, the source knows the location of the destination, and so does any intermediate node; 4) all the network nodes are homogeneous, and each could become a source, relay, or forwarder.

B. Problem Statement

In considering how cross-layer design improves network throughput and reliability for wireless cooperative ad hoc networks, the first question that arises concerns the joint MAC-network cross-layer routing design. For a network G(V, E), given a source-destination pair v S , v D ∈ V , the objective of a routing task is to find a subset of forwarders P F = {v F1 , v F2 , . . . , v Fn } ⊂ V that builds a routing path from v S to v D with successful packet delivery guaranteed. In particular, each forwarder in P F is determined locally, within a forwarding area defined as the radio coverage of the current source, which is divided into a positive progress area (PPA) and a negative progress area (NPA). In both, the PPA and NPA areas, the beaconless greedy forwarding (BLGF) and beaconless recovery forwarding (BLRF) phases are applied, respectively (as shown in Fig. 2).

The second question that this study addresses concerns the joint MAC-PHY cross-layer relay selection design. The aim of CoopGeo relay selection is to find a subset of optimal relay nodes P R = {v R1 , v R2 , . . . , v Rm } ⊂ V \ P F to enhance the network reliability, where each optimal relay v Ri that minimizes the average point-topoint SER for each cooperative hop is locally selected within a predefined relaying area.

One design goal of CoopGeo is to develop a fully beaconless approach to geographic routing that does not rely on periodic exchange of beacons as well as complete neighborhood information. Therefore, forwarder and relay selection use a local contention process based on geographical information and area-based timers. A specified interval of time T max is assigned to each selection process.

By tackling the above issues, we contemplate a feasible cross-layer protocol that comprehensively integrates the NWK, MAC, and PHY layers to achieve a highlyefficient communication. In the following section we detail the framework of the proposed cross-layer design.

III. COOPGEO: A GEOGRAPHIC CROSS-LAYER PROTOCOL FOR COOPERATIVE WIRELESS NETWORKS

CoopGeo, in general, performs two tasks in wireless cooperative ad hoc networks: routing and relay selection. As described above, the routing process works in two phases, i.e. BLGF and BLRF. Both phases share equally a T max interval of time where the forwarder selection is executed. The first half of the T max period is allocated to the BLGF phase and the second half to the BLRF phase.

In the BLGF phase, a next hop that provides maximal progress toward the destination is selected through a timer-based contention process. When failing to find a next hop in the BLGF phase, the routing process enters transparently to the BLRF phase and applies face routing by using graph planarization along with a select-andprotest principle. Cooperative relaying is required after the routing task, whenever the selected next hop decodes the data packet erroneously. In this case, CoopGeo starts out to execute the relay selection task within another interval of time T max , selecting an optimal relay that offers the best cooperative link between the current source and the next hop.

Fig. 1(a) gives an example for both the routing and relay selection in CoopGeo. The nodes competing in the BLGF phase are those located in PPA, i.e., X 1 , X 2 , R 1 , and F 1 . Those located in NPA, i.e., W 1 , . . . , W 4 , are considered to compete in the BLRF phase. The node F 1 is selected as the forwarder node, where the data transmission between the source S and the forwarder F 1 is carried out through a direct or cooperative transmission. In the case of cooperative transmission, the candidate relays with respect to the transmitter-receiver pair (S, F 1 ) that participate during the relay selection process are those within the relaying area (that will be defined later), including R 1 and X 1 . In this figure R 1 is selected as the optimal relay node of the cooperative transmission.

A. Beaconless Greedy Forwarding (BLGF)

At the beginning of a data transmission, S triggers the BLGF phase of the routing process by broadcasting its data to the neighborhood and then waits for the best next hop's response during the first half of the T max time. During this period, the neighborhood compete to forward the message by setting their contention-based timers (T CBF ), as explained in Section III-A1. When the best forwarder node is selected due to its timer expiration, it sends a clear-to-forward (CTF) message to S, then, the other candidates overhearing this message suppress their running timers and delete the data received from S. Since some candidates situated at the forwarding area may be unable to hear the CTF message, the hidden terminal problem could appear. To prevent it, S broadcast a warning message (SELECT) to indicate that a forwarder node has been found. The hidden candidates overhearing it, will suppress their timer and the data packet. Immediately, F send an acknowledgement (ACK) to S and thereafter, it acts as the source and repeat the process hop-by-hop until the data is delivered to the final destination D.

1) Geographic contention-based forwarder selection (T CBF ): To implement the BLGF phase, we base the timers settings on the metric proposed in [START_REF] Sanchez | BOSS: Beaconless on demand strategy for geographic routing in wireless sensor networks[END_REF], which applies an area-based assignment function. Fig. 2 depicts, as mentioned above, two areas, PPA and NPA, that divide the radio coverage of a current source, both of which are further divided into sub-areas called Common Sub-Areas (CSAs) in order to avoid collisions during the contention period. Moreover, those candidate nodes situated at the same CSA offer similar progress toward D, and thus, they have similar T CBF values. Note that unlike [START_REF] Sanchez | BOSS: Beaconless on demand strategy for geographic routing in wireless sensor networks[END_REF], we divide the NPA area by using concentric coronas instead of slides as used at the PPA area. We will discuss the reason at the BLRF section.

The timer setting for each candidate node is given as follows. First, each candidate node situated in PPA identifies which CSA group it belongs to by using the following equation:

CSA P P A = N SA × r -(d S,D -d Fi,D ) 2r , (9)
where N SA is a predefined even number of sub-areas to divide the coverage area, r is the transmission range which is equal to the largest progress, and (d S,D -d Fi,D ) represents the candidate progress to the destination. Next, given CSA P P A , hereafter called CSA, each candidate calculates its T CBF timer according to:

T CBF = CSA × T max N SA + rand T max N SA , (10)
where T max represents the maximum delay time that the current source S will wait for a next hop's response, and rand(x) a function obtaining a random value between 0 and x to reduce the collision probability. The T CBF function allocates the first half of T max to PPA candidates for the BLGF phase and the second half to the NPA candidates for the BLRF phase.

B. Beaconless Recovery Forwarding (BLRF)

As introduced before, the BLGF mode may suffer from the local minimum problem: the packet may be stuck at a node that does not have a neighbor (at PPA) closer to the destination than itself. To solve this problem, the Beaconless Forwarder Planarization (BFP) algorithm of [START_REF] Kalosha | Selectand-protest-based beaconless georouting with guaranteed delivery in wireless sensor networks[END_REF], which guarantees the packet delivery is applied at BLRF. BFP reduces the number of messages exchanged by using the select-and-protest principle. In the select stage, some NPA neighbors are selected to form a planar subgraph according to a contention function, then, in the protest stage, falsely planar edges are removed from the subgraph. Finally, the traditional face routing algorithm is applied to select the forwarder node.

BFP is implemented at the BLRF phase of CoopGeo as follows. First, the current source detects the local minimum when a T max /2 time has passed without receiving any CTF message from any neighbor situated at PPA. Thus, CoopGeo switches automatically from the BLGF mode to the BLRF mode so that, BFP is applied during the second half of T max . To accomplish this, the candidate nodes situated at the NPA area determine their CSAs and compute their contention timers (T CBF ) that will be used by the BFP algorithm. Once the planar subgraph is build, S send a SELECT message to the node that has been elected forwarder node, which confirms the reception with an acknowledgement.

In [START_REF] Sanchez | BOSS: Beaconless on demand strategy for geographic routing in wireless sensor networks[END_REF], the CSAs of NPA are created according to the progress toward the destination. CoopGeo, by contrast, adopts the distance with respect to the node that is suffering the local minimum problem, and accordingly the slides are modified to concentric coronas. Thus, The NPA area is divided into n = N SA/2 equally sized concentric coronas (see Fig. 2), where the width of the i-th corona is ( √ i -√ i -1)r 1 , and r 1 is the radius of the first corona, being calculated with r 1 = r/ √ n. To use the same terminology as the one used at the BLGF phase, in the following a corona will be referred as a CSA. To set a contention timer, a candidate F in NPA first finds its CSA N P A index by using the following equation:

CSA N P A = √ n • d S,F r 2 + N SA 2 . ( 11
)
With knowledge of their CSA N P A index, hereafter called CSA 3 , each NPA forwarder candidate determines its contention timer according to [START_REF] Zhao | Practical relay networks: A generalization of hybrid-ARQ[END_REF], and BFP is applied.

In this paper, we do not explain the BFP algorithm of [START_REF] Kalosha | Selectand-protest-based beaconless georouting with guaranteed delivery in wireless sensor networks[END_REF] in detail. Instead, we present an example to illustrate the process in Fig. 3. Let us consider a scenario where the source S is surrounded by six neighbors which respond in the order: F 1 , F 4 , and F 5 according to their timers defined by [START_REF] Zhao | Practical relay networks: A generalization of hybrid-ARQ[END_REF]. F 2 receives the CTF message from F 1 and becomes a hidden node, F 3 receives the CTF from F 4 , and F 6 receives the CTF from F 5 . Thus, the hidden nodes are F 2 , F 3 and F 6 . F 2 is located in the proximity region (Gabriel Graph) of F 1 and F 3 in the proximity region of F 4 . So, in the protest phase, F 2 protests against F 1 and F 3 protests F 4 . Thus, S removes the links with violating nodes (node in the proximity

C. MAC-PHY Cross-Layered Relay Selection

The relay selection process takes place after the forwarder selection whenever the demand for cooperation is announced by a forwarder. In such a case, a new contention period will be allocated for relay selection. The relay selection process, in this paper, is based on the selection criterion of [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF], in which we had addressed a geographic relay selection problem. Specifically, the best relay is selected according to a distance-dependent metric m i , as shown in [START_REF] Liu | Cooperative wireless communications: A cross-layer approach[END_REF], relying on a combination of the source-relay and relay-destination distances.

Rewriting (8)-with a relay index i introduced-in terms of coding gain and diversity order, we have

P s = (∆ • γ) -d , (12)
where ∆ denotes the coding gain of the scheme, given by

∆ = b 2 σ 2 S,F 16
A 2 σ 2 S,Ri + B σ 2 Ri,F -1 , ( 13
)
d = 2
is the diversity order, and γ = P/N o represents the SNR, where P = 2P x is the total transmission power. The goal is to select the best relay that maximizes the coding gain ∆ and, consequently, minimizes the SER. In [START_REF] Yi | Diversity order analysis of the decodeand-forward cooperative networks with relay selection[END_REF], the only term affecting the coding gain is

m i ≡ A 2 σ 2 S,Ri + B σ 2 Ri,F , i = 1, 2, ..., N . ( 14
)
Consider a σ 2 i,j ∝ d -p i,j path loss model, where p represents the path loss exponent. Then the channel variances σ 2 i,j in ( 14) can be replaced with the distance-dependent parameters d -p i,j . Thus, ( 14) becomes

m i = A 2 d p S,Ri + Bd p Ri,F , i = 1, 2, ..., N , ( 15
)
where m i is treated as our relay selection metric, which indicates the SER performance at the forwarder-the smaller the metrics is, the better the resulting SER performance will be. Therefore, the best relay can be determined according to the following criteria 4 ,

i * = arg min i∈{1,..,N } m i = arg min i∈{1,..,N } A 2 d p S,Ri +Bd p Ri,F . ( 16
)
We note that the best relay selected by the above criterion is the one that provides the best source-relayforwarder cooperative link in terms of average SER at F . The relay selection process in [START_REF] Wang | A geographic-based approach to relay selection for wireless ad hoc relay networks[END_REF], however, requires a central controller to make a best-relay decision according to the responses from all candidate relays. To reduce the required overhead while achieving a more efficient relay selection process, we propose a distributed relay selection protocol using MAC-PHY cross-layer design, as presented in the following part.

1) Geographic contention-based relay selection: The election process starts as soon as each candidate relay overhears the DATA/CTF packets. Each possible relay acquires two relative distances d S,Ri and d Ri,F to calculate its own selection metric according to [START_REF] Liu | Cooperative wireless communications: A cross-layer approach[END_REF]. Here the path loss exponent is assumed as a known parameter. For the purpose of decentralization, the relay selection metric m i is encoded in time difference inside a timer-based election scheme. Once a candidate whose timer expiration happens first, it relays the data packet to F , and the others candidates cancel their timers after receiving the packet. This contention-based relay selection scheme provides a distributed and efficient way to determine the best relay for each cooperative hop, and it answers the major question about cooperative MAC design, i.e., whom to cooperate with and how to do selection? The metric defined in [START_REF] Liu | Cooperative wireless communications: A cross-layer approach[END_REF] indicates the cooperative link quality in terms of average point-topoint SER, depending on the modulation type and the locations of nodes. In order to translate our relay selection selection metric ( 15) into a timer we normalized it according to their relative distance from x * , which is be the best placement of a relay (minimized the average point-to-point SER). We denote x S , x F , and x i as the locations of the current source, the forwarder, and the i-th candidate relay, respectively. In addition, we define f as a mapping function that maps a candidate relay's location into its relay selection metric (x S and x F are fixed), as in [START_REF] Bletsas | A simple distributed method for relay selection in cooperative diversity wireless networks, based on reciprocity and channel measurements[END_REF]. The optimal point x * can be obtained by solving the optimization problem [START_REF] Gletsas | A simple cooperative diversity method based on network path selection[END_REF]. Thus, the best relay is the one whose metric is closest to f (x * ).

f (x i ) = A 2 x i -x S p + B x i -x F p (17) minimize f (x) = A 2 x -x S p +B x -x F p (18) x * = A 2 x S + Bx F A 2 + B (as p = 2) . ( 19
)
We then derive a mapping function M, which scales our metric function f into the interval [0, 1]:

M(f (x)) = f (x) -f (x * ) f (x max ) -f (x * ) , ( 20
)
where x max is an arbitrary point defined geometrically as far as possible of x * inside the relay area 5 Finally, a contention timer at each candidate relay is set by using the following function:

T CBR = T max M(f (x)) + rand 2T max N SA . ( 21
)
2) Relay selection area: The CoopGeo relay selection process do not use control messages as in the forwarding selection process so as to guarantee that only one node has been selected as relay, and thus avoiding message duplications or collisions. Besides overhearing the relayed message that triggers the contention timers suppression of the other candidate nodes, we have considered the relaying area size as a way to control these issues. Since the candidates should reside in a predefined area where relay selection is executed, the relaying area is determined by the source and forwarder nodes positions. In Fig. 4(a) and 4(b), two relaying areas are depicted. First, let the set C represent the potential relay nodes situated in the relaying area formed by the intersection of the source and forwarder node coverage areas. Second, let the set D represent a relaying area shaped by a Reuleaux triangle from the source node point of view. In the first case, for any relay candidate x i ∈ C, its selection metric is mapped onto this set, where M(f (x i )) ∈ [0, 1]. For the Reuleaux triangle, any relay x i and any other possible relay x j have the following relationship:

x i -x j 2 ≤ r, ∀x i , x j ∈ D, i = j,
where r is the transmission range of a node. Hence, from the relaying areas depicted in the figure, the Reuleaux triangular area is the best suited to be used since all relay candidates can hear to each other, and accordingly, the hidden relay problem can be effectively avoided which is not the case of the intersection relaying area. 5 xmax is an arbitrary point over the relay area used for normalization purpose, in [START_REF] Liu | A cooperative mac protocol for wireless local area networks[END_REF] f (xmax) is theoritically the maximal distance that could be exist between x * and any other point inside the relay set, for example in Fig. 4(a) the perfext value for xmax is the intersection between the transmission radius of S and F.

D. CoopGeo in Action

In this subsection, we depict the behavior of nodes running CoopGeo (cf. Fig. 5) when a data transmission between a source and a destination is performed.

When the source S intends to transmit its data to the destination D, it checks if the channel is free for a predefined time interval. In this case, S broadcasts its data packet DATA and starts a T S1 timer. The neighbors of the source then receive the packet, store it, and set up their T CBF timers, as defined in [START_REF] Zhao | Practical relay networks: A generalization of hybrid-ARQ[END_REF], to participate in the forwarder selection process. 6The neighbor F ∈ F i whose timer expires first sends a CTF control message to claim the forwarding status, then, it initializes a T F 1 timer. The other candidates hearing this control message quit the forwarding selection process.

The DATA/CTF handshake carried out by S and F is used to initiate the relay cooperation on demand if it is needed, since within the CTF message, F indicates if relay cooperation is needed in case of error decoding. In this way, the neighbors situated in the relaying area formed by S and F and being able to correctly decode the DATA 7 start their T CBR timers, as defined in [START_REF] Zhu | rDCF: A relay-enabled medium access control protocol for wireless ad hoc networks[END_REF], to participate in the relay selection process.

When S receives the CTF message, it replies with a SELECT message which confirms the forwarding status to F , and updates its T S1 timer to the maximum delay time allowed to receive an ACK from F . Meanwhile, the relay candidates decrement their T CBR timers. Thus, when the candidate R ∈ R i expires its T CBR timer the first, it becomes the relay node and immediately relay the stored data. The other candidates hearing the transmission notice that another node has relayed the data and quit the relay selection.

Consequently, the forwarder node combines the received signals from S and R, decodes the data, and stops its T F 1 timer. Then, it sends an acknowledgment to S and continues the CoopGeo execution toward D.

In addition to T CBF and T CBR timers, two other timers were used: T S1 at the source and T F 1 at forwarder node. At the beginning T S1 represents the maximum allowed time to find a forwarder node in the direction of D, given by

T S1 = T DAT A + T CT F + T max , (22)
where T DAT A and T CT F represent the data and CTF packet transmission times respectively, and, T max represents the maximum time interval allowed to the forwarding selection process. For simplicity, in the equation, we do not express the propagation delay. Since the DATA/CTF handshake represents that a forwarder node F was selected, T S1 is updated to a value that represents the maximum delay time allowed to receive an acknowledgement from F and it depends on whether relay cooperation is executed. The updated timer is given by

T S1 = T SEL + T ACK if no cooperation is needed T SEL + T max + T DAT A + T ACK otherwise , (23)
where the first statement includes the transmission time of the SELECT (from S to F ) and ACK (from F to S) messages; the second statement includes the required time of the first statement as well as T max and T DAT A which correspond to the maximum allowed time for the relay selection and the time needed to relay the packet.

For T F 1 , the affected value depends on whether the forwarder F correctly decodes the received data from

T F 1 = T CT F + T SEL if no cooperation is needed T CT F + T SEL + T max + T DAT A otherwise , (24)
where the first statement allocates to T F 1 the time required to transmit the CTF message and the time required to receive a SELECT message from S respectively; the second statement adds to the first statement the maximum allowed time to select a relay node and the time the relay node needs to send the relayed data, respectively. Similar to T S1 timer, T F 1 does not consider the propagation delay.

If the timer T S1 of S expires before receiving a CTF or an ACK from F , we have different possibilities: 1) S could not find a forwarder; 2) F could not receive the SELECT message from S 3) F could fail; 4) F could not receive the data packet from R in the cooperative mode. For all these situations, the CoopGeo protocol is restarted.

Thus, we can see that the two most significant timers are T CBF and T CBR , which are used to select a forwarder F and an optimal relay R in each hop through contention mechanisms. The timers T S1 and T F 1 just help to detect a problem during the CoopGeo execution.

IV. PERFORMANCE EVALUATION

We first consider a single-hop cooperative relay network with N = 5 available relays, deployed in R 2 . Denote (x, y) as the coordinates of nodes. We locate the source and the destination at (0, 0) and (1, 0) respectively, and randomly place, with uniform distribution, the relays in a square field following {(x, y) | 0 ≤ x ≤ 1, |y| ≤ 0.5}. We assume that the channel variances between any two nodes follow σ 2 i,j ∝ d -p i,j , where the path loss exponent is taken to be p = 2 in our simulations. The channel variance is normalized to unity for unit distance. QPSK modulation is used in this simulation and the fading channels are assumed sufficiently fast-varying such that the channel coefficients keep constant only within every symbol interval. The number of network topologies is 200.

For each realization of nodes distribution, we can determine the distances from each relay to the source as well as destination, and then the corresponding selection metric for each relay can be determined by using [START_REF] Beres | Selection cooperation in multi-source cooperative networks[END_REF]. According to the selection criterion introduced in Sec. III-C, the best relay is the one with the minimum selection metric, while the second best relay has the second minimum selection metric and so on. Fig. 6 depicts the SER versus SNR performance of the above scenario, where SNR is defined as P/N 0 and P is the total transmit power fixed. In Fig. 6, the performance of direct transmission from the source to the destination is provided as a benchmark for a noncooperation scheme. Fig. 6 shows that the selected best relay contributes to the minimum SER at the destination as compared to other relays. In addition, it also reveals that worse relays corresponds to larger selection metrics, that is, the smaller the selection metrics, the better the resulting SER performances. Thus, we have demonstrated that by using the geographical information, nodes in cooperative networks can efficiently perform relay selection to improve the SER performance at the destination. In addition, we also compare the performance with a possible relay selection approach, named random relay selection, which means that the source randomly selects a cooperating relay without any information for each transmission. We see, in Fig. 6, that the performance curve of the random selection scheme lies in between the best and worst selections. This is because each relay has the same opportunities to be selected so that the performance will be averaged over all the distributed relays.

The next step in our simulation methodology is to evaluate the PHY/MAC layer performance of CoopGeo with Monte-Carlo simulations. We simulated the three lower layer processes, and our simulation settings are given in Table I. Our results are based on 20,000 random generated topologies, where all the nodes are competing to access the channel. We start by solving the two problems stated in Section II-B. Once the forwarder and In Fig. 7(a), we show the average packet error rate of two different protocols, one is the proposed CoopGeo using a cooperative relaying technique and the other is BOSS [START_REF] Sanchez | BOSS: Beaconless on demand strategy for geographic routing in wireless sensor networks[END_REF]. The packet error rate presented in Fig. 7(a) includes both the probability of collision inside different contention periods and the probability of error over the wireless channel. Fig. 7(a) shows that our protocol experiences a lower packet error rate of 2.5 times less than the traditional geographic based routing protocol in the best circumstances. Also, we can see that the packet error rate of the two protocols gets closer to each other as a function of the increased number of nodes in the neighborhood. This error rate depends on the number of nodes and is induced by the collisions inside the different contention periods. Moreover, in Fig. 7(b), we show that CoopGeo improves significantly the average error transmission probability with increasing the number of nodes in the neighborhood. This is due to the accurate selection of the relay node when more nodes are present in the neighborhood. We note that the CoopGeo experiment provides a very low transmission error rate, which allows increasing the constellation size of the modulation scheme to improve the bandwidth efficiency without loosing end-to-end throughput.

B. Results with Varying Input Parameters

1) Varying the contention window T max : In this simulation, we investigate the impact of the contention window size T max (that controls the delay affected to a contending node when it tries to forward/relay a packet) on the CoopGeo performance. Initially, we simulate our protocol with T max values from 100µs to 1000µs. In Fig. 7(c), we see that the collisions caused by the contending nodes when they send their CTF and relayed messages decrease while increasing the T max size. The sizes from 500µs to 1000µs are the best suited for CoopGeo, as they achieve much lower collision probability as compared with the other cases. We analyze the relationship between the normalized throughput with cooperative communications vs. the CTF-relayed messages collision probability, we observe that we may use a smaller T max size without affecting the performance of the protocol when fewer contending nodes are used for the case T max = 300µs, as shown in Fig. 7(e).

Taking T max = 500µs from the previous result as a reference show us that for a smaller saturated throughput rate with respect to T max = 300µs value, we may handle scenarios with higher densities.

2) Varying the constellation size: Finally, in Fig. 7(d), we provide the saturated throughput of the (MAC-PHY cross-layer) CoopGeo and compare it with a traditional geographic MAC-routing approach BOSS. Fig. 7(d) shows that the CoopGeo outperforms the traditional scheme in terms of saturated throughput, with different constellation sizes used. Due to very low transmission error rate in the cooperation-based CoopGeo scheme, we are able to increase the constellation size according to different transmission environments without deteriorating the end-to-end throughput.

V. CONCLUSIONS

In this paper, we have proposed a cross-layer protocol CoopGeo based on geographic information to effectively integrate the NWK, MAC, and PHY layers for cooperative wireless ad hoc networks. The CoopGeo provides a MAC-NWK cross-layer protocol for forwarder selection as well as a MAC-PHY cross-layer protocol for relay selection. Both the selection schemes are based on geographical information of the nodes without periodic exchange of beacons and complete neighborhood information. Simulation results demonstrate that the proposed CoopGeo can work with different densities and achieve better system performances than the existing protocol like BOSS, in terms of packet error rate, transmission error probability, and saturated throughput. Due to the beaconless local operation property, the CoopGeo is very efficient and scalable to any change in the network topology.

Fig. 1 .

 1 Fig. 1. (a) Cooperative multihop ad hoc network model (b) Direct and cooperative modes for each hop

Fig. 2 .

 2 Fig. 2. Area division for CoopGeo routing. F1 and F2 are sub-area 0 and 1 of PPA respectively, whereas F3 and F4 are sub-area 4 and 5 of NPA respectively.

Fig. 3 .

 3 Fig. 3. Beaconless Recovery Forwarding happens at NPA area when the Beaconless Greedy Forwarding fails

Fig. 4 .Fig. 5 .

 45 Fig. 4. (a) Mapping of the metric onto the set C (b) Mapping of the metric onto the set D for a normalized distance between the current source (0, 0) and its next hop (1, 0)

  0

Fig. 6 .

 6 Fig.6. Performance comparison for relay selection when using from the best to worst relays.

Fig. 7 .

 7 Fig. 7. (a) Packet error rate for Tmax = 500µs; (b) End-to-end transmission error probability for Tmax = 500µs; (c) CTF-Relayed message collision probability with changing Tmax from 100µs to 1000µs; (d) CoopGeo saturated throughput for QAM fom 16-128; (e) Normalized saturated throughput and collision probability for Tmax = 300µs and Tmax = 500µs

Geographic routing, based on location information for route decisions, can be applied to the so-called Selection Diversity Forwarding[START_REF] Larsson | Selection diversity forwarding in a multihop packet radio network with fading channel and capture[END_REF],[START_REF] Souryal | Information efficiency of multihop packet radio networks with channeladaptive routing[END_REF] -another way of achieving spatial diversity via forwarder selection -exploiting channel state information (CSI) and PHYnetwork cross-layer integration to select routes with favorable channel conditions. However, we do not examine this channel-adaptive scheme in this paper. The diversity gain we discuss is only from relay selection in cooperative networks.

This paper is the extended version of our previous work[START_REF] Aguilar | A cross-layer design based on geographic information for cooperative wireless networks[END_REF].

A CSA value at the forwarding selection is a nonnegative integer that falls in [0, N SA -1], where 0 corresponds to the area closest to D and (N SA -1) to the farthest one.

Eq. (8) is a bound and it is given as an asymptotically tight approximation at high SNR. As the SNR is sufficiently high, the average symbol error rate (SER) as in (8) is the same with the exact SER. For low SNRs, although[START_REF] Shan | Distributed cooperative mac for multihop wireless networks[END_REF] does not hold anymore, it does not affect the correctness of the selection for the best relay (or the second-best relay, the third-best relay, and so on).

In geographic protocols, the source generally has to indicate the location information of both itself and the destination in the packet header. The header added in the beginning of a packet is usually transmitted through low rate codes so that one could neglect its transmission error within the transmission range.

Neighbors can determine the correctness of the DATA based on the measurements of received SNRs, as described in Sec. II-A.S, or relay cooperation is executed. For the former, F listens to the channel and waits for a SELECT message from S, which completes the direct communication mode; for the latter, F waits for the SELECT message and DATA relayed, from the source and the relay node, respectively.


Jean-François Laslier

Why not proportional?

This paper reviews the arguments that justify the principles of proportional and degressively proportional representation.

Introduction

In current practice, apportionnements are obtained through negociation, with references to principles of justice, fairness, or e¢ ciency. This essay is devoted to the second aspect: What has been, and what should be, the content of the notions of "justice", "fairness" and "e¢ cientcy" with respect to apportionnement problems? Usual justi…cations in this literature rest on intuitive appeal for equality, but the structure of the apportionnment problem is complex enough that it is not clear what exactly we should aim at equalizing, or that equality should be the ultimate goal. In this regard I …rst review the early literature, which considers as obvious the idea that strictly proportional representation is ideal (section 2). In the more recent literature I distinguish three major arguments.

The Poor Representativity argument in favor of degressive proportionality (section 3) echoes the ancient view that a single delegate cannot represent well a very large number of citizens. This view has been given a clean mathematical expression known as the Square Root Law. The welfarist approach (section 4) has, more recently, clearly enunciated the argument in favor of proportionality, a point which I call here the Pure Majoritarian argument in favor of proportionality. The welfarist framework also provides a simple argument in favor of degressive proportionality, which I call the Utilitarian-Egalitarian argument. This last point appears to be the mathematical expression of the commonly mentionned idea that large countries would have too much power in a strictly proportional system.

Proportional representation

Equality is a very basic form of justice requirement, which appears in almost all de…nitions of justice or just institutions. Many philosophical as well as practical controversies can be seen as debates about what should be equalized, but once the equalizandum is found, the determination of justice is "a matter of weight", an operation essentially quantitative. Consider, for instance Aristotle's classi…cation of the social philosophies of his time: "... all men agree that what is just in distribution must be according to merit in some sense, though they do not all specify the same sort of merit, but democrats identify it with the status of freeman, supporters of oligarchy with wealth (or with noble birth), and supporters of aristocracy with excellence.

The just, then, is a species of the proportionate."

[Nichomachean Ethics Book V, chapter 3]
The practical question of allocating seats of an assembly to represent voters presents itself already in mathematical, quantitative, terms: "How many"seats per country, per district, per party, per voter, etc. In such a case, Aristotle's phrase "The just is a species of the proportionate" can easily be taken word for word. Then the general requirement of equality may seem, at …rst sight, to have a non-questionable consequence: the ultimate democratic unit is the citizen, therefore one should seek to equalize the number of seats per citizen. Many would consider this de…nition of a "just" apportionment as obvious, and would not ellaborate further on the notion of equality.

For instance, concerning the European Parliament, Balinski and Young (1982a) wrote: "Trans-national parties have formed. Members of Parliament no longer vote in national blocs; instead of representing purely national interests they represent people in one larger European Community. This new situation means, however, that representatives ought properly to represent equal numbers of constituents no matter in what nation they happen to reside."

Starting from the a priori idea that the representational ideal was proportionality, the early mathematical literature on the subject has thus neglected to provide further justi…cation of why proportionality is desirable. Instead of this normative enquiry, it has focused on a peripheral, albeit very practical question: the question of the rounding methods. If each representative is to represent the same number of citizens, strictly proportional representation usually would recommend fractional numbers of representatives. In practice, one has thus to move away from strict proportionality in order to have a de…nite, integer, number of representatives. Practical apportionnement can only be proportional "up to one seat", and the di¤erent rounding methods can be compaired to that respect (Balinski and Young 1982b).

The Cambridge Compromise (Grimmet et al, 2011) has tackled carefully the questions of roundings to integers, but has also put forward the idea that the principle of degressive proportionality should be conceived independently of the rounding questions.

Degressive proportionality

The voting power literature started with the observation that with a weighted voting rule, the possibility for the vote of a country to make a di¤erence is not in direct relation with its weight. A well-known example is the voting rule used at the Council of the European Union in 1958-1973 after the Treaty of Rome, which is the …rst version of the European Union.

The European Economic Community had six member states. France, Germany and Italy had 4 votes each, Belgium and the Netherlands had 2 votes and Luxembourg had 1 vote. Acts proposed by the Commission required 12 votes to be adopted.

In this case, the single Luxembourg vote can never make a di¤erence for reaching or not the threshold of 12 votes. Formally, Luxembourg has no power at all.

An even simpler example is a two-voter society using weighted majority rule with unequal weights for the two voters. Then the smaller voter has no power at all. Such examples make it clear that it would be a mistake to trust that proportional representation automatically ensures proportional power.

From this observation, and with the objective of designing a "fair" apportionment system and of representing people equally, one might therefore seek to equalize across citizens the voting power, de…ned as the probability that a citizen, through the election, makes a di¤erence.

It is important at this point to note that the voting power approach relies on hypotheses that must be made precise to describe how individual opinions are formed and translated into votes of their representatives. Also, one should not confuse the question of how many delegates should one country send to an assembly and the question of how many votes should be given to each country in a council deliberation. In the former case, the delegates of the country may well belong to di¤erent parties and split their votes, in the latter case, the country will have one voice. In both cases, proportionality can be a theoretical answer, but the two cases are clearly not to be confused.

The most usual hypothesis is "independent voting". This means that the individual opinions are independent random variables with the same law (usually a probability :5 to favor or to object the proposal) and that, most importantly, any two individuals have the same probability to be in agreement, whether they are citizens of the same country or not.

In the case of "Bloc voting", that is when each country is represented by a single spokesman (its government) or if all the representatives vote the same way, a much-celebrated result, known as the "square-root law" is obtained. Under this set of hypotheses, the power of an individual citizen to change her country's vote will be equalized across individuals if the weight of each country is proportional to p n, where n is the number of citizens in the country (Penrose, 1946; Lindner and Machover 2004, S÷ omczyński and • Zyczkowski, 2004, 2010). The logic behind this result is well explained by Penrose himself: "...small electorates are less susceptible to control by resolute blocs and are likely to obtain more representative governments than large electorates. If factors other than numerical size are constant, the spokesman for any electorate represents a section of that electorate proportional to the square root of the total number of electors."

The political argument is that the quality of national representations decreases with the size of their populations. We could call this point the Poor Representativity argument in favor of degressive proportionality. Under speci…c assumptions (independence), this decrease of quality can be expressed mathematically, leading to the concluclusion that the probability for a citizen of a country of size n to be pivotal is proportional to 1= p n. Giving weight p n to the country compensates exactly and is thus "fair" because it equalizes the probability of being decisive among citizens of the di¤erent countries.

Up to my knowledge this precise argument was …rst raised by Penrose and was not discussed in political science. A somehow related idea is that overly large bodies of constituents cannot form a nation. To quote again Aristotle: "You cannot make a city of ten men, and if there are a hundred thousand it is a city no longer."[Nichomachean Ethics Book IX, chapter 10]. But Penrose's idea is to explain the loss of representativity by the statistical ‡utuations of independent variables, and this particular point can hardly be found, even informally stated, in the political science literature.

Felsenthal and Machover (1998) propose another equalisandum besides voting power: the expected value of the majority de…cit, where the majority de…cit after a decision is 0 for all countries where a majority of voters support the decision, and is equal for the other countries to the di¤erence between the number of individuals who object to the decision and the number of of individuals who aggree with the decision. A square-root law can then be derived, again under the assumption of independent voting.

In testing the theoretical ideas that justify the square root law, Gelman, Katz and Bafumi (2004) noticed that the empirical estimate one can produce of the probability of being pivotal is closer to 1=n than to 1= p n. They deduce that the proportional representation is "basically fair"compared to a representation that would follow the square-root law.

Di¤erent formulas and indices have previously been proposed to quantify various kinds of voting power: see [START_REF] Shapley | A method for evaluating the distribution of power in a committee system[END_REF], Banzaf (1965), [START_REF] Owen | Political games[END_REF], or [START_REF] Laruelle | Assessing success and decisiveness in voting situations[END_REF]. These formulas are more or less explicitely related to models of how countries'votes derive from the opinions of the citizens and to how coalitions of countries emerge. They can be used to describe actual parliaments (see [START_REF] Barr | Who has the power in EU?[END_REF] for the EU). Surveys of the theory of voting power have been published by Felsenthal and Machover (1998) and more recently by [START_REF] Laruelle | Voting and Collective Decision-Making[END_REF].

The square-root law is an instance of degressive proportionality (up to rounding). Degressively proportional allocations are often found in practice and advocated [START_REF] Lamassoure | Report on the composition of the European Parliament European Parliament[END_REF]. This may explain why the square-root law has gained some popularity among those who discuss which mathematical formula could be adopted as a rule to de…ne the weights of representatives in commissions and/or the composition of parliaments. 1 But the argument itself upon which the square-root rule is based, the Poor Representativity argument, has not gained much endorsement. In a sense the intellectual construction of the square-root rule is appreciated because of its consequences more than as a justi…cation of these consequences.

The Cambridge Compromise took as a constraint that the apportionnement should be degressively proportional. It recommends a Base+Prop formula: a number of seats is divided equally among the countries independently of their population …gures and a number of seats is allocated in proportion of the population. The consequence of using a Base+Prop formula is a degressively proportional distribution of seats (up to roundings). The proposal is not grounded on a single principle to be applied or on a criterion to be optimized, but the idea can nevertheless be faithfully explained as resulting from two (contradictory!) principles. A principle of equality among states is served by the Base, that is the …xed number of seats allocated to each of them, and a principle of equality among citizens is served by the proportional part of the allocation.

Welfarism

The ideal of equalizing voting power may be criticized, as any form of egalitarianism. For instance, a trivial way to equalize voting power would be to make decisions randomly, with no regard to individuals'opinions. This obviously bad solution is egalitarian, which proves that equality cannot be the only criterion. A voting rule has consequences for each citizen. If we are able to measure how good the rule is for each citizen, be it by some "voting power" measure or any other index, we obtain, associated to each rule, a distribution of the index accross the whole population. It is this distribution which has to be evaluated.

As is common in social sciences, in evaluating such distributions, one is faced with a trade-o¤ between e¢ ciency and equality, two requirements which are partially, but not completely, opposed. The apportionment problem is no exception and, as an institutional design problem, requires for its solution that the social objectives be clearly stated.

For a single yes/no decision, Barbera and Jackson (2006) show that the rule that would maximize the sum, across individuals, of expected utility is a weighted voting rule, where the weight of a country is proportional to the social importance of the issue at stake for this country's citizens. Barbera and Jakson use a hypothesis of independence across countries and [START_REF] Beisbart | Welfarist evaluations of decision rules for boards of representatives[END_REF] and [START_REF] Beisbart | Welfarist evaluations of decision rules under interstate utility dependencies[END_REF] relax this hypothesis to show how the results then depend on how di¤erent countries'interests are correlated. (See also [START_REF] Laruelle | Voting and Collective Decision-Making[END_REF] This approach ellaborates on a very natural argument in favor of proportionality which can be stated, in its simplest form, as follows:

Suppose that the citizens of a country always share the same opinion; that is the country's vote. Suppose moreover that the stake is the same for all citizens in all countries, say +1 or 0. We can think that a citizen will earn 1 Euro if the collective decision matches her will and 0 if not. Then the e¢ cient collective decision is clear: it should follow the will of the majority, for that is the way for the whole society to bene…t more. In that case, the majoritarian outcome is easily obtained by applying to each country's vote a weight proportional to its population. This provides justi…cation for proportionality by the e¢ ciency of majority rule in these one-shot yes/no decisions, which have the same importance for everyone. We can call this point the Pure Majoritarian argument in favor of proportionality.

It turns out that this simple point is quite robust to a number of variations. Suppose for instance that, within each country, not all citizens but a …xed fraction (larger than :5) of them agree with the country's vote. Then simple computation shows that the result is the same. Suppose now that the opinions are randomly generated. Since proportionality is optimal in every instance, it is also optimal ex ante, for instance in expectation.

The obvious drawback of the Pure Majoritarian argument is that, when we do not take one but several decisions, members of small countries are less often satis…ed than members of large countries. The argument can then be turned into arguments in favor of decreasing proportionality in two ways. Still consider, for simplicity, the extreme case where all the citizens of a country share the same opinion.

First, consider that the objective is not e¢ ciency but equality, among citizens of di¤erent countries, of the probability p i that the …nal decision matches citizen i's preference. Give the same weight to all countries, large or small. Then if opinions are independent from one country to the other, p i is same within each country and also the same from one country to the other. Equalty is thus achieved. One can obtain in this way a justi…cation for the idea that countries should be represented per se, independently of their size. Because degressive proportionality is "in between" constant and proportional weights, it is justi-…ed by a compromise between e¢ ciency and equality [START_REF] Beisbart | Welfarist evaluations of decision rules under interstate utility dependencies[END_REF].

Second, if one has in mind that a constitutional decision such as the weights given to the countries will govern not only one but a long sequence of future decisions, one should consider that the utility for a citizen of the voting scheme is not simply +1 or 0 but stems from the fact that her will is going to be more or less often ful…lled. This frequency, say p i is the object of preference of the individual i, and the social judgment should bear on the distribution of these frequencies p i in the population. It turns out that if the utility attached to frequency p i by the individual i is a concave function, say (p i ), common to all individuals, then maximizing the sum of individual utilities ususally leads to recommend weighted voting rules whose weights are degressively proportional with respect to the countries' populations [START_REF] Koriyama | Optimal apportionnement[END_REF][START_REF] Macé | Computing the optimal weights in a utilitarian model of apportionnment[END_REF]. The concavity of the individual evaluation of p i can be interpreted, as usual, in terms of decreasing marginal utility. The marginal satisfaction obtained by an individual when her p i is raised from, say, :60 to :61 is larger than the one obtained when her p i is raised from, say, :71 to :72.

The two previous arguments, equality and concave utilitarianism, are in fact equivalent, a pattern familiar in normative economics, which links utilitarianism to the theory of inequality (see for instance [START_REF] Blackorby | Utilitarianism and the theory of justice[END_REF]. Indeed, when the social criterion is the sum of individual utilities, the concavity of utility with respect to p i also means that the society would gain by having one p i decresased from :71 to :70 and another p j increased from :60 to :61. The two versions of this idea can thus be given a single name: the Utilitarian-Egalitarian argument in favor of decreasing proportionality.

This argument is intuitive in the case of a committee, where each country has one and only one delegate who is to be given some weight, and in the case of a parliament dealing with issues about which all the citizens share the opinion voiced by their representatives. It can be proven that the argument is still valid as soon as the citizens'opinions are not completely independent from their country of residence [START_REF] Koriyama | Optimal apportionnement[END_REF].

The idea that small countries should be given relatively more weight because, otherwise, they would systematically lose is familiar in politics. The Utilitarian-Egalitarian approach articulates this sensible concern. When a populous country has a weight proportional to its population, its citizens are better treated than the citizens of smaller countries because that country is relatively more often in a position to dictate its choice. It may therefore be fair to redistribute part of this large weight to smaller countries.

The Cambridge Compromise solution was not designed to be optimal with respect to some utilitarian-egalitarian criterion. It nevertheless shares an important qualitative property with these allocation schemes, namely degressive proportionality.

See the open letter "How to vote in the Council of the European Union", signed by several scientists in

http://chaos.if.uj.edu.pl/~karol/pdf/voting08.pdf