Conflict-Aware Relay Selection for Multicast in MUD based Wireless Networks

Conflict-Aware Relay Selection for Multicast in MUD based Wireless Networks

Asma Ben Hassouna, Hend Koubaa, Leila Azouz Saidane and Farouk Kamoun

CRISTAL Laboratory, National School of Computer Science (ENSI) University of Manouba, Tunisia

AbstractWe introduce a set of multiuser diversity (MUD) based relay selection schemes. The first one, called the Efficient Multi-user Diversity-based Relay (E-MDR) selection scheme, is done over steps by exploiting the channel qualities in terms of maximum achievable data rate (or channel capacity). E-MDR- based flooding strategy achieves the best multicast throughput without considering concurrent transmissions. The second one is the Conflict-free Multi-user Diversity based Relay (C-MDR) selection scheme, performs relay selection with consideration of the access conflicts. Finally, the Efficient Conflict-aware Multi- user Diversity-based Relay (EC-MDR) is proposed to do a compromise between C-MDR and E-MDR. Results prove that taking advantage of the user-diversity using E-MDR and exploiting the opportunities of concurrent transmissions by means of C-MDR gives better performance compared to the classic single-rate MPR selection scheme. Besides, it shows that coupling the throughput-sensitivity and the conflict-awareness, by means of EC-MDR, certainly leads to better resource exploitation than existing multiple-rate selection schemes.

Keywords Multi-user diversity; multi-rate; multi-point relay; wireless; ad hoc; throughput; multicast; conflict

I. INTRODUCTION

The original MPR selection heuristic [1] was the basis of a big number of wireless multicast algorithms. Regarding their objectives, the algorithms based on MPR selection technique are clustered into three groups. In the first group, the inherent MPR algorithms [2][3][4] apply several performance extensions (such as collision avoidance, reducing the number of forwarding users and power usage) while maintaining the concept of the original MPR heuristic. In the second group, the QoS-based MPR algorithms [5] select MPR users that verify a set of quality of service needs. Both groups do not exploit the multi-rate feature which characterizes many existing wireless standards as IEEE 802.11b, 802.11a, 802.11g. Mainly, multi-rate means the aptitude of a wireless card standard to automatically function at many different bit- rates and to vary its communication range. In the third group, relay selection algorithms [6][7][8] allow the senders to take advantage of the multi-rate feature. However, the works in this group are subject to some problems. Mainly, the multicast protocol in [6] focuses on the rate-adaptation rather than optimizing the number of relays. The rate-sensitive relay selection schemes presented in [7] and [8] are both conceived for multicast in the wireless mesh networks. The first proposes a weighted connected dominating set-based relay selection scheme (we call WCDS) which works out the data transmission rate at each forwarding user. The second (we call the Enhanced WCDS, E-WCDS) is based on the previous one.

It shows that the single-rate (i.e. single transmission) relay selection problem is considerably different from the multiple- rate (i.e. multiple transmissions) case where a user can dynamically adjusts its link layer multicast rates to its neighbors. However, these two works do not consider two issues: (a) the influence of the number of transmissions on the received throughput and (b) the effect of access conflicts on the system throughput. Accordingly, these works lead only to sub-optimal multicast solutions.

In a wireless network, diversity between users or Multi- User Diversity (MUD) means exploiting the qualities of the communicating users channels as a feature to improve the delivery of a message. MUD is possible due to the multi-rate feature. To deeply exploit the wireless medium, the MUD should be sensitive to the Wireless Broadcast Advantages (WBA) [9] which refers to an intrinsic attribute of wireless communication. The WBA means that direct neighbors of one source node can overhear the data transmitted only once. The direct neighbors depend on the transmission rate and, consequently, on the communication range. In this paper, we propose three new relay selection schemes that exploit the MUD and the WBA features and fix the above-mentioned issues (a) and (b).

The first relay selection scheme, called the Efficient Multi- user Diversity-based Relay (E-MDR) selection scheme, resolves problem (a). It is accomplished by means of a number of procedures executed to find the best relay users, their data transmission rates and their associated two-hop users. After each step, the throughput achieved could be enhanced. E- MDR selection scheme aims jointly to (i) reduce the number of relays and that of transmissions (the solution of issue (a)),

