Ichrak Amdouni
email: ichrak.amdouni@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Cedric Adjih
email: cedric.adjih@inria.fr

OSERENA: a Coloring Algorithm Optimized for Dense Wireless Networks

Keywords: Wireless networks, ad hoc networks, wireless sensor networks, node coloring, distributed coloring, dense networks, bandwidth efficiency

The goal of this paper is to present OSERENA, a distributed coloring algorithm optimized for dense wireless sensor networks (WSNs). Network density has an extremely reduced impact on the size of the messages exchanged to color the WSN. Furthermore, the number of colors used to color the network is not impacted by this optimization. We describe in this paper the properties of the algorithm and prove its correctness and termination. Simulation results point out the considerable gains in bandwidth.

Introduction and state of the art

Graph coloring can be seen as a specific case of graph labeling: labels, usually called colors, are assigned to vertices (respectively edges) of a graph subject to certain constraints. Depending on which graph element is colored, we obtain vertex or edge coloring. For both, the objective is to minimize the number of colors needed to color the whole graph. Typically, the constraint considered for h-hop vertex coloring, with h an integer 1 is: no two vertices that are k-hop neighbors with 1 k h have the same color. The Vizing's theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF] states that the minimum number of colors needed to 1-hop color a graph, number denoted χ, meets ∆ χ ∆ + 1, where ∆ is the maximum degree of the graph. The h-hop node coloring problem has been proved NPcomplete in [START_REF] Garey | Computers and intractability: a guide to theory of NP-completeness[END_REF] for h = 1 and in [START_REF] Mccormick | Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem[END_REF][START_REF] Amdouni | Node coloring for dense wireless sensor networks[END_REF] for any h > 1.

This explains why heuristics are used for large graphs. Authors of [START_REF] Hilgemeier | Fast heuristics for the edge coloring of large graphs[END_REF] compare the performances of different heuristics for edge coloring over standard benchmarks (taken from a list of 119 graphs given at CP2002) for small graphs (< 500 nodes). They show that among the tested heuristics, ant1 often finds the optimum or a number of colors differing not much. A survey of local search methods (TabuCOL, simulated annealing, neighborhood search, and clustering guided search) can be found in [START_REF] Galinier | A survey of local search methods for graph coloring[END_REF] and [START_REF] Wu | Coloring large graphs based on independent set extraction[END_REF]. If these algorithms are efficient for small graphs, it is no longer the case with large random graphs [START_REF] Wu | Coloring large graphs based on independent set extraction[END_REF]. Hybrid algorithms can be used, as well as the extraction of large independent sets from the graph to obtain a smaller residual graph easier to color (see for instance EXT RACOL that needs 2.5 hours to color 1000 nodes with a density of 5 in [START_REF] Wu | Coloring large graphs based on independent set extraction[END_REF]). The main performance criteria of a coloring algorithm are the number of colors and the time needed to color the considered graph. Of crucial interest is the approximation ratio of coloring algorithms that is defined as the ratio of the number of colors obtained by the algorithm to the optimal number. A well-known coloring algorithm is FirstFit [START_REF] Cargiannis | A tight bound for online coloring of disk graphs[END_REF] that sequentially assigns colors to nodes. Each node is colored with the first available color. Depending on the coloring order, different coloring results are obtained. Approximation ratio of coloring algorithms for grids, triangular lattices and hexagonal graphs can be found in [START_REF] Bermond | Improper colouring of weighted grid and hexagonal graphs[END_REF]. All nodes having the same color constitute a class. Hence, graph coloring can also be seen as determining independent sets of maximum size.

Coloring has been applied to wireless networks to improve medium access efficiency. Thus, with node coloring, nodes access the medium in time slots corresponding to their color [START_REF] Rajendran | Energy-efficient, collision-free medium access control for wireless sensor networks[END_REF][START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF][START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF]. Only nodes that do not interfere can transmit simultaneously, hence collisions are avoided while spatial reuse of the bandwidth is provided. The smaller the number of colors, the shorter the activity period in data gathering applications [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF][START_REF] Lee | FlexiTP: a flexible-schedule-based TDMA protocol for faulttolerant and energy-efficient wireless sensor networks[END_REF][START_REF] Gobriel | TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism[END_REF]. A color can be mapped into a channel, that is why graph coloring has been applied to channel assignment reducing radio interferences [START_REF] Hassan | A review of interference reduction in wireless networks using graph coloring methods[END_REF].

Running a distributed coloring algorithm on WSNs (Wireless Sensor Networks) is very challenging because of their strong limitations. They have low capacity of storage and computing, low energy especially for battery operated nodes and the network bandwidth is also limited. That is why algorithms supported by WSNs must be of low complexity. More challenging are dense WSNs, where a node cannot maintain its 2-hop neighbors because of memory limitation and a single message cannot contain all the information relative to the 2-hop neighbors of a node. Examples of dense WSNs are given by smart dust where microelectomechanical systems called MEMS can measure temperature, vibration or luminosity. Applications can be monitoring of building temperature, detection of seismic events, monitoring of pollution, weather prediction for vineyard protection... In this paper, we show how to optimize a coloring algorithm for dense WSNs. We present OSERENA, an optimized version of the node coloring algorithm SERENA [START_REF] Mahfoudh | Node Coloring and Color Conflict Detection in Wireless Sensor Networks[END_REF]. The optimization consists in the reduction of the algorithm overhead in both sizes of data stored and messages exchanged to color the network. Indeed, OSERENA does not require neither the storage nor the exchange of neighbors up to two hops. Furthermore, we prove that OSERENA keeps the same number of colors as SERENA. Moreover, OSERENA produces a small convergence time that is equal, most of the time, to the time needed by SERENA to color the algorithm.

The paper is organized as follows. In Section 2, we present OSERENA, a 3-hop node coloring algorithm that is optimized for dense networks. In section 3, we present the properties of OSERENA regarding the correctness, the overhead induced, and its convergence time. We also prove that OSER-ENA is equivalent to a centralized version of 3-hop node coloring. In Section 4, we evaluate the performance of OSERENA for many network configurations, varying network size and node density. We show that unlike the previous work in [START_REF] Mahfoudh | Node Coloring and Color Conflict Detection in Wireless Sensor Networks[END_REF], OSER-ENA keeps a number of rounds similar to the number of rounds induced by SERENA (the unoptimized version) to color the network, while using smaller messages. This property is illustrated through an extensive performance evaluation by means of simulations. Finally, we conclude in Section 5.

Coloring optimized for dense networks

The goal of this section is to make possible the use of the coloring algorithm in dense wireless sensor networks. We show how to reduce the overhead in terms of 1) memory required to store the data maintained by each node and 2) bandwith used by exchanging messages between neighbors. Of course this overhead reduction must not decrease the performance of the coloring algorithm: the number of colors and the time needed to color all network nodes must be kept small. First, we give some definitions followed by the basic principles of 3-hop node coloring.

Assumptions and definitions

Central assumptions and definitions

The type of node coloring needed to support a given application depends on the type of:

• communications supported: unicast and/or broadcast;

• application: general where any node is likely to exchange information with any neighbor node or on the contrary tree type where a node exchanges information only with its parent and its children in the data gathering tree;

• acknowledgement for unicast transmissions: immediate or deferred.

In this paper, we focus on 3-hop node coloring, which was proved in [START_REF] Mahfoudh | Node Coloring and Color Conflict Detection in Wireless Sensor Networks[END_REF] to be necessary to support general communications, where unicast transmissions are immediately acknowledged. We assume an ideal environment where: Assumption A0: All links are symmetric and stable. Assumption A1: Each node has a unique address in the network. Assumption A2: Any node does not prevent the correct receipt of any other node out of its transmission range.

A 3-hop node coloring is said valid if and only if no two 1-hop, 2-hop or 3-hop nodes have the same color. The smaller the number of colors obtained, the better the coloring algorithm.

