 Open Access
 Total Downloads : 27
 Authors : Asma Ben Hassouna, Hend Koubaa, Leila Azouz Saidane And Farouk Kamoun
 Paper ID : IJERTCONV4IS04016
 Volume & Issue : PEMWN – 2015 (Volume 4 – Issue 04)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
ConflictAware 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 Multiuser Diversitybased Relay (EMDR) selection scheme, is done over steps by exploiting the channel qualities in terms of maximum achievable data rate (or channel capacity). EMDR based flooding strategy achieves the best multicast throughput without considering concurrent transmissions. The second one is the Conflictfree Multiuser Diversity based Relay (CMDR) selection scheme, performs relay selection with consideration of the access conflicts. Finally, the Efficient Conflictaware Multi user Diversitybased Relay (ECMDR) is proposed to do a compromise between CMDR and EMDR. Results prove that taking advantage of the userdiversity using EMDR and exploiting the opportunities of concurrent transmissions by means of CMDR gives better performance compared to the classic singlerate MPR selection scheme. Besides, it shows that coupling the throughputsensitivity and the conflictawareness, by means of ECMDR, certainly leads to better resource exploitation than existing multiplerate selection schemes.
Keywords Multiuser diversity; multirate; multipoint 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 QoSbased MPR algorithms [5] select MPR users that verify a set of quality of service needs. Both groups do not exploit the multirate feature which characterizes many existing wireless standards as IEEE 802.11b, 802.11a, 802.11g. Mainly, multirate 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 multirate feature. However, the works in this group are subject to some problems. Mainly, the multicast protocol in [6] focuses on the rateadaptation rather than optimizing the number of relays. The ratesensitive 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 setbased relay selection scheme (we call WCDS) which works out the data transmission rate at each forwarding user. The second (we call the Enhanced WCDS, EWCDS) is based on the previous one.
It shows that the singlerate (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 suboptimal 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 multirate 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 abovementioned issues (a) and (b).
The first relay selection scheme, called the Efficient Multi user Diversitybased Relay (EMDR) 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 twohop 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)),

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 Conflictfree Multiuser Diversity based Relay (C MDR) selection scheme, resolves problem (b) by assuring multirate and conflictaware 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 multiplerate 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 conflictsensitive way, the data rates to use in order to maximize the throughput. CMDR is based on the two previouslypresented concepts: the data Transmission Rate
based Interference Graph (TRIGraph) and the Concurrent Multirate Multicast transmitter Set (CMMS). Actually, The conflict relationship between multirate 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 interferencefree. In Fig. 1, we present two CMMSs. The first is CMMS1={(a,2)} and the second is CMMS2={(a,5), (c,10)}. Mostly, the CMDR 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 Conflictaware Multiuser Diversitybased Relay (ECMDR) 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: multipletransmission schemes as DOMS [12], MOST [13] or unicast scheme (US)
V2(n), are the onehop neighbours of the onehop neighbours of n in V1(n) which are not in V1(n). Table I defines the used notations. In the following sections:

The throughput is the effective data rate received by the twhop users.

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

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


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 onehop and twohop 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 onehop and twohop 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 singletransmission ones like the broadcast scheme (BS) [12]. In this work, to compute the system throughput, we dynamically pick the transmission scheme. This means that itn
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

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}


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 EMDR selection scheme. In Section V, CMDR 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 onehop 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 onehop neighbours. The twohop neighbourhood of n, denoted by
Fig. 2. Example of step 1 execution

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 onehop 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 twohop neighbours and choose the relays, also called group handlers (or EMDR 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,


EMDR SELECTION SCHEME
To ensure a successful selection of the EMDR 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

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 noncovered 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 twohop 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 REMDR(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 EMPR(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 EMPR(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)
EMDR(n)
The set of EMDR relays of node n.
CMDR(n)
The set of CMDR relays of node n.
L(v)
Called a partition, i.e. the list of onehop neighbours
that are assigned to the relay v.
L(v)+u
The list of onehop neighbours (or partition) that are assigned to node v with consideration of the onehop
neighbour u.
L(v)u
The list of onehop 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 twohop
neighbours of n when using the relays chosen by the selection scheme Y.
Ry(n)
i
The total throughput received by the twohop nodes
from n when using the relays chosen by the EMDR 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 EMPR(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:

EMDR(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 EMDR(n) set:
EMDR(n)= EMDR(n) U v1(n)
C: While  V2(n) 0 do
1: Select the node v V1(n) EMDR(n) having the highest FX(v) value. If many exist, choose the node that has a common onehop 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 EMDR(n)
EMDR(n)= EMDR(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 EMDR(n) do 4: y = Mu(v)
5: For each w in {i: i EMDR(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 EMDR 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 EMDR 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 EMDR 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 multirate 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 onehop neighbours. EMDR 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 EMDR. Hence, the improvement is 20% compared to MPR and higher than 8% compared to WCDS. EMDR is applied on Example 2 in Fig.
9. Actually, step 1 and step 3 are carried out. EMDR 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).


CMDR/ECMDR: CONFLICT AWARE MUD BASED RELAY SELECTION SCHEMES

CMDR
Relay users must decide when to transmit data packets. Two clashing targets are considered when doing the selection of these users: avoiding the accessconflicts 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 EMDR(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 CMDR selection scheme is the best solution to stop this loss. The idea is simple: each user selects, from its onehop neighbourhood, the relay users and the data transmission rates that maximize the system throughput with consideration of access conflicts. The CMDR(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 CMDR 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 CMDR (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 CMDR(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 CMDR(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 CMDR(n) set. Subsequently, they are excluded from the other remaining CMMS in Mn set. The twohop 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 EMDR(n)
R EMDR(n) = 9
1
FMOST(u) = 6

b c d a
Step 2
12

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 EMDR(n)
2
R EMDR(n) = 9 Mb/s
No Maximization Moving user d to L(u): FMOST(u)= 9,5
FMOST(v)= 6
3
R EMDR(n)= 9Mb/s
V1(i): The set of onehop transmitter of user i
Mi: The CMMS set determined by user i considering the set of users in V1(i).
Function CMDR_Computation ( n, V1(n), Mn ) : CMDR(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 CMDR(u)
6: CMDR(n)= CMDR(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 CMDR_Computation
Fig. 8. The EMDR 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 EMDR(n).
R EMDR(n) =10,5Mb/s
2
Possible Maximization Move user d to L(v): FMOST(u)= 10
FMOST(v)= 12
R EMDR(n)= 11Mb/s
3
FMOST(v) = 12
L(v) = {c}
u chosen,
recompute :
FMOST(v) = 6
R EMDR(n) =10,5
Fig. 9. The EMDR selection scheme execution Example 2
Fig. 6. The construction of the CMDR set of user n


ECMDR
Generally, the CMDR selection scheme is executed in a localized way, i.e., between the twohop 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 EMDR 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 ECMDR selection scheme which considers both selection
n
u v w
6
3 13
4
a b c
Example 1
REWCDS(n)= 8,33Mb/s RMPR(n)= 7,5Mb/s
n
u v
13 6
5 6
d a b c d
Example 2
REWCDS(n)= 10,5Mb/s RMPR(n)= 10,5Mb/s
schemes: CMDR and EMDR. Each time, the selection scheme Y that gives the best throughput RY (computed as described in (3)) should be adopted. The ECMDR selection scheme application is described in (4). A decision parameter is computed as shown in (4a). In (4b), the conflictaware C MDR scheme should be applied when 1. However, the conflictunaware EMDR 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 EWCDS 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 onehop and twohop users. The data rates of links between the users are varied randomly. The average throughput received by the twohop neighbors of each communication scenario is described in Fig. 11. EMDR
(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 EMDR. Actually, MPR selection scheme chooses the transmissions that minimize relays number. However, EMDR selection scheme exploits the data rate opportunities with consideration of the number of transmissions.
Fig. 12 shows that ECMDR gives better throughput than all the other relay selection schemes (WCD, EMDR and C MDR). EMDR represents i) the solution of the coverage problem that reduces the performance of CMDR and ii) the solution of the accessconflict problem that limits the efficiency of EMDR. 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


PERFORMANCE STUDY MDR BASED MULTICAST
To study the performance of our work, we implemented the set of algorithms using the procedural and objectoriented 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 onehop and twohop 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, EMDR that deploys MOST multicast scheme adopts good transmission rates and convenient number of transmission. Indeed, EMDR 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 EMDR will be that dictated by step 1 which is higher or equal to the rate obtained using multirate 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
CMDR
u v
n
Mn= {1, 2}
1={(u,6),(v,4)} 2={(v,3)}
TH(1)=10 TH(2)=9
RCMDR(n)=(10+3)/2=6.5 Mb/s REMDR(n)=3Ã—3=9 Mb/s
ECMDR=EMDR
CMDR
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
RCMDR(n)=((5+3)+1.5)/2=4.75 REMDR(n)=1.5Ã—3=4.5 Mb/s
ECMDR=CMDR
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
RCMDR(n)=5+3*2=11Mb/s
REMDR(n)=(3Ã—2+5)/2=5.5Mb/s
ECMDR=CMDR
CMDR
u v
6 3 4
1.5 5 3
5 3 3
EMDR
a b c
n
u v
EMDR
a b c
n
u v
EMDR
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

(c)
Fig. 13. The application of ECMDR selection scheme
MPR
EMDR
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)
EMDR(MOST) EMDR(BS)
CMDR ECMDR
1 2 3 4 5 6
Communciation scenario
REFERENCES

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, 47 June 2013, doi: 10.1109/WoWMoM.2013.6583478.

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

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, 91102,DOI=10.1016/j.jnca.2015.03.00.

Zhiping Liao, Song Liu, and Shengfeng Xi, An Improved Multipoint
Fig. 11. The EMDR performance Fig. 12. The performance of MDR
relay selection schemes
Received Throughput
(Mb/s)
40
30
20
ECMDR WCDS
10
0
0 10 20 30 40 50 60 70
Number of users
Fig. 14. ECMDR Performance
In Fig. 14, we compare the throughput received by the two hop nodes, using WCDS and ECMDR, as a function of the number of users. We notice that the ECMDR gives higher throughput than multirate WCDS. Essentially, ECMDR prefers good links and conflictfree transmissions. As we notice, the throughput received increases when increasing the number of users, since the opportunities of high throughput/conflictfree links becomes more important.



CONCLUSION
In this paper, we have designed three multirate multi point relay selection schemes that exploit the BA of the wireless medium to create a specific set of multirate multipoint relays. Each selected relay does one transmission to convey a data packet to its selected onehop neighbours. As shown by the obtained results, our conflict aware MDR selection schemes, EMDR, CMDR and ECMDR, 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 PeertoPeer System, International Journal of Distributed Sensor Networks, vol. 2014, Article ID 792814, 10 pages, 2014. doi:10.1155/2014/792814

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.

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.

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.

J. Qadir, C.T. Chou, A. Misra, J.G. Lim, "Localized minimumlatency broadcasting in multirate wireless mesh networks", in IEEE WoWMoM07, Espoo, Finland, Jun., 2007.

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

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

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

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.

A. Hassouna, H. Koubaa, L.A. Saidene, F. Kamoun, "Accurate and fast multirate multicast scheme in wireless networks," in Proc of Fifth International Conference on Innovative Computing Technology, pp.124129, 2022 May, 2015.