1. maximize the throughput of each single multicast session (or partition), (iii) exploit extremely the offered link capacities, and as a consequence, (iv) enhance the all over network throughput. The second relay selection scheme, called the Conflict-free Multi-user Diversity based Relay (C- MDR) selection scheme, resolves problem (b) by assuring multi-rate and conflict-aware multicast. Essentially, the conflict effect depends on the data rate used for transmission (i.e. transmission range). It is more important when the data transmission rate decreases (i.e. when transmission range augments). Our present solution is based on our prior work that proposes a multiple-rate multicast scheme that takes into consideration the effects of access conflicts on the system throughput [10][11]. It enables each multicast transmitter to select, in a conflict-sensitive way, the data rates to use in order to maximize the throughput. C-MDR is based on the two previously-presented concepts: the data Transmission Rate-

   based Interference Graph (TRIGraph) and the Concurrent Multi-rate Multicast transmitter Set (CMMS). Actually, The conflict relationship between multi-rate multicast transmitters for each data transmission rate is studied using the TRIGraph. As shown in Fig. 1, each vertex in the TRIGraph corresponds to a couple (u, r) where u is a multicast transmitter in the communication graph and r is a data transmission rate used by u to serve users. If u and v cannot transmit packets concurrently using data rates r and r, the two corresponding vertices (u, r) and (v, r) are joined by an edge in the TRIGraph. The CMMS is defined as a set of couples (u, r). In a CMMS, all the transmitters can multicast simultaneously using their data rates and all the links associated with them remain interference-free. In Fig. 1, we present two CMMSs. The first is CMMS1={(a,2)} and the second is CMMS2={(a,5), (c,10)}. Mostly, the C-MDR targets to (i) select relay users and their data transmission rates that maximize the multicast throughput, (ii) consider the effect of access scheduling when choosing relay users and (iii) resolve conflict problems (the solution of issue (b)). The third and last relay selection scheme, called the Efficient Conflict-aware Multi-user Diversity-based Relay (EC-MDR) selection scheme, resolves jointly the two problems: (a) and (b).

   In general, the number of transmissions needed to serve a set of users depends on the chosen multicast scheme. Two groups of schemes are distinguished: multiple-transmission schemes as DOMS [12], MOST [13] or unicast scheme (US)

   V2(n), are the one-hop neighbours of the one-hop neighbours of n in V1(n) which are not in V1(n). Table I defines the used notations. In the following sections:

   1. The throughput is the effective data rate received by the tw-hop users.

   2. The rate limiting user is that having the lowest channel capacity.

   3. A sender prioritizes the high-rate transmissions in order to guarantee that one user can overhear the data with the best possible data rate.

1. MUD AND WBA BASED RELAY SELECTION PARAMETERS

   Let us consider a set of assumptions that are the basics of our work. First, each user knows its one-hop and two-hop neighborhoods as well as their identities and their channel qualities. Second, we consider a network that supports a wide variety of data transmission rates. Finally, no global knowledge of the network topology and channel qualities, consequently data rates, is required and each sender user n makes localized decisions based on the partial information of its one-hop and two-hop neighbors. Actually, many parameters are used to make relay selection decisions. We describe the most important ones: the partition throughput and the total received throughput.

   [12] and single-transmission ones like the broadcast scheme (BS) [12]. In this work, to compute the system throughput, we dynamically pick the transmission scheme. This means that it

   n

   u v w

   Step 1

   n

   u v w

   is possible to study the influence of this latter on the performance of our relay selection strategies.

   9 6

   9 2 5 2

   9 6 2

   5 a 2

   CMMS1

   a,2

   CMMS2

   a,5

   a b c

   a b c

   b c

   10

   d

   1. The multicast tree

      Conclusion

      c,10

      • u is not considered during the following steps.

      • The number of relays should be minimized.

      Throughput (MOST used)	Partitions
      FMOST(u) = 5,5 FMOST(v) = 12 FMOST(w) = 4 v is chosen, recompute: FMOST(w) = 2	L(u) = {} L(v) = {a,b} L(w) = {c}

   2. The TRIGraph

   Fig. 1. TRIGraph and CMMS example

   The rest of this paper is arranged as follows. Section II presents an overview of the system model. Section III describes the relay selection parameters. Section IV presents the E-MDR selection scheme. In Section V, C-MDR and EC- MDR selection schemes are introduced. Analytical study of MDR based multicast is proposed in Section VI. Finally, conclusions and future works are drawn in Section VII.

   II. SYSTEM MODEL

   We introduce several notations that are inspired of graph- theory definitions. The wireless network is modelled by a directed graph G(VG, EG). The network users represent the set of vertices VG. Each edge in the set EG is presented by a triple (u, v, r), which means that user u can use data rate r to serve user v. Also, we consider one sender user n and the set of its one-hop neighbours, denoted by V1(n). This latter is the set of users within the transmission range of user n when it transmits using the lowest possible data rate. Mainly, a sender user selects a set of relay users from the set of its one-hop neighbours. The two-hop neighbourhood of n, denoted by

   Fig. 2. Example of step 1 execution

   1. The partition throughput

      It is the throughput value of the multicast session managed by a relay user u (u in V1(n)). Let us consider Cu={ru,v: u in V1(n) and v in V2(n)} the set of the channel capacities of the one-hop neighbours of user u, where ru,v is the capacity of the channel between users u and v. The values in Cu are ordered in an increasing order. Each user v, from the set of neighbours of realy user u, can overhear a packet transmitted by user u with a data rate lower or equal to the capacity of the channel between u and v. Actually, The partition throughput is computed using a generic function FX(u). For instance, FX could be FBS (which computes the throughput based on the BS multicast scheme), FDOMS (which computes the throughput based on the concept of DOMS access scheme [12]) or FMOST (which computes the throughput as dictated by the MOST multicast scheme [13]). In fact, the idea is simple: each user has to inspect its two-hop neighbours and choose the relays, also called group handlers (or E-MDR users), that guarantee the highest throughput and the lowest number of

      transmissions. For example, the throughput of a multicast session (also called a partition) managed by the user u when using BS is given in (1) and when using MOST is presented in (2). Mainly, nr is the number of users receiving a packet with

      data rate r (such as r Cu). The value of nr is equal to 0 if no reception. The notations N(tMOST ) and C(tMOST ) indicates,