The time complexity of a coloring algorithm is generally evaluated in terms of rounds. By definition, a round is such that any node receives the messages sent by its 1-hop neighbors, processes them and broadcasts its own message to its 1-hop neighbors. The space complexity is given by the number and size of messages sent per node.

Further assumptions and simplifications

In the some sections, we will assume a more specific model, closely related to a common model for wireless sensor networks: the unit disk graph model [START_REF] Clark | Unit disk graphs[END_REF]. Hence:

• Nodes are modeled as a set of points in the 2dimensional plane.

• A uniform transmission range R is defined.

• A node receives a transmission from another node, if and only if, its distance is lower than R.

• There are no losses.

The same model is applied for instance for simulations in section 4.

Furthermore, in some calculation, we also make the following approximation: Assumption (approximation) A3: we equate distance to number of hops (e.g. a node at distance between R and 2R from another node, is assumed to be at 2 hops).

The assumption is valid asymptotically when the density converge towards infinity ; for a more detailed exploration of the exact relationship between number of hops and distance, see for instance [START_REF] Xiaoyuan | On the Probability of K-hop Connection in Wireless Sensor Networks[END_REF].

Basic principles of 3-hop node coloring

In SERENA, any node u proceeds as follows to color itself:

1. Node u characterizes the set N (u) of nodes that cannot have the same color as itself. The set N (u) is the set of neighbors up to 3-hop from u in 3-hop node coloring.

2. Node u computes its priority, denoted priority(u). This priority consists of two components: the most important one is denoted prio(u). It can be equal to the number of nodes up to 2-hop (resp. 3-hop) from u. We will see later the exact value taken in OSER-ENA. The second component of priority(u) denotes the address of the node. By definition, node u is said to have a priority higher than node v if and only if:

• either prio(u) > prio(v); • or prio(u) = prio(v)
and address(u) < address(v).

3. Node u applies the two following rules:

• Rule R1: Node u colors itself if and only if it has a priority strictly higher than any uncolored node in N (u).

• Rule R2: To color itself, node u takes the smallest color unused in N (u).

Motivations and optimization principles

This distributed coloring algorithm proceeds by iterations or rounds, where nodes exchange their Color message. In its simplest implementation, the Color message would include the address, the priority and the color of 1) the node u itself, 2) its 1-hop neighbors in N (u), as well as 3) its 2-hop neighbors in N (u). The data locally maintained by any wireless sensor would include these data as well as the priority and color of any neighbor up to 3-hop. It is well known that the average number of nodes in the neighborhood up to 2-hop is equal to 4 • density, where density stands for the average number of nodes in the disk of radius R, where R is the transmission range. Such an overhead can be unacceptable for wireless sensors with limited storage and processing capabilities as well as low residual energy. Dense networks with limited bandwidth, low energy and a short MAC frame size become challenging for a coloring algorithm. That is why, we propose in this paper an optimization of the coloring algorithm reducing the size of Color messages exchanged and the size of data structures maintained, while keeping a low complexity. We also show that this overhead reduction does not increase the convergence time of the coloring algorithm. The optimization principles are based on the following remarks:

• It is necessary that any node u knows the highest priority taken by its uncolored neighbors up to 3-hop in order to apply Rule R1. Furthermore, node u must send information concerning itself, its 1-hop and 2-hop neighbors to let its one-hop neighbors know information about their 1-hop, 2hop and 3-hop neighbors. Hence, node u must send its priority, the highest priority taken by its uncolored 1-hop neighbors as well as the highest priority taken by its uncolored 2-hop neighbors.

However, sending only one highest priority of the uncolored 1-hop or 2-hop neighbors would delay the coloring since the information update will be slow. This would not suffice to color any wireless network with the same number of rounds as SER-ENA. Indeed, node v, 2-hop away from node u colored at round r would not know at round r + 2 that it has the highest priority. Hence, MORE THAN ONE highest priority at respectively 1-hop and 2-hop must be maintained and sent, unlike the version briefly presented in [START_REF] Mahfoudh | Node Coloring and Color Conflict Detection in Wireless Sensor Networks[END_REF]. We will wee in Section 3.3 how to compute the near optimal number of priorities to maintain at one-hop and twohop respectively. Notice that the highest priority at 3-hop is locally computed and not sent.

• Similarly for the color, node u must know the colors already used in its neighborhood up to 3-hop. However, it does not matter u to know which node up to 3-hop has which color, but only which colors are taken at 1-hop, 2-hop and 3-hop respectively.

That is why, we use the fields color bitmap1, color bitmap2 and color bitmap3 for the bitmaps of colors used at 1-hop, 2-hop and 3-hop respectively.

OSERENA: Optimized coloring algorithm

The Color message

From simulation feedback, we have noticed that the assignment of prio(u) =number of neighbors up to 2 hops outperforms the assignment prio(u) =number of neighbors up to 3 hops from u, or a random assignment. However, as OSERENA avoids the expensive computation of the list of neighbors up to 2 hops, OSERENA defines for any node u, prio(u) as the number of its neighbors + the sum of the number of 1-hop neighbors of its 1-hop neighbors. This computation is done during the initialization of the coloring algorithm. We also define max prio1(u) as:

• the four highest priorities of the uncolored 1-hop neighbors of u, if four such nodes exist;

• the priority of the only three (respectively two, respectively one) uncolored 1-hop neighbor, if only three (respectively two, respectively one) such nodes exist;

• empty, denoted ∅, if none exists.

We then have the following notation:

max prio1(u) = Max4 v uncolored∈1hop(u) priority(v).
Similarly, we define max prio2(u) as the three highest priorities of the uncolored 1-hop neighbors of the 1-hop neighbors of u, if they exist. We then have:

max prio2(u) = Max3 v∈1hop(u) max prio1(v).
The variable max prio3(u) is defined as the highest priority of the uncolored 1-hop neighbors of the 1hop neighbors of the 1-hop neighbors of u. We get:

max prio3(u) = Max v∈1hop(u) max prio2(v).
The computation of max prio1(u), max prio2(u) and max prio3(u) is done from the Color messages received during the current round. The values computed for max prio1(u) and max prio2(u) are inserted in the Color message sent by node u.

It follows that the Color message sent by any node u contains priority(u), max prio1(u) and max prio2(u), as well as the color of u, the bitmap of colors used at 1-hop from u, denoted bitmap1(u) and the bitmap of colors used at 2-hop from u, denoted bitmap2(u).

Processing

With the optimization, Rules R1 and R2 become:

Rule R'1: Any node u colors itself if and only if: priority(u) = max(max prio1(u), max prio2(u), max prio3(u)). (eq.1)

Rule R'2: When a node u selects its color, it selects the smallest color unused in color bitmap1(u) ∪ color bitmap2(u) ∪ color bitmap3(u).

Notice that this color should also not be used by heard nodes (nodes with which there is no symmetric link). This, in order to avoid color conflicts.

The aim of rules R3 and R4 is to improve convergence time. Although the Color message does not contain the whole list of colored 2-hop neighbors, a node processing this message can deduce the recently colored nodes and stores them in a local data structure denoted implicit node colored list whose size is equal to implicit node colored size. As we will see later, the storage of this list decreases the coloring time. To build this list, any node u proceeds as follows:

Rule R3: When a node u receives the Color message from any neighbor node v it compares the current value of max prio1(v) (respectively max prio2(v)) with the previous one sent by v, denoted previous max prio1(v) (respectively previous max prio2(v)).

Any priority value of previous max prio1(v) (respectively previous max prio2(v)) higher than the highest value of max prio1(v) (respectively max prio2(v)) corresponds to a recently colored node. This node is then inserted in the set implict node colored list.

Rule R4: When a node computes max prio1, max prio2 and max prio3 from the values received in the Color messages, it proceeds as follows:

• in the computation of max prio1, it discards any priority value corresponding to an already colored node (that is a node that belongs to the list implicit node colored list).

• in the computation of max prio2, it discards for any sender v, any priority value p corresponding to an already colored node received in max prio1(v) if and only if:

1. either p is the highest priority in max prio1(v), 2. or p is the second highest priority in max prio1(v) and (the third or fourth highest priority in max prio1(v) is equal to ∅), 3. or p is the third highest priority in max prio1(v) and (the fourth highest priority in max prio1(v) is equal to ∅).

• in the computation of max prio3, it discards for any neighbor v, any priority value corresponding to an already colored node received in max prio2(v) if and only if it is the highest or the second highest priority in max prio2(v).

The motivation of this rule is that a node u can receive information about a node v from a neighbor w such that the distance between v and w is greater than the distance between v and u. Consequently, node w can send node v as an uncolored node while u knows that this node is colored. In such a case, if u considers this information from v and it sends it to its neighbors, coloring will be delayed because the node to be colored after w will think this latter is uncolored and so does not color itself. However, using the list implicit node colored list, u will discard the node w and does not propagate an out-of-date information which helps to speed up the coloring convergence time. However, not any colored node can be discarded from max prio1 or max prio2. Indeed, let us consider a node u that discards the 4 values sent in max prio1(v). In some configurations, u might think it is the node having the highest priority among its 3 hop neighbors, although v would have sent a priority higher than priority(u) if it could send more than 4 values in a max prio1 it sends.

That is why, we adopted the Rule 4. A node can be discarded from max prio1 or max prio2 if there is still at least one priority that may be equal to ∅.

Rule R5 is related to the termination rule of the coloring algorithm.

Rule R5: Any node u stops sending its Color message as soon as it is colored, max prio1(u) = ∅ and it has received from all its 1-hop neighbors v a Color message with max prio1(v) = max prio2(v) = ∅.

Rule R6 has been introduced to tolerate message losses and link failures.

Rule R6: If at a round r > 1 of the coloring algorithm, any node u does not receive a message from its 1-hop neighbor v, it uses the information received from v at round r -1. After n successive rounds, with n 2 without receiving a Color message from v, v is no longer considered as a 1-hop neighbor of node u.

Properties of OSERENA

Correctness of OSERENA coloring

In this section we prove that in a wireless environment assuming hypothesis A0, A1 and A2, OSER-ENA provides a valid 3-hop node coloring avoid-ing collisions. Furthermore, we prove that this algorithm ends when all nodes are colored.

Lemma 1. With OSERENA, any node u colors itself if and only if it has the highest priority among all the uncolored nodes in N (u).

Proof.

Let us show that if any node u is coloring itself, then it has the highest priority among the uncolored nodes up to 3-hop. By Rule R'1, if u is coloring itself then priority(u) = max(max prio1(u), max prio2(u), max prio3(u)) (eq.1). From (eq.1), we get priority(u) max(max prio1(u)).

Hence, no uncolored one-hop neighbor has a priority higher than u. From (eq.1), we get priority(u) max(max prio2(u)). Hence, no uncolored two-hop neighbor has a priority higher than u, otherwise we would have the following contradiction: priority(u) max(max prio2(u)) > priority(u). From (eq.1), we get priority(u) max prio3(u). Hence, no uncolored three-hop neighbor in N (u) has a priority higher than u, otherwise we would have the following contradiction: priority(u) max prio3(u) > priority(u). Hence, node u has the highest priority among the uncolored nodes in N (u).

Conversely, if node u has the highest priority among its uncolored neighbors up to 3-hop, it means that:

• all its uncolored one-hop neighbors have a smaller priority. Hence, for any v uncolored one-hop neighbor of u, we have priority(v) < priority(u).

Hence, max(max prio1(u)) = max v∈1hop(u) (priority(v) f or v uncolored ) < priority(u);

• all its uncolored two-hop neighbors have a smaller priority. Let us consider the highest priority in max prio2(u). It denotes the highest priority of an uncolored node w that is one-hop neighbor of v, itself one-hop neighbor of u. Consequently, we have the following cases:

• node w is the node u itself and has priority priority(u);

• node w is a one-hop or two-hop neighbor of node u. In which case, we have by assumption: priority(w) < priority(u).

Hence, max(max prio2(u)) = priority(u).

• and all its uncolored three-hop neighbors in N (u) have a smaller priority. By definition, max prio3(u) is the maximum priority of uncolored nodes q that are one-hop neighbors of w, itself one-hop neighbor of v, one-hop neighbor of u. Consequently, we have the following cases:

• node q is the node u itself and has priority priority(u);

• node q is a one-hop, two-hop or three-hop neighbor of node u. In which case, we have by assumption: priority(q) < priority(u).

Hence, max prio3(u) = priority(u).

Finally, priority(u) = max(max prio1(u), max prio2(u), max prio3(u)). Hence, node u is coloring itself with OSERENA.

Lemma 2. With OSERENA, when node u colors itself, it knows all the colors taken in N (u) with a higher priority. Proof. The exchange of Color messages allows any node u to know any uncolored node in N (u) having a higher priority than itself. Node u also knows the colors of already colored nodes in N (u) by means of bitmap1, bitmap2 and bitmap3. Thus, when u colors itself, it takes the smallest color unused in these bitmaps, and hence unused in N (u). Lemma 3. OSERENA coloring ends when all nodes are colored. Proof. If u is colored and max prio1(u) = ∅, then node u and all its one-hop neighbors are colored. Moreover, if node u receives a Color message from any one-hop neighbor v with max prio1(v) = max prio2(v) = ∅, it means that all the one-hop neighbors of v and all the one-hop neighbors of its one-hop neighbors are already colored. Hence, all nodes up to three-hop from u and belonging to N (u) are colored. The coloring algorithm ends when node u as well as all its 1-hop, 2-hop and 3hop neighbors are colored.

Lemma 4. In a wireless network meeting assumptions A0, A1 and A2 and in the absence of message loss and node failure, all nodes color themselves with OSERENA and stop sending their Color message.

Proof. Let us consider any node u. The nodes in N (u) color themselves according to their priority. As soon as u becomes the uncolored node with the highest priority, it colors itself according to rules R'1 and R'2. According to rule R5, as soon as u is colored and max prio1(u) = ∅, then node u and all its one-hop neighbors are colored. Moreover, if node u receives a Color message from any one-hop neighbor v with max prio1(v) = max prio2(v) = ∅, it means that all the one-hop neighbors of v and all the one-hop neighbors of its one-hop neighbors are already colored. Hence, all nodes up to three-hop from u and belonging to N (u) are colored. Hence, it is useless for u to send its Color message insofar as any information contained in its message is already known by its one-hop, two-hop and three-hop neighbors in N (u) and these nodes are already colored.

Property 1 OSERENA provides a valid 3-hop node coloring in any ideal wireless environment.

Proof. For three-hop coloring, for any node u, the set N (u) contains by definition all nodes up to 3hop from u, assuming an ideal environment. From Lemma 1, with three-hop coloring, any node u can color itself if and only if no uncolored node in N (u) has a priority higher than u. According to rule R'1, priority of node u meets (eq.1). Moreover, since no two nodes have the same priority, we cannot have a simultaneous coloring of two nodes up to 3-hop away each other. According to Lemma 2, when coloring itself, any node u knows all the colors taken by nodes in its N (u), so it selects the smallest color according to rule R'2. Consequently, assuming an ideal wireless environment, no 2 nodes within 3-hop neighborhood from each other takes the same color. Which means that OSERENA provides a valid coloring. With this coloring, nodes that belong to N (u) cannot create a collision with data sent by u or an acknowledgement sent to u.

Property 2 A failure to receive a Color message from a one-hop neighbor induces an additional latency in network coloring and does not compromise the validity of coloring with OSERENA.

Proof. Deduced from rule R6.

Equivalence of OSERENA to a centralized algorithm

In this section, we compare the behavior of OS-ERENA with the well-known centralized First Fit 3-hop node coloring [START_REF] Cargiannis | A tight bound for online coloring of disk graphs[END_REF]. More precisely, we compare the colors granted to nodes by both coloring algorithms. With centralized First Fit 3-hop node coloring, nodes are sorted according to their priority and are colored in that order. Any node u receives the smallest unused color in N (u).