2. E-MDR SELECTION SCHEME

   To ensure a successful selection of the E-MDR users and the data rates to be used, many steps must be carried out:

   Step 1: presented in Fig. 3, is a compulsory step that aims

   to create the set of partitions {L(u): u inV1(n)}. Each partition

   u u

   respectively, the number of transmissions and the set of data

   u

   rates of the best transmission strategy tMOSTgiven by MOST.

   L(u) is composed of users from V2(n) and is managed by user

   uV1(n). First of all, the algorithm of this step chooses users from V1(n) that are the only relays that can reach users in

   FBS (u) L(u) Cu (1)

   rC (t )

   nrr

   MOST

   FMOST (u) u

   N (t MOST )

   u

   1. The total throughput

   (1)

   (2)

   V2(n) (instructions B:). Second, the throughput FX(u) of each user uV1(n) is checked. Then, the user u having the highest value FX(u) is chosen to cover all the non-covered users in V2(n) (instruction C:). Actually, this step is necessary as it allows maximising the coverage of each relay user while maintaining good partition throughputs.

   Step 2: described in Fig. 4. In fact, the only solution to

   It is the throughput received by the two-hop neighbours of

   n. It is denoted by RY(n). This latter designates the throughput received by users in the set V2(n). The value of RY(n) is computed as given in (3). In fact, Y(n) is the set of relays chosen by n after executing the relay selection scheme Y. NX(u) is the number of transmissions needed by relay user u to deliver one data packet to all the users in L(u) using the multicast scheme X. As we notice, depending on the chosen multicast scheme, NX(u) value varies from 1 (using BS) to

   |L(u)| (using US). The output of any relay selection scheme Y,

   proposed in this paper, is a set of couples (u, r), which means that the chosen relay u should transmit using data rate r.

   enhance the throughput is to use the most suitable transmission rates available. In fact, it is possible to enhance the multicast session throughput obtained after Step 1 by means of the eventual step 2. In fact, the idea of this step is to change the attachment relay vV1(n) of the user Mu(v) if this move improves RE-MDR(n) value. This change may cause: (i) a loss in the throughput of the partition L(v) (lower FX(v) value) as well as that of the destination partition (ii) an improvement in the throughput of both the partition L(v) (higher FX(v) value) and destination partition or (iii) no throughput variation. If the resulting loss is lower than the gain, then the algorithm of step 2 decides to change the attachment relay of user Mu(v). Actually, for each user v in E-MPR(n), the

   FX (u) NX (u)

   RY (n) uY (n)

   NX (u)

   uY ( n)

   (3)

   algorithm considers y=Mu(v). Then, it seeks to attach y to the

   best relay from E-MPR(n), i.e., the relay that enhances RE- MDR(n) value. After that, the lowest capacities of the source

   partition or of the destination partition, which could be affected, are updated. In the algorithm of Step 2, y is excluded

   TABLE I. INDEX OF USED SYMBOLS

   from L(v) when < 0. In fact, < 0 means that:

   The set of MPR of node n.

   Notation	Description
   MPR(n)
   E-MDR(n)	The set of E-MDR relays of node n.
   C-MDR(n)	The set of C-MDR relays of node n.
   L(v)	Called a partition, i.e. the list of one-hop neighbours that are assigned to the relay v.
   L(v)+u	The list of one-hop neighbours (or partition) that are assigned to node v with consideration of the one-hop neighbour u.
   L(v)-u	The list of one-hop neighbours that are assigned to node v without considering the one hop node u.
   E(v)	The average distance between the data rates of the nodes from L(v) and the minimum data rate Cm. V
   FX(v)	The throughput of the multicast session managed by v and composed of nodes in L(v). The transmission scheme X is used.
   FX (v)+u	The throughput of the multicast session managed by v and composed of nodes in L(v) +u
   FX (v)-u	The throughput of the multicast session managed by v and composed of nodes in L(v) u
   Cv(1)	The lowest data rate of the nodes in L(v).
   ru,v	The capacity of link (u, v) (VG).
   |S|	The cardinality of the set S.
   Mu(v)	The node from L(v) having the minimum channel capacity.
   Ry(n)	The total throughput received by the two-hop neighbours of n when using the relays chosen by the selection scheme Y.
   Ry(n) i	The total throughput received by the two-hop nodes from n when using the relays chosen by the E-MDR scheme in step i.

   • Adding y to L(w) leads to a throughput gain (2<0) and including y to L(v) causes a throughput loss (1<0).

   • Adding y to L(w) leads to a throughput loss (1<0) that is higher than the throughput loss obtained when

   adding y to L(w) (2>0).

   Step 3: is shown in Fig. 5. It is probably executed by n to enhance the throughput obtained after the execution of Step 1. We consider a user xV2(n) and xL(v) such as x Mu(v). If it is possible to find another user v, such as v E-MPR(n), x

   V1(v) and Cv(1) Cv(1), then transferring x from L(v) to L(v) is a good move to enhance the throughput. Actually, when x is excluded from L(v) and is added to L(v), its throughput will be improved, and consequently the system throughput will be enhanced. This probable Step 3 improves the throughput of Step 1 where the coverage issue may dominate the throughput maximisation issue. After the execution of this step, each user from V2(n) can overhear the data with the best possible data rate.

   Step 1: Relay Identification

   A: Initially:

   • |E-MDR(n)| = 0,

   • For each v in V1(n)

   |L(v)| = 0

   End for

   B: Identify the set of neighbours v1(n) from V1(n) that are the only neighbours of nodes from V2(n). Add these neighbours to E-MDR(n) set:

   E-MDR(n)= E-MDR(n) U v1(n)

   C: While | V2(n)| 0 do

   1: Select the node v V1(n) E-MDR(n) having the highest FX(v) value. If many exist, choose the node that has a common one-hop neighbour with an existing relay. If such node does not exist, choose another node randomly.

   2: Add all the nodes from V2(n) covered by v to L(v).

   3: Add v to E-MDR(n)

   E-MDR(n)= E-MDR(n) + {v}

   4: Eliminate from V2(n) all the nodes covered by v: V2(n) = V2(n) L(v)

   End While

   of scheduling the access of these users can cause a dramatic throughput loss due to choosing conflicted relays.

   Step 2: The Enhancement of weakest users capacity

   1: While not stop do 2: Stop = true

   3: For each v in E-MDR(n) do 4: y = Mu(v)

   5: For each w in {i: i E-MDR(n) and i v and y V1(i) }

   6: 1=FX(v)+y – FX(v)-y

   7: 2= FX(w)-y – FX(w)+y

   8: = 1 + 2

   9: // >0, a throughput loss is obtained

   10: If ( < 0) then

   11: Stop=false

   12: L(w) = L(w) +{y}

   13: L(v) = L(v) {y}

   14: End if

   15: End For

   16: End For

   17: End While

   Fig. 4. The algorithm of step 2

   Fig. 3. The algorithm of step 1

   After step 1, each user from V2(n) is associated to one relay user from V1(n). Only the relays chosen during step 1 are considered during the two next steps (i.e. steps 2 and step 3). The E-MDR selection scheme aims to minimize the number of relays/ transmissions with consideration of the multicast throughput. For example, in Fig. 2, user u is not chosen as an E-MDR user. Thus, it is not considered during steps 2 and step 3. Also, we notice that some relays chosen during step 1 may be excluded from the set of relays during step 2 or step

   3. Consequently, the overall number of transmissions is controlled. Two examples that demonstrate the application of the E-MDR selection scheme are introduced in Fig. 8 and Fig. 9.

   Fig. 7 illustrates the throughput of the same two communication examples when using the WCDS relay selection scheme and the multi-rate version of MPR selection scheme. This latter prioritizes coverage factor and uses the BS to compute the throughput. In all the given instances, the source user n has to choose its relays from the set of one-hop neighbours. E-MDR is applied on Example 1 in Fig. 8. As we notice, only step 1 is performed. The throughput goes from 7.5Mb/s obtained using MPR and 8.33Mb/s obtained using WCDS to 9Mb/s achieved using E-MDR. Hence, the improvement is 20% compared to MPR and higher than 8% compared to WCDS. E-MDR is applied on Example 2 in Fig.

   9. Actually, step 1 and step 3 are carried out. E-MDR throughput reaches 11Mb/s which indicates an improvement compared to the throughput obtained using the MPR and WCDS schemes (and that is 10.5Mb/s).