Lemma 5. For any node u, for any given priority assignment, nodes ∈ N (u) color themselves in the same order with OSERENA and First Fit.

Proof. Let us consider any node u that is coloring itself in OSERENA, we have:

• any node v ∈ N (u) such that priority(v) > priority(u) is already colored in OSERENA, otherwise u could not color itself now;

• any node v ∈ N (u) such that priority(v) < priority(u) is not colored in OSERENA, because it is constrained by node u that is not yet colored.

Hence, in N (u) the coloring order in OSERENA is compliant with the priority order that is by definition followed by First Fit. In conclusion, both coloring algorithms follow the priority order to color nodes in a given neighborhood N (u).

Property 3 For any topology, OSERENA provides the same coloring as a centralized First Fit 3-hop node coloring algorithm using the same priority assignment.

Proof. For any topology, for any node u in this topology, the color of u is determined by the colors already used in N (u) when u colors itself. According to Lemma 5, all nodes in N (u) color themselves in the same order with OSERENA and First Fit. Let u 1 be the first node that colors itself in N (u). It takes the smallest available color in N (u 1 ). Let u 2 be the the first node that colors itself in N (u 1 ), and so on. After a finite number of iterations (at most equal to the number of nodes in the topology), we get a node u k+1 the first node that colors itself in N (u k ) and has colored itself without being constrained by any other node in OSERENA: u k+1 has the highest priority in N (u k+1 ). This node takes the color 0 in OSERENA. With First Fit, since no node in N (u k+1 ) is already colored, u k+1 takes color 0. Nodes in N (u k+1 ) with a priority higher than or equal to priority(u k ) are colored according to their priority order with OSERENA and First Fit. Consequently, they receive the same colors. We apply the same reasoning to node u k and nodes in N (u k ) with a priority higher than or equal to priority(u k-1 ), going back up to node u 1 and finally node u that receives the same color with OSERENA and First Fit, because the same colors are already assigned in N (u).

Reduced overhead

In this section, we show how OSERENA reduces the overhead both in terms of 1) bandwidth by reducing message number and message size and 2) node storage by decreasing the size of data maintained at each node.

OSERENA does not require to send or to maintain the 2-hop neighborhood of a node, as shown in Section 2.4.1. The use of max prio1 and max prio2 reduces the size of Color messages exchanged between neighbors. We now show how to determine the optimal size of max prio1 and max prio2.

Message size

Assuming the near optimal size of max prio1 and max prio2 determined later on (see Lemma 6), we can compute the maximum size of the message Color exchanged between neighbor nodes. Proof. This is deduced from the Color message format, where the 8 factor comes the maximum size of priority + max prio1 + max prio2.

Constraints for the computation of max prio1 and max prio2 sizes

We first notice that the reduction of message size must not imply a higher number of rounds to color the network. Hence, the optimal size of max prio1 and max prio2 is a trade-off between bandwidth consumption and convergence time of the coloring algorithm.

The simplest solution would be to maintain only one priority for max prio1 and max prio2. However, this solution does not allow to remove already colored nodes in the computation of max prio1, max prio2 and max prio3. Hence, a coloring that is much slower than SERENA. That is why, several priorities are maintained in max prio1 and max prio2. The question is how many? To be able to discard one value corresponding to an already colored node and sent by neighbor v in max prio2(v) implies that v sends at least 2 values in max prio2(v). To be able to compute its 2 highest values in max prio2(v) and discard one value, node u must receive at least 3 values in max prio1(u). Hence, the minimum sizes are Size max prio1 = 3 and Size max prio2 = 2.

Unfortunately, we can still exhibit scenarios with this minimum setting, where only the first address in max prio2 is discarded if already colored, producing a number of rounds higher than SERENA. In simulations, we identified a scenario with 100 nodes uniformly distributed with a density of 20 need 175 rounds to color themselves with OSERENA instead of 134 rounds with SERENA. That is why, we select Size max prio1 = 4 and Size max prio2 = 3.

Computation of the optimal size of max prio1 and max prio2

In this section, we assume the unit disk graph model of section 2.1.2 (including Assumption A3).

Recall that in OSERENA, any node u receiving a Color message from one neighbor v, can have fresher information than v. That is, v believes that node w is not yet colored and so, keeps it in max prio1(v) or max prio2(v) it sends, whereas u knows that w is already colored because it it closer to w than v. In such a case, OSERENA allows u to ignore w when computing max prio1(u) by usage of the list implicit node colored list as explained in section 2.4.2. However, to keep the correctness of the algorithm, the node u cannot always ignore the colored node w when computing max prio2(u) and max prio3(u) (see the coloring rule R3). If node u that is the next node to be colored after w, is not allowed to ignore w already colored, u will not color itself and will wait until node v removes node w. Hence, node u in OSERENA colors itself later than it would do in SERENA. Lemma 6. With the setting Size max prio1 = 4 and Size max prio2 = 3 and rules R3 and R4, OSER-ENA colors any node u in the same round as SER-ENA, except when three nodes two-hop away from u, but 4-hop away from each other are coloring simultaneously just before u. Proof. We first identify this scenario and then compute its probability in the next section. When three nodes two-hop away from u, but 4-hop away from each other are coloring simultaneously just before u, node u is not allowed by rule R3 to discard the three of them in the received max prio2(v), hence the coloring of node u is delayed. We can show that this scenario is the only one that will delay u coloring. On the one hand, two one-hop neighbors of u are not allowed to color simultaneously, because they are at most two-hop away. On the other hand, a one-hop and a two-hop neighbor of u are not allowed to color simultaneously, because they are at most three-hop away. It results that the only case of simultaneous colorings in N (u) involves nodes that are 2-hop away from u and 4-hop away from each other.

Lemma 7. The setting Size max prio1 = 5 and Size max prio2 = 4 provides the same number of rounds as SERENA.

Proof. With the setting, Size max prio1 = 5 and Size max prio2 = 4, it is no longer possible to have a bad scenario where four nodes two-hop away from u, but 4-hop away from each other are coloring simultaneously. We prove it by contradiction. Let u be any node. We assume that the four nodes v 1 , v 2 , v 3 and v 4 that are 4-hop away from each other and 2-hop away from u are coloring themselves simultaneously. We notice that the distance between these four nodes is maximized when they belong to the circle centered at u and of radius 2R and are diametrally opposed. We can compute the distance of two adjacent points denoted v 1 and v 2 , we then have

d(v 1 , v 2 ) 2 = d(v 1 , u) 2 + d(u, v 2 ) 2 = 4R 2 + 4R 2 = 8R 2 . Hence d(v 1 , v 2 ) = 2 √ 2R < 3R: this contradicts our assumption.
That is why in the following of this paper, we take Size max prio1 = 4 and Size max prio2 = 3 leading to a smaller bandwidth use.

Convergence time

As shown in the previous section, the selected setting of the size of max prio1 and max prio2 provides the same number of rounds as SERENA, except when the bad scenario occurs. In the bad scenario, the coloring of a node is delayed in OSER-ENA. Notice that even in this case, the total number of rounds required by OSERENA can still be equal to the total number of rounds required by SERENA. The occurrence of the bad scenario is a necessary but not sufficient condition to increase the number of rounds with OSERENA.

To conclude, the scenario where one OSERENA node u is colored with a delay compared to SER-ENA happens if the following events occur:

• E 1 : ∃ v 1 , v 2 and v 3 , three nodes that are 2-hop away from u and 4-hop away from each other.

• E 2 : these three nodes v 1 , v 2 and v 3 have a priority higher than u.

• E 3 : v 1 , v 2 and v 3 are colored simultaneously.

We assume the unit disk graph model of section 2.1.2, including Assumption A3. We adopt the following notations. Let d(u, v) denote the euclidian distance between nodes u and v. Let P denote the probability that the bad scenario occurs. We want to estimate an upper bound of this probability. Let P i denote the probability that the event E i occurs, with i ∈ [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF][START_REF] Mccormick | Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem[END_REF]. We have: P = P 1 • P 2 • P 3 . For any node u, let D(u, R), (respectively C (u, R)), denote the disk (respectively the circle) centered at u of radius R. Let A \ B denote the set containing exactly the elements of A but not those of B. The computation of upper bounds of probabilities P 1 and P 2 is done geometrically. On Figure 1, a bound of P 1 corresponds to the probability for v 3 to belong to the hatched area. The computation of the probability P 1 is illustrated in figure 2. Nodes v i , for i ∈ [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF][START_REF] Mccormick | Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem[END_REF], should belong to D(u, 2R) \ D(u, R) and should be at a distance belonging to (3R, 4R] from each other. To maximize the number of possible nodes v 3 , we take v 1 ∈ C (u, 2R). The choice of v 1 done, we increase the number of possible nodes v 3 by taking v 2 ∈ C (u, 2R) ∩ C (v 1 , 3R), approximating 3R + ε by 3R. We make v 1 and v 2 closer increasing again the possibilities for v 3 by transforming the triangle (v 1 , u, v 2 ) in a right triangle. We then have d(v 1 , v 2 ) = 2R √ 2 computed as the hypotenuse in the triangle (u, v 1 , v 2 ). We now select v 3 that belongs to We compute S P the surface of this area. S P S D -2S T -S C , where S D is the surface of the disk quarter D(u, 2R), S T is the surface of the triangle formed by s, u and v 3 and S C the surface of the square (s, s 1 , u, s 2 ) whose diagonal is y (see figure 1). We first compute d(u, q) in the right triangle (u, q, v 3 ). We get 2R 2 + d(u, q) 2 = 2 2 R 2 . Hence, d(u, q) = R √ 2. In the isocel triangle (v 1 , v 2 , s), we compute d(q,t. We have: (d(s,t)) 2 + 2R 2 = 8R 2 . Since d(s,t) = d(s, u) + d(u, q), we get d(s, u) = d(s,t)d(u, q) = ( √ 6 -√ 2)R. We then get:

D(u, 2R)\ D(u, R)\ D(v 1 , 2R √ 2)\ D(v 2 , 2R √
S D = ΠR 2 and S C = y 2 /2 = (4 -2 √ 3)R 2 . S T = ( 4 -2 √ 3 -2 + √ 3)R 2 .
We deduce S P = (Π -2 4 -2 √ 3)R 2 . Hence, P 1 = number o f f avorable cases number o f possible cases = S P 4ΠR 2 . Finally, we get

P 1 = 1 4 - √ 4-2 √ 3 2Π
.

Estimation of an upper bound of P 2

For any node u, let us compute P 2 the probability of event E 2 : there exists three nodes two-hop away from u with a priority higher than u. This event E 2 can be considered as the intersection of two events E 21 and E 22 , where E 21 means that there exists three nodes in D(u, 2R) with a priority higher than u. Event E 22 means that three nodes in D(u, 2R) do not belong to D(u, R). We do not have event E 2 1 if and only if in D(u, 2R), 1) u has the highest probability, or 2) u has the second highest probability or 3) u has the third highest probability. Let M denote the number of nodes that are exactly one-hop away from u. The average number of nodes in D(u, 2R) is equal to 4M + 1. We compute P 21 the probability of event E 21 . We have P 21 = 1 -3 4M+1 . We can now compute P 22 the probability of event E 22 . We get P 22 =probability that none of these three nodes in D(u, 2R) belong to D(u, R). Since the nodes are independent, we get P 22 = (1 -ΠR 2 4ΠR 2 ) 3 = (3/4) 3 . Since events E 21 and events E 22 are independent, we get P 2 = P 21 • P 22 , leading to P 2 = 27 64 (1 -3 4M+1 ).

Estimation of an upper bound of P 3

For any node u, we select the last three nodes v 1 , v 2 and v 3 , two-hop away from u that color themselves just before u. We want to compute P 3 the probability that event E 3 occurs that is: these three nodes color themselves simultaneously. We can bound P 3 by 1.

Upper bound for P

Property 5 The probability of occurrence of the bad scenario is upper bounded by 27 64 (1

-3 4M+1 ) • ( 1 4 - √ 4-2 √ 3 2Π
).

Proof. Since P ∏ 3 i=1 P i , we get

P 27 64 (1 - 3 4M+1 ) • ( 1 4 - √ 4-2 √ 3 2Π
).

Noticing that (1 -3 4M+1 ) 1, a numeric evaluation of the bound yields: P 0.0564

Performance evaluation by simulation

We now evaluate the performance of OSERENA by simulation for various WSNs.

Simulation modules and parameters

We consider various wireless network configurations, with the unit disk model, where the number of nodes varies from 50 to 200 and the average number of neighbors per node, called density, varies from 8 to 45. We check the connectivity of all the topologies generated by our random topology generator. Three modules are simulated:

• The Neighborhood Discovery Module in charge of detecting the creation of new links, testing their symmetry and detecting their breakdown. This is done by means of periodic exchanges of Hello messages. The Hello message contains the list of addresses of heard/symmetric nodes.

• The OSERENA Module in charge of coloring the wireless network, once topology is stabilized.

• The SERENA used as a reference for a comparative performance evaluation.

We evaluate the number of colors used, the number of rounds needed to color the whole network, the average number of Color messages sent per node as well as the average size of these messages. Each result is the average of 10 to 50 simulations.

Performance results of OSERENA

In this series of simulations, we fix the number of nodes in the interval [50, 200] and vary the node density from 8 to 45. We evaluate the performance criteria of OSERENA and then iterate on another number of nodes.

Number of colors

The main performance criterion of a coloring algorithm is the number of colors needed to color the whole network. This number depends on network topology. First, we want to evaluate the impact of node density and node number on the number of colors used by OSERENA. The figure 3 shows that the number of colors strongly depends on the density of the graphs, and much less on the number of nodes. Intuitively, the reason is that the color selected by a node, depends only on its 3-hop neighborhood, hence is related to the number of the 3-hop neighbors (which is itself directly proportional to density).

Furthermore, the size of the 3-hop neighborhood is not related to the number of nodes of the graph, hence this last parameter has less impact. This occurs until the transmission range becomes too large and the 3-hop neighborhood includes the whole network (as shown in the figure for a number of nodes = 50 and for density 30, where increasing density for a fixed number of nodes is equivalent to increasing transmission range).

Number of rounds

To measure the time complexity of OSERENA, we evaluate the number of rounds needed to color the whole network. More precisely, what is the impact of node density and node number on the number of rounds? In figure 4, we observe that the number of rounds depends more on the number of nodes in the network than on density.

There is one natural explanation on the observation that the number of nodes has an impact on the number of rounds (and much less on the number of colors, see previous section): in OSERENA, every node u must wait until all the nodes in its N (u) having a higher priority than itself color themselves. Recursively, each node in this set should do the same. This is likely to lead to waiting "chains", and such chains are longer in larger networks. It contributes to increase coloring delay.

Number of messages sent per node

To compute the overhead induced by OSERENA, we first evaluate the average number of messages sent per node for various network configurations, pointing out the influence of node density and node number. As illustrated in figure 5, the average number of messages is close to the number of rounds (in figure 4). This is expected since every node sends one message per round until a stopping condition is fullfilled (rule R5): in the simulations, for most nodes, most of the time, rule R5 is not verified.

Number of bytes sent per node

Another expression of the message overhead is given by the average number of bytes sent per node for various network configurations. What is the impact of node density and node number on the number of bytes exchanged during the coloring? From the figure 6, the number of nodes has barely noticeable impact on the average number of bytes sent per nodes, whereas density has a limited, but direct impact. This is a direct consequence of the structure of the Color message, which includes 2 bitmaps of colors of the 1-hop and 2-hop neighborhood, which increases linearily with density (e.g. 2 additional bits in message, per additional color in the 3-hop neighborhood).

Comparison with SERENA

We now compare the performances obtained by OS-ERENA with those of SERENA. OSERENA ensures that nodes should get the same colors as with SERENA. The open question is at which expense?