3. C-MDR/EC-MDR: CONFLICT AWARE MUD BASED RELAY SELECTION SCHEMES

   1. C-MDR

      Relay users must decide when to transmit data packets. Two clashing targets are considered when doing the selection of these users: avoiding the access-conflicts and maximizing the throughput. Therefore, a balance is needed. In fact, separation between the stage of picking relay users and that

      Step 3: The Enhancement of partition throughput

      1: For each u in V1(n) do

      2: Compute Cu(1) based on channel quality information

      3: End For

      4: For each u in V1(n) do

      5: For each x in L(u) do

      6: For each v in {j: j E-MDR(n) and x V1(j) and Cj(1) Cu(1) and Cj(1) ru,x} do

      7: For each y in {i: i L(u) and ru,i = ru,x } do 8: L(u) = L(u) {y}

      9: L(v) = L(v) + {y}

      10: End For

      11: End For

      12: End For

      13: End For

      14: Repeat from 4: till no nodes change their groups

      6: The adopted relay v that have the best Cj(1) higher than Cu(1) and lower or equal to ru,x .

      7: The list of nodes in L(u) having the same channel capacity as x.

      Fig. 5. The algorithm of step 3

      The C-MDR selection scheme is the best solution to stop this loss. The idea is simple: each user selects, from its one-hop neighbourhood, the relay users and the data transmission rates that maximize the system throughput with consideration of access conflicts. The C-MDR(n) set is formed of a set of couples (u, r) which means that a user u is chosen to be a relay of n and that u can transmit data at data rate r. The input of the C-MDR selection strategy, applied by each user n, is the set of CMMSs of users in V1(n), denoted by Mn={1, 2, 3,}. Each CMMS i encloses a set of couples (u, r). If two couples (u, r) and (v, r) in C-MDR (n) set belong to the same CMMS set, then u and v can transmit their data at the same time using their data rates r and r. We say that (u, r) and (, r) are concurrent couples. The C-MDR(u) set should assemble the maximum number of concurrent couples. In fact, the target of this work is to select a set of relays that have the maximum aggregated throughput and that can be scheduled to transmit data at the same time. Due to space limitation, the scheduling strategy is discussed in future works. After determining the set of CMMS, each user n has to build the set of C-MDR(n) by applying the algorithm in Fig. 6. Actually, the process starts by choosing the best

      CMMS i in Mn. Then, the concurrent couples in i are added to C-MDR(n) set. Subsequently, they are excluded from the other remaining CMMS in Mn set. The two-hop neighbours

      n

      u v w

      Step 1

      n

      u v w

      Step 2

      Step 3

      n

      u v w

      of n, which are covered by the users of the chosen couples

      3 6 2 3 4

      3 4 6

      when they transmit data using their associated data rates, are excluded from V2(n). bestCMMS() function computes the throughput of each CMMS in the set Mn and returns the best

      4 13 12

      a b c d

      6 12

      FMOST(i)	L(i)
      FMOST(u) =	L(u) = {a, b}
      9,5	L(v) = {c, d}
      FMOST(v) = 12	L(w) = {}
      FMOST(w) = 2
      y chosen, recompute:	z E-MDR(n) R E-MDR(n) = 9 1
      FMOST(u) = 6

      1. b c d a

         Step 2

         12

      2. c d

      Step 3

      CMMS. The throughput computation is done as described by

      the algorithm in Fig. 10. Finally, the couples that do not cover any user in V2(n) and the empty CMMSs are excluded from the set Mn (instructions :18 to :29 and :30 to :35 in the algorithm in Fig. 6). Finally, this latter is reconstructed

      (reConstruct() function).

      No Maximization Users a and c do not hear from other relays in E-MDR(n)

      2

      R E-MDR(n) = 9 Mb/s

      No Maximization Moving user d to L(u): FMOST(u)= 9,5

      FMOST(v)= 6

      3

      R E-MDR(n)= 9Mb/s

      V1(i): The set of one-hop transmitter of user i

      Mi: The CMMS set determined by user i considering the set of users in V1(i).

      Function C-MDR_Computation ( n, V1(n), Mn ) : C-MDR(n)

      1: While |V2(n)|0 do

      2: i=bestCMMS(Mn)

      3: Mn =Mu- i

      4: For each (u, r) in i do

      5: //add v to the set of C-MDR(u)

      6: C-MDR(n)= C-MDR(n) +{(u,r)}

      7: For each j in Mn do

      8: //eliminate couples from j

      9: j=j- {(u, r)}

      10: End for

      11: //remove nodes covered by v at data rate r

      12: For each v in V2(n) do

      13: If Cu,v r then

      14: V2(n) = V2(n) – {v}

      15: End if

      16: End for

      17: End for

      18: //eliminate couples (u, r) that do not cover any node

      19: For each i in Mn do

      20: For each (u, r) in i do

      21: covered=0

      22: For each v in V2(n) do

      23: If Cu,v r then covered++

      24: End if

      25: End for

      26: If covered == 0 then

      27: j=j- {(u, r)}

      28: End if

      29: End for

      30: End for

      31: //eliminate empty CMMS sets from Mn

      32: For each i in Mn do

      33: If | i|==0 then

      34: Mn=Mn – i

      35: End if

      36: End for

      37: //Building the new Mu and recompute throughputs

      38: reConstruct(Mn)

      39: End while

      40: End C-MDR_Computation

      Fig. 8. The E-MDR selection scheme execution Example 1

      n

      n

      Step 1

      u v u v

      n

      Step 2 Step 3

      u v

      13

      6 12

      5 6

      a b c d

      5 13

      6

      6

      a b c d

      5 6 6 12

      a b c d

      FMOST(i)	L(i)	Step 2		Step 3
      FMOST(u) = 15	L(u) = {a, b, d}	No Maximization Users a and c do not overhear from other relays in E-MDR(n). R E-MDR(n) =10,5Mb/s 2		Possible Maximization Move user d to L(v): FMOST(u)= 10 FMOST(v)= 12 R E-MDR(n)= 11Mb/s 3
      FMOST(v) = 12	L(v) = {c}
      u chosen,
      recompute :
      FMOST(v) = 6	R E-MDR(n) =10,5

      Fig. 9. The E-MDR selection scheme execution Example 2

      Fig. 6. The construction of the C-MDR set of user n

   2. EC-MDR

   Generally, the C-MDR selection scheme is executed in a localized way, i.e., between the two-hop neighbourhood V2(n) of a user n. The example in Fig. 13(a) shows that prioritizing good concurrent transmissions may cause severe throughput loss. This latter is due to the fact that these transmissions are not sufficient to cover all the receivers in V2(n). Thus, we need additional transmissions, definitely using lower data rates, which reduce the system throughput. For that reason, sometimes it may appear appealing to think differently and to ignore concurrent transmissions by applying E-MDR selection scheme. This latter may possibly cause severe throughput losses because good concurrent transmissions are ignored. For instance, Fig. 13(c) shows that the actual throughput, obtained with consideration of access conflicts, is not reflected by E- MDR selection scheme. In view of that, the relay selection scheme should be defined dynamically depending on the communication topology. The solution that we propose is the EC-MDR selection scheme which considers both selection

   n

   u v w

   6

   3 13

   4

   a b c

   -Example 1-

   RE-WCDS(n)= 8,33Mb/s RMPR(n)= 7,5Mb/s

   n

   u v

   13 6

   5 6

   d a b c d

   -Example 2-

   RE-WCDS(n)= 10,5Mb/s RMPR(n)= 10,5Mb/s

   schemes: C-MDR and E-MDR. Each time, the selection scheme Y that gives the best throughput RY (computed as described in (3)) should be adopted. The EC-MDR selection scheme application is described in (4). A decision parameter is computed as shown in (4a). In (4b), the conflict-aware C- MDR scheme should be applied when 1. However, the conflict-unaware E-MDR scheme is selected when < 1. Fig. 13 presents three application examples of the proposed MDR

   Fig. 7. The throughput of BS based MPR selection scheme and E-WCDS selection scheme of two examples.

   selection schemes.

   RC- MDR (n)

   RE- MDR (n)

   C MDR if

   1,

   a

   communication scenarios; each scenario is formed of a source user, different sets of one-hop and two-hop users. The data rates of links between the users are varied randomly. The average throughput received by the two-hop neighbors of each communication scenario is described in Fig. 11. E-MDR

   (v,r) : The number of users in the set {i: i V2(n) and Cv,i r}.

   Mi: he set of CMMS determined by user i considering V1(i). TH(i) : The throughput of CMMS i

   THmax/max: The best throughput/CMMS

   Function bestCMMS ( Mn ): CMMS

   EC MDR E MDR

   1:

   2:

   3:

   TH=0

   For each i in Mn do

   (v,r )i

   4:

   5:

   6:

   7:

   8:

   9:

   10:

   otherwise

   b

   selection scheme that uses MOST multicast scheme was adopted. MOST is selected because it was proven [13] that it outperforms all the existing schemes (Mainly, BS, US and DOMS). The results prove that the throughput of MPR scheme is a lower bound of the throughput given by E-MDR. Actually, MPR selection scheme chooses the transmissions that minimize relays number. However, E-MDR selection scheme exploits the data rate opportunities with consideration of the number of transmissions.

   Fig. 12 shows that EC-MDR gives better throughput than all the other relay selection schemes (WCD, E-MDR and C- MDR). E-MDR represents i) the solution of the coverage problem that reduces the performance of C-MDR and ii) the solution of the access-conflict problem that limits the efficiency of E-MDR. This latter outperforms WCDS which actually chooses relays having the highest transmission rates

   If TH(i) > TH then THmax= TH(i) max= i

   End if End for Return max

   End bestCMMS

   r (v,r )

   TH(i )

   Fig. 10. The computation of the CMMS throughput

4. PERFORMANCE STUDY MDR BASED MULTICAST

   To study the performance of our work, we implemented the set of algorithms using the procedural and object-oriented programming paradigms offered by C++ language. To facilitate the throughput calculation, the wireless network is modelled as a graph. The links of this graph are set based on the available information about the global topology and neighbouring one-hop and two-hop nodes. We deploy several

   without considering the effect of the number of transmissions needed by a relay to deliver data to its one hop receivers. However, E-MDR that deploys MOST multicast scheme adopts good transmission rates and convenient number of transmission. Indeed, E-MDR may execute the throughput enhancement steps (step 2 and step 3) without registering any alteration in the initial relay set structure obtained after step 1. In the worst case, the throughput obtained by E-MDR will be that dictated by step 1 which is higher or equal to the rate obtained using multi-rate MPR selection scheme.

   n 2

   TRIGraph

   u v

   v,3

   n 1 2

   u,1.5

   TRIGraph

   u v

   u,2

   n

   u v TRIGraph

   2

   u,3

   1

   v,3

   6 3 u,6

   1.5 5 3

   v,2

   4

   u,5

   u,5

   3 4 1

   v,4

   2 2

   v,3

   5 3 3 4

   v,4

   a b c

   3

   a b c

   a b c 3

   n

   C-MDR

   u v

   n

   Mn= {1, 2}
   1={(u,6),(v,4)} 2={(v,3)}	TH(1)=10 TH(2)=9
   RC-MDR(n)=(10+3)/2=6.5 Mb/s RE-MDR(n)=3×3=9 Mb/s
   EC-MDR=E-MDR

   C-MDR

   u v

   n

   Mn= {1, 2, 3, 4}
   1={(u,1.5)} 2={(u,2)} 3={(v,2)} 4={(v,3),(u,5)}	TH(1)=4.5 TH(2)=4 TH(3)=4 TH(4)=8
   RC-MDR(n)=((5+3)+1.5)/2=4.75 RE-MDR(n)=1.5×3=4.5 Mb/s
   EC-MDR=C-MDR

   Mn= {1, 2, 3, 4}
   1={(u,5) ,(v,3)} 2={(u,1),(v,4)} 3={(u,5),(v,4)}	TH(1)=11 TH(2)=10 TH(3)=9
   RC-MDR(n)=5+3*2=11Mb/s RE-MDR(n)=(3×2+5)/2=5.5Mb/s
   EC-MDR=C-MDR

   C-MDR

   u v

   6 3 4

   1.5 5 3

   5 3 3

   E-MDR

   a b c

   n

   u v

   E-MDR

   a b c

   n

   u v

   E-MDR

   a b c

   n

   u v

   3 3 3

   1.5

   1.5

   1.5

   5 3 3

   a b c

   (a)

   a b c

   a b c

   1. (c)

      Fig. 13. The application of EC-MDR selection scheme

      MPR

      E-MDR

      14 14

      Throughput (Mb/s)

      12 12

      Throughput (Mb/s)

      10 10

      8 8

      6 6

      4 4

      2 2

      0 0

      1 2 3 4 5 6 7 8 9 10 11

      Communication scenario (higher data rates are generated randomly)

      E-MDR(MOST) E-MDR(BS)

      C-MDR EC-MDR

      1 2 3 4 5 6

      Communciation scenario

      REFERENCES

      1. Kitasuka, T.; Tagashira, S., "Finding more efficient multipoint relay set to reduce topology control traffic of OLSR," In the Proc of WoWMoM 201, pp.1,9, 4-7 June 2013, doi: 10.1109/WoWMoM.2013.6583478.

      2. H. Chizari, M. Hosseini, S. Salleh, S. Abd Razak, A. H. Abdullah: EF- MPR, a new energy eFficient multi-point relay selection algorithm for MANET, The Journal of Supercomputing 59(2): 744-761, 2012.

      3. A. Boushaba, A. Benabbou, R. Benabbou, A. Zahi, M. Oumsis. Multi- point relay selection strategies to reduce topology control traffic for OLSR protocol in MANETs. J. Netw. Comput. Appl. 53, July, 2015, 91-102,DOI=10.1016/j.jnca.2015.03.00.

      4. Zhiping Liao, Song Liu, and Shengfeng Xi, An Improved Multipoint

         Fig. 11. The E-MDR performance Fig. 12. The performance of MDR

         relay selection schemes

         Received Throughput

         (Mb/s)

         40

         30

         20

         EC-MDR WCDS

         10

         0

         0 10 20 30 40 50 60 70

         Number of users

         Fig. 14. EC-MDR Performance

         In Fig. 14, we compare the throughput received by the two- hop nodes, using WCDS and EC-MDR, as a function of the number of users. We notice that the EC-MDR gives higher throughput than multi-rate WCDS. Essentially, EC-MDR prefers good links and conflict-free transmissions. As we notice, the throughput received increases when increasing the number of users, since the opportunities of high- throughput/conflict-free links becomes more important.