Number of colors

Simulation results are compliant with the expected behavior of OSERENA: any node receives the same color with SERENA and OSERENA.

Number of rounds

Simulation results show that even if the bad scenario occurs, OSERENA needs the same number of rounds as SERENA in all the network topologies tested. Comparing figure 6 and figure 7 we observe that the number of rounds is equivalent. The reason is that the event where OSERENA requires more rounds than SERENA on one node has low probability (see section 3.4.4) ; and then, the occurence of one such event does not automatically increase the total number of rounds for the coloring of the whole network.

Number of messages sent per node

Simulation results show that the average number of messages sent per node is comparable with SER-ENA and OSERENA for various network configurations. This is a consequence of the previous result. The figure 9 illustrates the major contribution of OSERENA compared SERENA: the size of the Color messages is much smaller.

In SERENA, a Color message includes information for each node in its entire 3-hop neighborhood (address, priority, color): several bytes per node in the 3-hop neighborhood. In OSERENA, only a small fixed subset of priorities and addresses of these nodes are exchanged, and only 2 bits per color are required.

Notice that for wireless sensor networks based on 802.15.4, the maximum packet size is 127 bytes, hence SERENA messages are problematic even at the lowest density (and would have probably to be fragmented in several packets), whereas on contrary, OSERENA fits within this limit until high densities.

Conclusion

Coloring algorithms have been introduced in WSNs to allow sensor nodes to save energy and bandwidth. Collisions are avoided and nodes can sleep when they are neither sender nor receiver of the transmitted messages. However, their use in dense WSNs is possible only if they are optimized to support such networks. Indeed, the resource constrained nature of sensors combined with the possible high number of neighbors is a real challenge for the design of bandwidth and energy efficient protocols. That is why we have proposed OSERENA, whose performance evaluation results confirm that the WSN is colored with the almost the same number of rounds and exactly the same number of colors as its unoptimized version, but with a message size that does not depend on network density. Consequently, OSERENA enables considerable gains in bandwidth and energy consumption.

Property 4

 4 With the setting Size max prio1 = 4 and Size max prio2 = 3, OSERENA uses a Color message whose size is at most 8 • (size address + size prio) + size color + size bitmap1 + size bitmap2 bytes.

Fig. 1 . 1 Fig. 2 .

 112 Fig. 1. Possible zone for node v 3 .

  2), corresponding to the hatched area depicted in Figure 1.

Fig. 3 .

 3 Fig. 3. Number of colors.

Fig. 4 .

 4 Fig. 4. Number of rounds.

Fig. 5 .

 5 Fig. 5. Average number of messages sent per node.

Fig. 6 .

 6 Fig. 6. Average number of bytes sent per node.

Fig. 7 .

 7 Fig. 7. Number of rounds for SERENA.

Fig. 8 .

 8 Fig. 8. Average number of messages sent per node with SERENA and OSERENA.

4. 3 . 4 .

 34 Figure 9 depicts the average number of bytes sent per node with SERENA and OSERENA. It points out the benefit brought by the optimization of OS-ERENA.

Fig. 9 .

 9 Fig. 9. Average number of bytes sent per node with SER-ENA and OSERENA.


Cyprien Awono
email: cyprien.awono@usherbrooke.ca

Gredi

Catherine Laroche Dupraz

Dominique Vermersch

Consumer willingness to pay for attributes of west-African poultry: using the microeconometrics of implicit price

Keywords: West Africa, attributes, poultry, marginal willingness to pay, implicit price. JEL codes: C5, D12, Q18

Consumer concerns in food purchasing contain a number of attributes, including the nutritional and sanitary values, conditions of breeding and selling, and other social issues. The purpose of this paper is to introduce an analytical and an empirical approaches to estimating the marginal willingness to pay (WTP) for chicken attributes in Cameroon using data from an investigation on the field. First we constructed a theoretical model of implicit price. Secondly, we assumed that WTP for chicken attributes can be derived from estimate hedonic function, there by expressing the prices consumers are willing to pay as function of implicit price of each chicken attributes. Two models are proposed and discussed. Our findings indicate that in spite of the possibility of bargaining the price of the local flesh chicken, consumer's substituted it by imported frozen cut chicken which main attributes are low cost, sold in separated parts and available in all urban markets.

Introduction

This paper is written in a context where, since 1995, the Cameroonian flesh chicken production of is strongly competed by the low prices of imported frozen cut chicken coming from Europe or Brazil [START_REF] Awono | Les déterminants microéconomiques de la consommation urbaine de poulets dans les pays du sud : Cas du Cameroun et d'Haïti[END_REF]. This movement was accompanied by a strong fall of chicken prices, causing collapse of many local poultry farms. The situation was reported and condemned by the local actors and international non governmental organisations. An empirical analysis of the urban chicken consumption in Cameroun seems to indicate that it is over-simplistic to consider chicken as a homogeneous product, insofar as imported frozen cut chicken targets different consumers and it doesn't compete with local markets [START_REF] Awono | Les déterminants microéconomiques de la consommation urbaine de poulets dans les pays du sud : Cas du Cameroun et d'Haïti[END_REF][START_REF] Awono | Les déterminants microéconomiques de la consommation urbaine de poulets dans les pays du sud : Cas du Cameroun et d'Haïti[END_REF]. Though both types of chickens bring some meat, sources of calories and proteins to the consumers, other attributes of consumption differentiate in their eyes. However, the analysis of satisfaction of food needs of developing countries population traditionally limits itself to the analysis of the total offer and it often forgets the differentiation of products.

In what follows, we first investigate on the field to identify and studying factors consumers' perception for specific attributes will influencing prices in Cameroon. Next, we constructed a theoretical model of willingness to pay (or hedonic price) by taken in account the traditional or informal market (qualified as imperfect) of Cameroon to interpret our findings: so, we assumed the segmentation of markets and the consumer never has the perfect information concerning attributes of chicken sold. Contrary to develop countries, prices are not posted, consumer has to bargain the price every time, place of sale can influenced the price of chicken and other socio-economics characteristics or attributes can always influenced the choice and the price of the chicken. This model also takes in account the purchasing power of consumers in local market. At last, with available data collected, we measured the marginal willingness to pay by applying the hedonic method based on intrinsic and extrinsic attributes of chicken. The remaining text is subdivided into four sections in addition to the present introduction. In section 2, we present the data collected, and then we developed the analytical method. Section 3 is devoted to the implementation of an econometric method as well as results obtained. Finally in section 4, we conclude and give implications of the paper.

Materials and methods

Source of data

In order to studying relevant characteristics or attributes of chicken as it is perceived by consumers, a specific survey1 was conducted in two steps in Yaoundé, the capital of West African nation of Cameroon. The first one was a qualitative exploratory survey to categorize chicken sold, consumers and to assume the segmentation of the local markets. After this first stage, formal questionnaire related mainly to chicken consumption was written and applied. During the period May and July 2005, 180 households in Yaoundé were sampled using the quota method (read GRAIS, 2003;[START_REF] Ardilly | Les techniques de sondage[END_REF]GROSBRAS, 1987), in other to obtain great variation in term of socio-cultural backgrounds (principal activity, standard of living, level of study, age...). Contrary to the classic approach which would want that the data are only collected on the attributes of the product, we proposed in an informal market to take into account perceived attributes for which consumer are willing to pay connected to the salesmen and to the buyers: the intrinsic attributes. This is why data were collected considering, extrinsic attributes such as price, practice for cooking (sold in parts), alive (sold by judged), terms of sale (possibility of bargaining, adjournment of payment or handing-over) 2 , availability every time and intrinsic attributes such as symbolic value of local chicken (useful for formalities or traditional ceremonies), ethnicity, social report, conditions of breeding (buyer knows the origin of chicken) and taste. Indeed, it important to take into account other socio-economics attributes like age (assumed that possibility of bargaining can increase if the buyer is mature), principal activity (indicate the purchasing power), size of the family (indicate the number of mouth to be nourish) and level of study (indicate if the buyer can have information about the poultry). We assumed that these attributes can give us in our context, the implicit price of the chicken. Collected data are presented on table 1. According to the nature of available data, hedonic model was tested. This model gives the willingness to pay extrinsic and intrinsic attributes of local chicken or imported chicken.

Analytical method

A hedonic price model was used to determine the effect of various factors on price. A hedonic price function relates the price of a product (good or a service) to its various attributes or characteristics. [START_REF] Waugh | Quality factors influencing vegetable prices[END_REF] and later [START_REF] Lancaster | Consumer Demand: A New Approach[END_REF] made early attempts to related price to products characteristics. [START_REF] Rosen | Hedonic prices and implicit markets: product differentiation in pure competition[END_REF] and [START_REF] Lucas | Hedonic price functions[END_REF] advanced those ideas providing a theoretical framework for hedonic price analysis. The underlying hypothesis of such analysis is that the products have utility bearing attributes and that the values of those attributes contribute to the price of the product. The observed product price is therefore a composite of the implicit values of the product's attributes. In this paper, we assume the imperfection of local markets. Consumer doesn't have information about the product sold, the price is resulting from bargaining and consumer has possibility of handing-over. However, prices are not posted like in developed countries and the product is mostly sold alive and by "judged". This is why we suggest using in this context, characteristics of chicken as well criteria related to choice, the place of sale and to the buyer.

a) The basic model Assume that consumer's utility is given by:

Z H U U , ,
. Then Z is a composite commodity, is a vector of socioeconomics characteristics of consumer: age, income, family status, etc.., H is a vector of consumption of a differentiated good used in unit: it is chicken characterised by its attributes J i j x j ... , where

J x x H x H ,... 1 . Assume that the chicken price J x x P P ,... 1
is the marginal willingness to pay function or hedonic price of chicken. Under these assumptions, the preferences are weakly separable in consumption of chicken and its attributes. In other words,

Z x x U Z x x H U J J , ,... , , ,... , 1 1
(1) Let us simply assume that consumer can have an uninterrupted range of choice of characteristic and nothing his disposable income W . Her utility-maximisation is given by:

W Z x x P Z x x U Max J J Z x x J ,... , ,... , 1 1 , ... 1 (2)
The first-order condition for the price of attributes or in our context willingness to pay (WTP) attributes of chicken is given by:

J j w U U x P P j Z x j j j ... 1 (3)
2 The fact of knowing that one can negotiate the price or report the payment for another day is very important for households with very low income on the African markets Assume now that the hedonic price function j P has been estimated for the marginal willingness to pay for attribute j x . It is, in optimum, equal to the marginal rate of substitution between these characteristics and the composite good, it is also equal to the marginal willingness to pay of consumer j w . The consumer is assumed to be a price taker in the chicken market, that consumer can be viewed as facing an array of implicit marginal price schedules for various characteristics. Equation (3) shows that consumer maximizes utility by simultaneously moving along each marginal price schedule until she reaches a point where her marginal willingness to pay for an additional unit of that characteristic just equals the marginal implicit price of that characteristic. According to Freeman (1992), figure 1 shows the partial relationship between the hedonic price and j x . Figure 2 shows the marginal willingness to pay curves for two consumers, i and i , who have chosen utility maximizing bundles of chicken characteristics. Figure 2 represent the resolution of equation 3.

Figures 1 and 2 (According to Freeman, 1993)

According to [START_REF] Rosen | Hedonic prices and implicit markets: product differentiation in pure competition[END_REF], the behaviour of the consumer can again also be represented as a bidding function , , , W u x representing the willingness to pay for chicken's characteristics

j x x x x
,... 1 considering an income W and a level of utility u .This bidding function is defined implicitly by following equation:

W x x U j , ,... , 1 (4)
Marginal bidding,

j x
, is equal to the marginal rate of substitution

z x U U j defined before.
In a symmetrical way and as also represented it by Rosen before, the hedonic price of the chicken can be also interpreted as a bidding of offer.

b) The imperfection of the market Considering the marginal implicit price of characteristic j

x as the effective marginal willingness to pay of the consumer for this attribute is subject of controversy [START_REF] Freeman | Hedonic Prices, Property Values and Measuring Environmental Benefits: A Survey of the Issues[END_REF]Bonnieux and Desaigues, 1996). Even more so in our case, like in African market, consumers are not better informed about chicken attributes. Then, price-taker hypothesis is particularly arguable in Africa, notably as much as, during the purchase of poultry; the consumer and the seller are practically in a situation of bilateral monopoly: each participates in the building of price which results from bargaining. Finally, the resolution of equation ( 2) assumed an uninterrupted range of choice of attributes. And, in the reality of the Cameroonian market, the most part of attributes cover only a restricted range and drive to a discrete choice. In most cases, consumer is theoretically willing to pay more a lot a product likely to bring him the upper quantity of a particular attribute, but that such attribute is not available on the market. Figure 3 illustrates this scenario. Figure 3 shows the marginal implicit price function ... ... j j x P and estimated marginal willingness to pay functions for high income ' j w and low income j w . Then, the attribute j x being available only for

j j x x
. Beyond j x , the curve j P is cut-down in the point A : j x is the maximum quantity j x that the product is in measure to offer.

Figure 3 (According to Freeman, on 1993)

Another scenario (which is not symmetrical therefore to figure 3), illustrated in the figure 4, is when the marginal willingness to pay ij w of low income i is less than price j P . The absence of intersection between j P and ij w , point out that low income i can not obtain the main attribute j x . Then, if want any more to eat chicken which is the less expensive meat, he have

to buy a substitute chicken (imported) not introducing this attribute.

c) The segmentation of the market

According to Freeman (1992) and Straszheim, 1974, if market segmentation does exist like in Cameroon, separate hedonic price functions must be estimated for each segment; and imported chicken and local flesh chicken must be separately estimated for each segment with a different set of implicit prices.

Hedonic regression

Awono et al (2008), show that the market perhaps considered as segmented. In fact, between the flesh local chicken and the imported chicken, there are many place of sale (big traditional markets, outskirts markets, "fish shops"3 , small quarter shop) and scale of price (by judged, in kilogram or in separated part).

It is important to underline that acquired results (section 3) can not compared with others; for lack of similar studies in African markets. However, in he is article on consumer's preferences for the sheep and nanny goats in the south of Nigeria, Jabbar (1998) considers in its hedonic regression, price as dependent variable. He splits independent variables into two groups: on the one hand it considers ordinal variables to be co variables, numerical variables (the weight of the animals and the length of animal husbandry) and as mailmen, (sex, market, reason of sale). But as part of our study, it was difficult to implement the method of analysis of covariance (ANCOVA) used by Jabbar (read Gudajarati, on 2003) to determine the hedonic price of the chicken; for lack of covariables (we didn't measure weight and length of animal husbandry of the bought chicken). In so far, we did not insert in our model the weight of the chicken, which however participates unquestionably in the determination of the selling price. Unfortunately, it is not possible to know the weight of the chicken for every transaction, this last being principally sold by judged: any try of estimate of weight is perhaps very badly interpreted as well by the seller as even by the consumer. Moreover, the taking into account of the income of consumers would undoubtedly have been a very important explicative variable. But, the most part of the interviewees refused to specify their level of wage and / or remuneration, what restricted us in the simple knowledge of the marginal willingness to pay for the chicken attributes. This is why we considered the socio-professional category as an explicative variable, this one being linked at the level of remuneration of the interviewee. Ordinal variable indicating the level of study, on a scale from 1 à 4 180 : 1 = not made studies; 2 = primary Studies; 3 = secondary Studies and; 4 = Higher education.

2.4.

Preference for the local flesh chicken [PREFLOCAL] Instruments of the preference of local flesh chicken:

 At the time of ceremonies [PATC]  In households [PATF] 1 si, hors considération de prix, le poulet local est préféré par le consommateur et 0 sinon. 1 if, except consideration of price, the local flesh chicken is preferred by the consumer and 0 if not.