5. CONCLUSION

In this paper, we have designed three multi-rate multi- point relay selection schemes that exploit the BA of the wireless medium to create a specific set of multi-rate multipoint relays. Each selected relay does one transmission to convey a data packet to its selected one-hop neighbours. As shown by the obtained results, our conflict aware MDR selection schemes, E-MDR, C-MDR and EC-MDR, are very simple ways to exploit MUD with no need to complex calculation strategies. They lead to higher throughput. In the future, it would be appealing to design the version of MDR selection scheme that targets to minimise the number of hops needed to reach any destination in the system.

Relaying Scheme for Message Propagation in Distributed Peer-to-Peer System, International Journal of Distributed Sensor Networks, vol. 2014, Article ID 792814, 10 pages, 2014. doi:10.1155/2014/792814

1. Said El brak, Mohamed El brak, and Driss Benhaddou, A New QoS Management Scheme for VoIP Application over Wireless Ad Hoc Networks, Journal of Computer Networks and Communications, vol. 2014, 2014. doi:10.1155/2014/945695.

2. A Basalamah, H Sugimoto, T Sato, A rate adaptive multicast protocol for providing MAC layer reliability in WLANs. IEICE Trans. Commun. 3(10), 12161220, 2006.

3. C.T. Chou, A. Misra, Junaid Qadir, "Low latency broadcast in multirate wireless mesh networks", in IEEE Journal on Selected Areas in Communication (JSAC), vol. 24, no. 11, Nov., 2006, pp. 2081 – 2091.