1 if the local flesh chicken is specifically consumed at the time of the particular ceremonies/occasions and 0 if not. 1 if the local flesh chicken is consumed in a usual way in the households and 0 if not.

The linear regression model can therefore be given by:

m j k kj j j z WTP 1 0 pour n i j ,..., , [5]
j estimates the marginal value of each characteristic. In this study, the hedonic regression was employed using the method of ordinary least squares (OLS) procedure of Eviews software for windows to estimates parameters.

Results

Several models were fitted to assess the effect of different factors on price of chicken attributes.

3.1.

Case of the imported frozen cut chicken The table 2 introduces the results of the hedonic regression for imported frozen cut chicken. Table2. Results of the hedonic regression for imported frozen cut chicken. Dependent variable: willingness to pay for imported frozen cut chicken attributes [ Like [START_REF] Jabbar | Buyer preference for sheep and goats in southern Nigeria: A hedonic price analysis[END_REF] and [START_REF] Dalton | A household hedonic model of rice traits: economic values from farmers in West Africa[END_REF] research on the hedonic prices of rice in West Africa, the significant variables call several interpretations:

-The variable [COST] is statically significant and positive; indicating that consumers are willing to pay imported frozen cut chicken as price is less than other product, such as in our case local flesh chicken.. -Practice for cooking [PRACT] is significant and positive, indicating that consumers are more likely to buy chicken made proportional, sold in parts and therefore ready for cooking dishes. -Proximity of the place of sale is significant and negative [PROXI], this means that the consent to pay cutting chicken in nearness markets of household is weaker than in the more distant markets. Survey carried out on the field [START_REF] Awono | Déterminants de la consommation urbaine de poulet de chair au Cameroun : Cas de la ville de Yaoundé[END_REF][START_REF] Awono | Les déterminants microéconomiques de la consommation urbaine de poulets dans les pays du sud : Cas du Cameroun et d'Haïti[END_REF] in Yaoundé proving that the distance of the markets where chicken are sold, is not a restricting factor for consumer when trying a less expensive chicken. As regards none significant variables, certain results obtained are a priori against -intuitive. Socioeconomic variables are not significant, indicating those consumers are not willing to pay premium for those perceived attributes. We assumed that, offers have a policy of low cost which attracts consumers despite their principal activity or social category. The only variable which is significant is possibility of negotiation [BARG]. But it is negative, which confirms that to have a price near to his spare price, the consumer tries to negotiate price with the seller. So the willingness to pay for the local flesh chicken is not only dictated by the peculiarity of the chicken, but also by other tacit attributes. Like in 3.1, socioeconomics variables are significant. We can conclude like in 3.1.

Case of the local flesh chicken

Conclusion and implications

This study aims at developing an implicit price of chicken in Cameroon on the basis of the extrinsic and intrinsic characteristics of chicken as it is perceived by the consumer. The main originality of this approach is to consider imperfections of Cameroonian market to interpret our results: so, we assumed the segmentation of markets and the consumer never has the perfect information concerning the characteristics of chicken sold.

An essential limit of this study is to have not been able of knowing, for every transaction, the weight of the bought local flesh chicken, whereas this element indeed constitutes a major determinant of negotiated price. However, econometric estimations confirmed that the weak marginal willingness to pay the local flesh chicken is due the very weak purchasing power of consumers. Consumer's substituted local flesh chicken by imported frozen chicken. This advantage of the imported frozen chicken compared to the local flesh chicken is reinforced by their practice in culinary usage and availability in local market. The only advantage of local flesh chicken which is sold alive, is the possibility of bargaining Perhaps that, a better valorisation of the local flesh chicken attributes by improving information to the consumers could contribute to follow-up the local chicken connection. In the same way, they could wonder about the opportunity of the adaptation of local chicken connection to the evolution of household habits: allowing presented the local flesh chicken in separate parts and in all markets. Finally, the reduction of the price difference between the local flesh chicken and the imported chicken could envisage via a strengthening of protection on importation borders. The opportunity of such measures, its effects on the global economic and its compatibility with commitments of Cameroon with World trade organisation and International monetary fund remain to be studied and make subject of ongoing researches.

  Figure 4.

Table 1 . Explicative variables used to estimate hedonic price function.

 1

		Variable		Description
	1. Dependent variable
	Willingness to pay [WTP]		WTP of chicken: posted for imported frozen cutting
				chicken and proposed by the purchaser for alive
				flesh local chicken sold. The price is expressed in
				Euro (€).
	2. Independents variables
	2.1. Criteria related to the product
	 Low cost [COST]
				1 if the choice is determined by the least price of
	 Taste [TASTE]		selected chicken and 0 if not.
				1 if the choice is determined by the succulence of
	 Practice [CUISS]		the flesh of selected chicken and 0 if not.
				1 if the practice of the chicken (the fact that it is
				plucked or cut out) enters the choice of bought
				chicken and 0 if not.
	2.2. Criteria related to the place of sale
	 Bargaining [BARG]		1 if the choice of the place of sale is determined by
	 Handing-over [HOVER]  Proximity [PROX]	the possibility of bargaining and 0 if not. 1 if the choice of the place of sale is determined by the possibility of handing-over and 0 if not.
	 Quality	[QUALIT]	1 if the choice of the place of sale is determined by its proximity and 0 if not.
				1 if the choice of the place of sale is determined by
				the quality from the products which are there and 0
				if not.
	2.3.	Dependent	criteria
		with the interviewee
	 Age [AGE]		Numerical variable which indicate the consumer
	 Mouth [MOUTH]		age.
				Numerical variable which indicate the size of the
	 Principal activity		household number of mouths to be nourish).
		o Unemployed [UNEM]
		o Informal [INFORM]	1 if the interviewee is unemployed and 0 if not.
		o Salesmen [SALES]
		o Employee [EMPLO]	1 if the interviewee qualifies his occupation of
	 Level of study [LEVET]	abstract and 0 if not.
				1 if the interviewee is a salesman/trading and 0 if
				not.
				1 if the interviewee is an employee/civil servant and
				0	if	not.

Table 3 . Results of the hedonic regression from local flesh chicken

 3 Table 3 has the results of the hedonic regression for local flesh chicken.

	Dependent variable: willingness to pay for local flesh chicken [WTP]
	Included observations: 156
	Variable	Coefficient Std. Error	t-Statistic	Prob.
	C	3605.136	559.1027	6.448074	0.0000
	MOUTH	8.443824	22.72587	0.371551	0.7108
	AGE	6.134856	8.095911	0.757772	0.4499
	LEVET	-179.2956	126.1968	-1.420761	0.1576
	TASTE	-169.8975	299.3850	-0.567488	0.5713
	QUALIT	-203.0100	326.7333	-0.621332	0.5354
	PROX	-180.9171	263.3542	-0.686973	0.4932
	BARG	393.5863	186.6845	2.108296	0.0368*
	HOVER	117.4038	465.8474	0.252022	0.8014
	UNEM	45.06590	206.1019	0.218658	0.8272
	EMPLO	-267.7879	202.8124	-1.320373	0.1888
	SALES	-137.1425	239.1956	-0.573349	0.5673
	PREFLOCAL	78.10300	171.4738	0.455481	0.6495
	PATC	-287.0493	178.1894	-1.610922	0.1094
	PATF	-49.74685	245.8415	-0.202353	0.8399
	R-squared	0.125690	Mean dependent var	3363.462
	Adjusted R-squared	0.038879
	S.E. of regression	940.6050
	Sum squared resid	1.25E+08
	Log likelihood	-1281.527	F-statistic		1.447862
	Durbin-Watson stat	1.541883	Prob(F-statistic)	0.138927

Caption: Significant test, * significant at 10 %

It would be necessary to add that in reality, the object of this survey at first was not to make an econometric estimate later. It is only several months after the survey, considering the extent of collected data that we decided to estimated a willingness to pay for chicken attributes.

Fish shops are special markets where fish and imported frozen cutting chicken are sold and stored in freezer.