4. J. Qadir, C.T. Chou, A. Misra, J.G. Lim, "Localized minimum-latency broadcasting in multi-rate wireless mesh networks", in IEEE WoWMoM07, Espoo, Finland, Jun., 2007.

5. T. J. Ali, V. Kühn, Exploiting Wireless Broadcast Advantage for Routing in Static Networks, in Proc. of 9th SCC'2013, Munich, Germany, 2013.

6. A. Ben Hassouna, H. Koubaa, F. Kamoun, Conflict-Aware Relay Selection for Multicast in MUD based Wireless Networks, Journal Of Networks, 8(4), DOI:10.4304/jnw.8.4.787–795.

7. A. Ben Hassouna, H. Koubaa, & F. Kamoun,Conflictaware multicast in multiuser diversitybased wireless networks. International Journal of Wireless and Mobile Computing, 7(6), pp. 556-564.

8. T.-P. Low, M.-O. Pun, C. -C. Jay Kuo, Optimized Opportunistic Multicast Scheduling Over Cellular Networks, Acoustics, Speech and Signal Processing, in IEEE ICASSP09, Apr. 2009.

9. A. Hassouna, H. Koubaa, L.A. Saidene, F. Kamoun, "Accurate and fast multi-rate multicast scheme in wireless networks," in Proc of Fifth International Conference on Innovative Computing Technology, pp.124-129, 20-22 May, 2015.