Shared MPR Sets for Moderately Dense Wireless Multihop Networks

Abstract

Multipoint relays (MPRs) are used for flooding topology control messages and finding the shortest paths for unicast communications in the optimized link state routing protocol (OLSR). In this paper, we propose a method for achieving more efficient MPR selection in moderately dense wireless multihop networks (including sensor networks) than the conventional MPR selection. First, we analyze moderately dense networks to show that a node close to the two-hop border has little probability of being a two-hop neighbor. Second, we explain that there is a chance of the node's MPRs being shared with its neighbors.

To maximize this chance, we propose using shared MPR sets. These sets minimize the MPR ratio, which is defined as the number of nodes selected as MPRs by at least one neighbor divided by the total number of nodes in the network. Simulations are used to confirm the efficiency of using shared MPR sets. A centralized heuristic algorithm shows an MPR ratio redundancy in moderately dense networks that is about 10% of that obtained through conventional MPR selection.

1. Introduction

Multipoint relays (MPRs) [1, 2] support the efficient flooding of topology control (TC) messages in the optimized link state routing protocol (OLSR) [3] and are used to find the shortest path to any pair of nodes for unicast communications in OLSR. Although OLSR is designed as a routing protocol for mobile ad hoc networks (MANETs), it can also be used for sensor networks. OLSR is a proactive routing protocol on which each node regularly exchanges topology information with other nodes.

MPR is the key concept used in OLSR. Each node selects a subset of its neighbors as its MPR set. According to the RFC 7181 [4], the MPR set is selected to satisfy two properties: (1) if a node v sends a message and that message is successfully forwarded by all MPRs of v, then all 2-hop neighbors of v will receive that message and (2) keeping the MPR set small ensures that the overhead of the protocol is kept at a minimum.

The nodes that have been selected as MPRs have two roles: generating and forwarding TC messages into the entire network and acting as routers. Each TC message generated by a node w advertises the link state information between itself and a node v during v's selection of w as one of its MPRs. In contrast, non-MPR nodes (none of which is selected as an MPR by a neighbor) do not generate or forward TC messages except to enable an OLSR redundancy option calledTC_REDUNDANCY. Thus, it is implied that non-MPR nodes act as edge nodes; that is, they do not act as routers. The path constructed with a sequence of links between an MPR and its selector is the shortest path.

We analyze the density of MPRs in moderately dense wireless multihop networks including sensor networks and present two issues that arise with conventional MPR selection: high MPR density and redundancy. First, the high MPR density issue implies that many TC messages are generated and flooded. Wu et al. [5] have already proven the asymptotic property that the average number of MPRs in a finite region is infinite when the network is extremely dense. However, we analyze moderately dense networks for additional insight into their nonasymptotic properties. Our concern is the distance from a node to its two-hop neighbor.

The second issue—redundancy of the conventional MPR selection—causes redundancy in dense networks because it minimizes the number of MPRs selected by each node using a fully distributed manner. Therefore, we propose a concept called “shared MPR sets” to reduce routing overhead. Through a simulation with a heuristic shared MPR selection algorithm, which is not distributed, we confirm the redundancy of conventional MPR selection in moderately dense networks.

For sensor networks, it is important to conserve the spectrum and energy. A way to achieve this is to improve the efficiency of OLSR by reducing TC messages. Our goal is to explain the following properties of moderately dense wireless multihop networks.

• (i)

Each node has a chance to share its MPRs with its neighbors (Section 3).

(ii)

If MPR sharing is achieved well, OLSR's routing overhead is reduced (Section 4).

In this paper, we only discuss the existence of shared MPR sets with a centralized algorithm (the effectiveness of this method is shown through simulations); we do not discuss a feasible algorithm for finding shared MPR sets in a distributed manner. A preliminary version of this study appeared in [6]. Developing an efficient distributed algorithm is our main goal for future work. Several distributed heuristic algorithms have been proposed by Yamada et al. [7], Maccari and Lo Cigno [8], and ourselves [9]. However, the efficiency of those proposed algorithms has not yet been fully analyzed.

The rest of the paper is organized as follows. Related work is described in Section 2; this includes studies regarding OLSR, MPRs, and connected dominating sets (CDSs). In Section 3, we analyze the distance from a node to its two-hop neighbor, which is associated with conventional MPR selection, and introduce the concepts of MPR sharing and shared MPR sets. In Section 4, we provide a heuristic algorithm for shared MPR selection and provide the simulation results for dense wireless multihop networks. Based on those results, we confirm that routing overhead is reduced when shared MPR sets are used. Finally, we conclude this paper in Section 6.

2. Related Work

2.1. OLSR

OLSR [3] is a proactive routing protocol for MANETs. OLSR maintains neighborhood information and topology information in each node and can find the shortest path between any pair of nodes with relatively less control traffic.

We briefly review these two types of information and two types of messages. We denote a node by v, w, or u. Regarding neighborhood information, node v stores the partial two-hop information $G_{P\mathrm{2}}(v)=(N(v)\cup N_{\mathrm{2}}(v),E_{P\mathrm{2}}(v))$ , MPRs $M(v)$ , and MPR selectors $M^{-\mathrm{1}}(v)$ . The node sets $N(v)$ and $N_{\mathrm{2}}(v)$ are sets of one-hop neighbors and strict two-hop neighbors, respectively. The edge set $E_{P\mathrm{2}}(v)$ is a set of symmetric links between one-hop neighbors and two-hop neighbors. Note that $E_{P\mathrm{2}}(v)$ does not contain links between strict two-hop neighbors.

Neighborhood information is updated when node v receives a HELLO message. HELLO messages are broadcasted by all nodes periodically but are never forwarded. When node v receives a HELLO message from node w, v recognizes that w is a one-hop neighbor of v and adds w to $N(v)$ .

The HELLO message of w includes one-hop neighbors $N(w)$ and MPRs $M(w)$ . When v receives a HELLO message of w, for each node $u\in N(w)$ , v adds u and $(w,u)$ in $N_{\mathrm{2}}(v)$ and $E_{P\mathrm{2}}(v)$ , respectively. Node v also adds w in $M^{-\mathrm{1}}(v)$ if $v\in M(w)$ . Afterward, node v computes its MPRs $M(v)$ by using the MPR selection algorithm [3] with updated $N(v)$ , $N_{\mathrm{2}}(v)$ , and $E_{P\mathrm{2}}(v)$ (The MPR selection algorithm is described in Section 2.2). Note that if node $u\in N_{\mathrm{2}}(v)$ is also in $N(v)$ , then node u is removed from $N_{\mathrm{2}}(v)$ . After several HELLO messages are exchanged, the neighborhood information satisfies

$$\begin{array}{l}N\left(v\right)=\left\{w\hspace{0.17em}|\hspace{0.17em}d\left(v,w\right)<r\right\}\\ N_{\mathrm{2}}\left(v\right)=\left\{u\hspace{0.17em}|\hspace{0.17em}u\in N\left(w\right),w\in N\left(v\right),u\notin N\left(v\right),u\ne v\right\}\\ E_{P\mathrm{2}}\left(v\right)=\left\{\left(w,u\right)\hspace{0.17em}|\hspace{0.17em}w\in N\left(v\right),u\in N\left(w\right)\right\}\\ M\left(v\right)\\ \subseteq N\left(v\right)\\ \text{such\hspace{0.17em}\hspace{0.17em}that}\hspace{0.17em}\hspace{0.17em}{\hspace{0.17em}}^{\forall }u\in N_{\mathrm{2}}\left(v\right),\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}{\hspace{0.17em}}^{\exists }w\in M\left(v\right),\hspace{0.17em}\hspace{0.17em}\left(w,u\right)\in E_{P\mathrm{2}}\left(v\right)\\ M^{-\mathrm{1}}\left(v\right)=\left\{w\hspace{0.17em}|\hspace{0.17em}v\in M\left(w\right)\right\}.\end{array}$$

(1)

Note that $d(v,w)$ is the distance between v and w and r is the radio range.

The topology information for each node, denoted by u, is a directed subgraph of the network G. The directed subgraph, denoted by $G^{\prime }(u)=(V^{\prime }(u),E^{\prime }(u))$ , includes all reachable nodes and partial directed links. $G^{\prime }(u)$ is generated on the basis of the received TC messages. A TC message is periodically generated by every MPR, denoted by w, and includes $M^{-\mathrm{1}}(w)$ . $M^{-\mathrm{1}}(w)$ is called an MPR selector set. TC messages are flooded into the entire network, and each of it informs the links between w and each of $M^{-\mathrm{1}}(w)$ . When node u receives a TC message generated by w, for each $v\in M^{-\mathrm{1}}(w)$ , node u adds v and $(w,v)$ in $V^{\prime }(u)$ and $E^{\prime }(u)$ , respectively. Node u also adds w in $V^{\prime }(u)$ .

The routing table of node u is constructed using $G_{P\mathrm{2}}(u)$ of the neighborhood information and $G^{\prime }(u)$ of the topology information. By using these two types of information, node u can find the shortest path to any other node in the network for unicast communications.

OLSRv2 [4] has already released in April 2014. Therefore, the discussion here is applicable to OLSRv2. In OLSRv2, nodes can freely interoperate regardless of whether they use the same MPR selection algorithm; an example algorithm for calculating MPRs is available in appendix B of OLSRv2 [4]. OLSRv2 defines two MPR sets (flooding MPR and routing MPR) and adopts neighborhood discovery protocol (NHDP) [10] to acquire neighborhood information.

2.2. Multipoint Relays

Multipoint relaying has been proposed by Qayyum et al. [1, 2] for efficiently flooding broadcast messages in mobile wireless networks. The concept of multipoint relaying is to reduce the number of duplicate retransmissions while forwarding a broadcast message.

Each node v selects a small subset of its neighbors $N(v)$ as MPRs $M(v)$ . When node v transmits a broadcast message generated either by itself or another node, each node $w\in M(v)$ retransmits the message only once; other neighbors do not retransmit it.

In MANETs, for proactive and reactive protocols, flooding is used to find a path to the destination. OLSR [3] also adopts the use of MPRs to disseminate TC messages.

Qayyum et al. [2] analyze MPRs and propose a heuristic MPR set selection algorithm. They prove that the following MPR problem is NP-complete: given a network (i.e., the set of one-hop neighbors for each node), a node v of the network, and an integer k, is there a multipoint relay set for v of size less than k?

The heuristic algorithm proposed by Qayyum et al. provides a near-optimal MPR set. They prove that the MPR set computed by that heuristic contains at most $\log n$ times more nodes than the optimal MPR set [2], where n is the number of nodes in the network. The input of the heuristic is the partial two-hop information $G_{P\mathrm{2}}(v)$ , and the output of the heuristic is the MPR set $M(v)$ . The heuristic algorithm is stated as follows:

• (1)

Start with an empty MPR set $M(v)$ .

(2)

First, select as MPRs those one-hop neighbors in $N(v)$ that are only neighbors of some node in $N_{\mathrm{2}}(v)$ ; add these one-hop neighbors to $M(v)$ .

(3)

While there still exists some node in $N_{\mathrm{2}}(v)$ that is not covered by $M(v)$ , one has the following:

• (a)

For each node in $N(v)$ that is not in $M(v)$ , compute the number of nodes that it covers among the uncovered nodes in $N_{\mathrm{2}}(v)$ .

(b)

Add the node of $N(v)$ in $M(v)$ for which this number is maximum.

Jacquet et al. [11] have analyzed OLSR MPR flooding in two network models: the random graph model and the random unit disk graph model. These two models are used for indoor and outdoor networks, respectively. In the two-dimensional random unit disk graph model, Jacquet et al. prove that the average size of the MPR sets tends to be smaller than $\mathrm{3}\pi (n^{\prime }/\mathrm{3}\pi {)}^{\mathrm{1}/\mathrm{3}}$ , where $n^{\prime }$ is defined by (3) in Section 3.1 below.

Busson et al. [12] have analyzed the conventional MPR selection in random unit disk graphs. They did not analyze sharing MPRs with neighbors; however, they do show that approximately 75% of MPR sets are selected in step 2 of the heuristic algorithm above, which implies that only the remaining 25% have a chance of sharing MPRs with their neighbors. The starting point of their analysis also uses (4), shown in Section 3.2 below. Our analysis in Section 3.2 is similar to theirs; however, unlike their research, we go on to analyze MPR sharing (Sections 3.3 and 3.4).

The motivation behind Maccari and Lo Cigno's research [8] is the same as ours. They describe the size of the global MPR set $M_G={\bigcup }_{v\in V}‍M(v)$ as the objective function that needs to be minimized; this objective function also appears in [6]. They have carefully revised the MPR selection algorithm and addressed implementation issues associated with that algorithm. Furthermore, they propose using the selector set tie breaker (SSTB) distributed strategy to minimize $M_G$ . Unlike us, their strategy for finding shared MPR sets is to use distributed algorithms; we use the centralized algorithm instead. However, we believe that the size of the global MPR set, which is calculated by the centralized algorithm, can be referred to as a type of numerical lower bound.

2.3. Connected Dominating Set

A connected dominating set (CDS) is a subset of nodes. Each node in a CDS has a path only through other nodes in the CDS, and every node in the network has at least one node in the CDS as a neighbor.

A small CDS is another candidate to reduce the number of forwarding nodes during the flooding process [13]. Instead of MPRs, a CDS can be used to flood messages to the entire network, and the nodes that are not there in CDS do not need to relay messages to flood. A small CDS will have less control traffic than MPRs. Furthermore, if the shortest path for every node is not a mandatory routing requirement, a small CDS can also be used for routing instead of MPRs.

A CDS does not have the (1) property of MPR sets that is described in Section 1. In other words, the use of MPRs guarantees the shortest path between any pair of nodes; CDS does not guarantee it. Furthermore, the time and message complexities of CDS schemes are slightly higher than those of MPR schemes. Perhaps for these reasons, unfortunately, CDSs are not currently employed in major MANET routing protocols.

Wu et al. [5] have explained several extensions designed to generate smaller CDSs using complete two-hop information. The complete two-hop information of node v is denoted by $G_{C\mathrm{2}}(v)=(N(v)\cup N_{\mathrm{2}}(v),E_{C\mathrm{2}}(v))$ . The difference between $G_{C\mathrm{2}}(v)$ and $G_{P\mathrm{2}}(v)$ is the sets of links. $E_{C\mathrm{2}}(v)$ includes all links in $E_{P\mathrm{2}}(v)$ as well as links between any pair of two-hop neighbors $N_{\mathrm{2}}(v)$ . Consider

$$\begin{array}{l}{E}_{C\mathrm{2}}=E_{P\mathrm{2}}\\ \cup \left\{\left(w_{\mathrm{1}},w_{\mathrm{2}}\right)\hspace{0.17em}|\hspace{0.17em}{w}_{\mathrm{1}},w_{\mathrm{2}}\in N_{\mathrm{2}}\left(v\right),\left(w_{\mathrm{1}},w_{\mathrm{2}}\right)\in V\right\}.\end{array}$$

(2)

To construct $G_{C\mathrm{2}}(v)$ in v, node v has to receive one-hop neighbor information $N(u)$ from each of its two-hop neighbor $u\in N_{\mathrm{2}}(v)$ . Because node u's HELLO messages have to reach all of u's two-hop neighbors, it implies that constructing $G_{C\mathrm{2}}$ requires higher communication overhead than constructing $G_{P\mathrm{2}}$ .

Wu et al. have proved that the extended MPR has a constant local approximation ratio rather than the logarithmic local ratio associated with the original MPR [5].

3. Analysis of MPRs in Dense Networks

3.1. Notation

We model a network as a unit disk graph $G=(V,E)$ , where V is a set of nodes in the network and E is a set of available links between nodes. Each node knows partial information of G by receiving HELLO and TC messages. The total number of nodes in the network is denoted by $n\hspace{0.17em}\hspace{0.17em}(=|V|)$ . For simplicity, we assume that the transmission range r of each node is uniform. There is an edge $(v,w)\in E$ if and only if $d(v,w)<r$ , where the function $d(\hspace{0.17em})$ is a distance between two nodes. A region $D(v,x)$ is defined as a disk with radius x that centers v. $D(v,r)$ is called a unit disk of v. A node in the unit disk $D(v,r)$ is called a one-hop neighbor of v.

Our analysis assumes that nodes are placed uniformly in a two-dimensional region. The expected number of nodes in a one-hop region is denoted by $n^{\prime }$ . For example, if the region is a square of side R and the number of nodes in the region is n, then

$$\begin{array}{cc}& n^{\prime }=\pi r^{\mathrm{2}}\frac{n}{R\times R}.\end{array}$$

(3)

We use the term “density” (defined as $n^{\prime }$ ) instead of the number of nodes in a unit square, that is, $n/R^{\mathrm{2}}$ , for convenience.

3.2. Distance to Two-Hop Neighbors

Suppose that there are two nodes v and u such that $d(v,u)=\mathrm{2}r-\delta \le \mathrm{2}r$ , as shown in Figure 1(a). We discuss the condition where u is a two-hop neighbor of v. Obviously, node u is a two-hop neighbor of v if and only if there is at least one node w that satisfies $d(v,w)\le r$ and $d(w,u)\le r$ . In other words, $d(v,u)\le \mathrm{2}r$ is a necessary but insufficient condition for u being a two-hop neighbor of v.

Figure 1

Determining whether u is a two-hop neighbor of v.

The region W is defined as $W=D(v,r)\cap D(u,r)$ , as shown in Figure 1(b). Node u is a two-hop neighbor of v if and only if there is at least one node $w\in W$ . The size of region W is denoted by $S(W)$ and expressed as follows:

$$\begin{array}{l}S\left(W\right)=\mathrm{2}\left(\pi r^{\mathrm{2}}·\frac{\mathrm{2}\theta }{\mathrm{2}\pi }-r^{\mathrm{2}}\sin \theta \cos \theta \right)\\ =r^{\mathrm{2}}\left(\mathrm{2}\theta -\sin \mathrm{2}\theta \right),\end{array}$$

(4)

where $\theta =\theta (\delta )=\arccos (\left(\mathrm{2}r-\delta \right)/\mathrm{2}r)$ . We define a probability function $p(\delta ,n^{\prime })$ that expresses the probability that u is a two-hop neighbor of v when u is $\mathrm{2}r-\delta$ away from v. Suppose that node w is a two-hop neighbor of v. The probability that w is not in the region W is $(\pi r^{\mathrm{2}}-S\left(W\right))/\pi r^{\mathrm{2}}$ . Node u is a two-hop neighbor of v if there is at least one one-hop neighbor of v in W. Therefore, in uniformly distributed networks, we approximate

$$\begin{array}{cc}& p\left(\delta ,n^{\prime }\right)=\mathrm{1}-{\left(\frac{\pi r^{\mathrm{2}}-S\left(W\right)}{\pi r^{\mathrm{2}}}\right)}^{n^{\prime }},\end{array}$$

(5)

where $n^{\prime }$ is the average number of a node's one-hop neighbors.

We try to expect the number of two-hop neighbors of v in various densities. First, we denote the expected number of nodes in $D(v,\mathrm{2}r)$ by $f(\mathrm{2}r)=\pi (\mathrm{2}r{)}^{\mathrm{2}}·n^{\prime }/\pi r^{\mathrm{2}}=\mathrm{4}{n}^{\prime }$ . Note that $f(\mathrm{2}r)$ includes the number of one-hop neighbors in $D(v,r)$ . We suppose that $f^{\prime }(x)=\mathrm{2}{n}^{\prime }x/r^{\mathrm{2}}$ is the derivative of $f(x)$ . We denote the expected number of two-hop neighbors of v by $E[|N_{\mathrm{2}}(v)|]$ . We derive $E[|N_{\mathrm{2}}(v)|]$ using a function $g(x,n^{\prime })$ , which is the expected number of two-hop neighbors of v in a disk $D(v,x)$ with the radius $x\hspace{0.17em}\hspace{0.17em}(r\le x\le \mathrm{2}r)$ and the density $n^{\prime }$ . The function $g(x,n^{\prime })$ is derived using $f^{\prime }(x)$ and $p(\delta ,n^{\prime })$ . Consider

$$\begin{array}{cc}& E\left[\left|N_{\mathrm{2}}\left(v\right)\right|\right]=g\left(\mathrm{2}r,n^{\prime }\right)\end{array}$$

(6)

$$\begin{array}{cc}& g\left(x,n^{\prime }\right)={{\displaystyle \int }}_r^x{f}^{\prime }\left(y\right)·p\left(\mathrm{2}r-y,n^{\prime }\right)dy.\end{array}$$

(7)

Figure 2 shows the numerical results of $g(x,n^{\prime })$ with various radii x and densities $n^{\prime }=\infty$ , 80, 40, 20, 10, and 5. From these results, we confirm that nodes close to the border of $D(v,\mathrm{2}r)$ are rarely a two-hop neighbor of v under moderately high-density conditions.

Figure 2

The expected number of two-hop neighbors in a disk of radius x.

To ensure the rareness of two-hop neighbors close to the border of $D(v,\mathrm{2}r)$ in moderately dense networks, Table 1 shows the radius x of a disk covering $q=\mathrm{70}\%\text{–}95\%$ of two-hop neighbors. The radius x satisfies $(q/\mathrm{100})g(\mathrm{2}r,n^{\prime })=g(x,n^{\prime })$ for each q and $n^{\prime }$ . We conclude that, even when density $n^{\prime }=\mathrm{80}$ (a very high density where the expected number of two-hop neighbors is 214), 95% of the two-hop neighbors (nearly 203 nodes) have $\delta >\mathrm{0.10}r=(\mathrm{2}-\mathrm{1.90})r$ , $\theta >\mathrm{0.32}=\mathrm{1}{\mathrm{8}}^{°}$ . In a moderately dense network, such as $n^{\prime }=\mathrm{20}$ (where the expected number of two-hop neighbors is 44), 90% of two-hop neighbors (40 nodes) have $\delta >\mathrm{0.22}$ , $\theta >\mathrm{0.47}=\mathrm{2}{\mathrm{7}}^{°}$ , and 70% of two-hop neighbors (31 nodes) have $\delta >\mathrm{0.39}$ , $\theta >\mathrm{0.64}=\mathrm{3}{\mathrm{6}}^{°}$ . From this observation, we expect that some small number of MPRs can cover all of a node's two-hop neighbors in moderately dense wireless multihop networks. This expectation is confirmed by the simulation illustrated in Figure 7 of Section 4.

Table 1

The radius x of a disk that covers q% of two-hop neighbors on various density $$n^{\prime }$$ .

q	$$n^{\prime }=\mathrm{\infty }$$	80	40	20	10	5
70%	$$\mathit{1.76}r$$	$$\mathit{1.69}r$$	$$\mathit{1.66}r$$	$$\mathit{1.61}r$$	$$\mathit{1.55}r$$	$$\mathit{1.51}r$$
80%	$$\mathit{1.84}r$$	$$\mathit{1.77}r$$	$$\mathit{1.74}r$$	$$\mathit{1.69}r$$	$$\mathit{1.64}r$$	$$\mathit{1.59}r$$
90%	$$\mathit{1.92}r$$	$$\mathit{1.85}r$$	$$\mathit{1.82}r$$	$$\mathit{1.78}r$$	$$\mathit{1.74}r$$	$$\mathit{1.70}r$$
95%	$$\mathit{1.96}r$$	$$\mathit{1.90}r$$	$$\mathit{1.87}r$$	$$\mathit{1.84}r$$	$$\mathit{1.81}r$$	$$\mathit{1.78}r$$

3.3. Conventional MPR Selection of a Node

Here, we review OLSR's conventional MPR selection in which any node selects its MPR set independently of its neighbors’ MPR sets. Understanding the symmetric property of this conventional selection will be helpful in understanding how MPRs can be shared as described in Section 3.4.

Suppose that there are two nodes $u_{\mathrm{1}}$ and $u_{\mathrm{2}}$ that satisfy $d(v,u_{\mathrm{1}})=\mathrm{2}r-{\delta }_{\mathrm{1}}$ and $d(v,u_{\mathrm{2}})=\mathrm{2}r-{\delta }_{\mathrm{2}}$ and that they are node v's two-hop neighbors, as shown in Figure 3. We assume that $u_{\mathrm{1}}$ and $u_{\mathrm{2}}$ are closer to each other than to other v's two-hop neighbors.

Figure 3

Covering two two-hop neighbors.

The regions $W_{\mathrm{1}}$ and $W_{\mathrm{2}}$ are defined similar to W in Section 3.2. Consider

$$\begin{array}{cc}& W_{\mathrm{1}}=D\left(v,r\right)\cap D\left(u_{\mathrm{1}},r\right)\\ W_{\mathrm{2}}=D\left(v,r\right)\cap D\left(u_{\mathrm{2}},r\right),\end{array}$$

(8)

where $u_{\mathrm{1}}$ (or $u_{\mathrm{2}}$ ) is a two-hop neighbor of v if and only if there is at least one node $w_{\mathrm{1}}\in W_{\mathrm{1}}$ (or $w_{\mathrm{2}}\in W_{\mathrm{2}}$ ). The angles ${\theta }_{\mathrm{1}}$ and ${\theta }_{\mathrm{2}}$ are defined as ${\theta }_{\mathrm{1}}=\theta ({\delta }_{\mathrm{1}})$ and ${\theta }_{\mathrm{2}}=\theta ({\delta }_{\mathrm{2}})$ , respectively.

The following discussion assumes that there are multiple nodes in $W_{\mathrm{1}}$ and $W_{\mathrm{2}}$ ; this avoids the case of having only one node in $W_{\mathrm{1}}$ and $W_{\mathrm{2}}$ , in which case, the nodes must be added to MPR set $M(v)$ in step 2 of the heuristic described in Section 2.2.

If there is at least one node w in $W_{\mathrm{1}}\cap W_{\mathrm{2}}$ , which is the hatched region in Figure 3, then $u_{\mathrm{1}}$ and $u_{\mathrm{2}}$ can be covered by single node $w\mathrm{\hspace{0.17em}\hspace{0.17em}}(=w_{\mathrm{1}}=w_{\mathrm{2}})$ . If there is no node in $W_{\mathrm{1}}\cap W_{\mathrm{2}}$ , there must be at least one node $w_{\mathrm{1}}\in W_{\mathrm{1}}\cap \overline{W_{\mathrm{2}}}$ and the other node must be $w_{\mathrm{2}}\in \overline{W_{\mathrm{1}}}\cap W_{\mathrm{2}}$ to cover $u_{\mathrm{1}}$ and $u_{\mathrm{2}}$ , respectively.

We denote $\angle u_{\mathrm{1}}v{u}_{\mathrm{2}}$ by ϕ and suppose that ${\delta }_{\mathrm{1}}\ge {\delta }_{\mathrm{2}}$ ; that is, ${\theta }_{\mathrm{1}}\ge {\theta }_{\mathrm{2}}$ . The inclusion relation between $W_{\mathrm{1}}$ and $W_{\mathrm{2}}$ is divided into the following three cases, where $S(\hspace{0.17em})$ is the size of the region:

• (1)

$\varphi >{\theta }_{\mathrm{1}}+{\theta }_{\mathrm{2}}$ ; that is, $S(W_{\mathrm{1}}\cap W_{\mathrm{2}})=\mathrm{0}$ .

(2)

${\theta }_{\mathrm{1}}+{\theta }_{\mathrm{2}}\ge \varphi$ and $\varphi >{\theta }_{\mathrm{1}}-{\theta }_{\mathrm{2}}$ , as shown in Figure 3; that is, $S(W_{\mathrm{1}}\cap W_{\mathrm{2}})>\mathrm{0}$ .

(3)

${\theta }_{\mathrm{1}}+{\theta }_{\mathrm{2}}\ge \varphi$ and ${\theta }_{\mathrm{1}}-{\theta }_{\mathrm{2}}\ge \varphi$ ; that is, $W_{\mathrm{2}}\subseteq W_{\mathrm{1}}$ .

In the first case, two nodes $w_{\mathrm{1}}\in W_{\mathrm{1}}$ and $w_{\mathrm{2}}\in W_{\mathrm{2}}$ are selected as MPRs of v to cover $u_{\mathrm{1}}$ and $u_{\mathrm{2}}$ , respectively. Two nodes $w_{\mathrm{1}}$ and $w_{\mathrm{2}}$ are selected independent of each other.

In the second case, if there is at least one node $w\in W_{\mathrm{1}}\cap W_{\mathrm{2}}$ , the optimal or heuristic MPR selection algorithm selects w as an MPR of v. However, this selection depends on the existence of other two-hop neighbors. The nodes in v's MPR set are either a single node w or two nodes $w_{\mathrm{1}}\in W_{\mathrm{1}}\cap \overline{W_{\mathrm{2}}}$ and $w_{\mathrm{2}}\in W_{\mathrm{2}}\cap \overline{W_{\mathrm{1}}}$ .

In the third case, if the optimal or heuristic MPR selection algorithm selects a node $w_{\mathrm{2}}\in W_{\mathrm{2}}$ as an MPR to cover $u_{\mathrm{2}}$ , then node $w_{\mathrm{2}}$ also covers $u_{\mathrm{1}}$ .

The number of MPRs of node v changes by selecting the second case. Each iteration of step 3 in the heuristic greedily adds a node in $M(v)$ ; thus, the algorithm covers the maximum number of uncovered nodes in $N_{\mathrm{2}}(v)$ .

3.4. Sharing an MPR with a Neighbor

Considering the symmetric property of conventional MPR selection (see Section 3.3), we explain how sharing MPRs with a neighbor is possible. Suppose that there are two nodes $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ , each of which is a one-hop neighbor of the other. Sharing MPRs means that $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ select the same node as their MPR.

First, we discuss the condition in which sharing MPRs is not allowed. As shown in Figure 4(a), if $v_{\mathrm{1}}$ has a two-hop neighbor u such that u is not a two-hop neighbor of $v_{\mathrm{2}}$ , then $v_{\mathrm{2}}$ has no one-hop neighbor in $W_{\mathrm{1}}$ . In this condition, $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ cannot share an MPR to cover u.

Figure 4

Covering two two-hop neighbors.

However, if there is a node u such that u is a two-hop neighbor of both $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ , as shown in Figure 4(b), and there is at least one node $w\in W_{\mathrm{1}}\cap W_{\mathrm{2}}$ , then $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ can select a node w as an MPR to cover u, thus sharing an MPR.

The sharable condition discussed above is symmetrical to the second case of conventional MPR selection, which is described in Section 3.3. However, the optimal and heuristic MPR selection described in Section 2.2 does not consider such sharing.

Note that the two-hop coverage of $v_{\mathrm{1}}$ and $v_{\mathrm{2}}$ 's MPR set is maintained regardless of whether the MPR is shared between them. The MPR is still guaranteed to construct the shortest path between any pair of nodes in the network, in contrast to CDSs, which do not guarantee the shortest path.

3.5. The Proposed Shared MPR Sets

The concept of shared MPR sets was first introduced by Yamada et al. [7]. They call the concept an MPR selection “redundancy,” which is defined as follows: for a combination of MPR sets of all nodes, if the number of MPRs in the network is greater than that of other combinations of MPR sets, the combination of MPR sets is redundant.

We define the MPR ratio to measure the degree of sharing. The ratio for shared MPR selection will be less than that for conventional MPR selection. We also define the number of MPRs per node to compare the average size of each node's MPR sets; this number will be constant for shared and conventional MPR selections. The MPR ratio and number of MPRs per node are defined as follows:

$$\begin{array}{cc}& \text{the\hspace{0.17em}\hspace{0.17em}MPR\hspace{0.17em}\hspace{0.17em}ratio}=\frac{\left|{{\displaystyle \bigcup }}_{v\in V}M\left(v\right)\right|}{n},\\ \text{the\hspace{0.17em}\hspace{0.17em}number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}MPRs\hspace{0.17em}\hspace{0.17em}per\hspace{0.17em}\hspace{0.17em}node}=\frac{{\sum }_{v\in V}\left|M\left(v\right)\right|}{n},\end{array}$$

(9)

where V is the set of nodes in the network, $M(v)$ is an MPR set of node v, and n is the number of nodes in the network (i.e., $n=|V|$ ). The MPR ratio shows the number of nodes selected as MPRs by at least one neighbor in the network. If the ratio is $\mathrm{1}$ , then all nodes are selected as MPRs. The number of MPRs per node shows the average number of MPRs selected by a node.

To compute $M(v)$ for all nodes, we define a bipartite graph $\mathcal{G}=(\mathcal{N}\cup {\mathcal{N}}_{\mathrm{2}},\mathcal{E})$ , where $\mathcal{N}$ is the union of one-hop neighbor sets $N(v)$ of all $v\in V$ and ${\mathcal{N}}_{\mathrm{2}}$ is the target pairs set derived by $N_{\mathrm{2}}(v)$ of all $v\in V$ . Consider

$$\mathcal{N}={\displaystyle \bigcup }_{v\in V}N\left(v\right)$$

(10)

$${\mathcal{N}}_{\mathrm{2}}=\left\{\left(v,u\right)\hspace{0.17em}|\hspace{0.17em}v\in V,u\in N_{\mathrm{2}}\left(v\right)\right\}$$

(11)

$$\begin{array}{l}\mathcal{E}=\{(w,p)\hspace{0.17em}|\hspace{0.17em}w\in \mathcal{N},p=(v,u)\in {\mathcal{N}}_{\mathrm{2}},w\in N\left(v\right),u\\ \in N\left(w\right(,\end{array}$$

(12)

where $(w,p)=(w,(v,u))\in \mathcal{E}$ means that there are two links $(v,w)$ and $(w,u)$ ; $\mathcal{N}$ and ${\mathcal{N}}_{\mathrm{2}}$ satisfy the conditions of $|\mathcal{N}|\le n$ and $|{\mathcal{N}}_{\mathrm{2}}|={\Sigma }_{v\in V}|N_{\mathrm{2}}(v)|$ .

To achieve the smallest MPR ratio, we need to find the smallest subset of $\mathcal{N}$ that covers all of ${\mathcal{N}}_{\mathrm{2}}$ . We define the coverage that $w\in \mathcal{N}$ covers as $(v,u)\in {\mathcal{N}}_{\mathrm{2}}$ if and only if $w\in N(v)$ and $u\in N(w)$ ; that is, $(w,p)\in \mathcal{E}$ . In conventional MPR selection, the coverage is defined for each node v as $w\in N(v)$ covers $u\in N_{\mathrm{2}}(v)$ if and only if $u\in N(w)$ ; that is, $(w,u)\in E_{P\mathrm{2}}$ .

Let $\mathcal{M}$ be a subset of $\mathcal{N}$ . The set $\mathcal{M}$ is called a global MPR set if a subset $\mathcal{M}$ covers all pairs of ${\mathcal{N}}_{\mathrm{2}}$ . For every node $v\in V$ , each node $u\in N_{\mathrm{2}}(v)$ has one or more one-hop neighbors in a global MPR set. Then, $N(v)\cap \mathcal{M}$ can be a candidate MPR set of v. Each node can select $N(v)\cap \mathcal{M}$ or its subset as the shared MPR set. The MPR ratio is given by $|\mathcal{M}|/n$ .

The computational complexity of finding the shared MPR sets that minimize the MPR ratio is expected to be NP-complete, because the basic structure of the problem is the same as the MPR problem [1] described in Section 2.2. Then, we use a heuristic shared MPR selection algorithm, which is discussed in the next section.

4. Experiments of Sharing MPRs with Neighbors

4.1. A Heuristic Shared MPR Selection Algorithm

We use the following algorithm in our experiment to show that shared MPR sets can reduce the routing overhead, especially the number of TC messages; however, note that because it is a centralized algorithm, it is not directly applicable to OLSR or other MANET routing protocols.

The algorithm adopts the greedy heuristic proposed by Qayyum et al. [1]. The primary difference between it and the conventional OLSR algorithm is that this algorithm runs on a whole network (i.e., is nondistributed) rather than on each node. Only the final step (4) runs on each node.

The input of this algorithm is $\mathcal{G}$ as defined in Section 3.5, and the output is the MPR sets $M(v)$ for all nodes. The heuristic algorithm is as follows:

• (1)

Start with an empty global MPR set $\mathcal{M}$ .

(2)

First, select, as global MPRs, those nodes in $\mathcal{N}$ that are the only neighbors of pairs in ${\mathcal{N}}_{\mathrm{2}}$ , and add these nodes to $\mathcal{M}$ .

(3)

While there exists at least one pair in ${\mathcal{N}}_{\mathrm{2}}$ that is not covered by $\mathcal{M}$ , one has the following:

• (a)

For each node in $\mathcal{N}$ that is not in $\mathcal{M}$ , compute the number of pairs that it covers among the uncovered pairs in ${\mathcal{N}}_{\mathrm{2}}$ .

(b)

Add the node of $\mathcal{N}$ in $\mathcal{M}$ for which this number is maximum.

(4)

For each node v, run the heuristic described in Section 2.2 to compute $M(v)$ . However, $N(v)\cap \mathcal{M}$ is used instead of $N(v)$ as the heuristic's input. The heuristic outputs the MPR set $M(v)$ for each v.

4.2. Metrics and Method

We use five metrics to explain our simulation results. The first two metrics concern the number of MPRs: the MPR ratio and the number of MPRs per node (described in (9)).

The remaining three metrics concern the routing protocol's communication overhead: the number of TC messages, the number of OLSR packets, and the total size of OLSR packets (in bytes). These three metrics are measured at the data link layer using a simulator log and are normalized by dividing the number of nodes and the simulation duration. Note that we count TC messages that are generated by a node and are forwarded by other nodes.

Moreover, to clearly show the redundancy of conventional MPR selection, the MPR ratio and number of TC messages in conventional MPR and shared MPR selections are compared. We define the MPR redundancy of conventional MPR selection as

$$\begin{array}{cc}& \frac{\left|{{\displaystyle \bigcup }}_{v\in V}M\left(v\right)\right|\text{\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}conventional\hspace{0.17em}\hspace{0.17em}MPR\hspace{0.17em}\hspace{0.17em}selection}}{\left|{{\displaystyle \bigcup }}_{v\in V}M\left(v\right)\right|\text{\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}shared\hspace{0.17em}\hspace{0.17em}MPR\hspace{0.17em}\hspace{0.17em}selection}}-\mathrm{1}.\end{array}$$

(13)

We define the TC message redundancy of conventional MPR selection as

$$\begin{array}{l}\frac{\#\text{\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}TC\hspace{0.17em}\hspace{0.17em}messages\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}conventional\hspace{0.17em}\hspace{0.17em}MPR\hspace{0.17em}\hspace{0.17em}selection}}{\#\text{\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}TC\hspace{0.17em}\hspace{0.17em}messages\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}shared\hspace{0.17em}\hspace{0.17em}MPR\hspace{0.17em}\hspace{0.17em}selection}}\\ -\mathrm{1}.\end{array}$$

(14)

We use the ns-2 simulator (ver. 2.29) with UM-OLSR v0.8.8 [14]. The simulation is set so that each node has an IEEE 802.11 interface, the transmission range is $r=\mathrm{250}$ meters, and all nodes are distributed randomly in a region of $\mathrm{2000}\times \mathrm{2000}$ meters² (i.e., an $\mathrm{8}r\times \mathrm{8}r$ region); the HELLO and TC message intervals are set to 2 and 5 s, respectively, and all nodes are set towill_default willingness. The simulation for each scenario runs for 100 s, and the number of messages is counted during the last 80 s of each simulation.

For the simulation, we assume that nodes do not move. We show the results of conventional MPR selection adopted in OLSR as well as shared MPR selection (which are described in Section 4.1). The number of nodes n in the network varies from 20 to 300. For each number of nodes, fifty different node topologies are simulated; the average results are shown in Section 4.3. Note that some topologies with small numbers of nodes are not fully connected graphs.

Regarding communication overhead, we describe how OLSR is modified to evaluate the heuristic shared MPR selection algorithm. Communication overhead caused by aggregating $\mathcal{G}$ to a virtual server and informing the global MPR set $\mathcal{M}$ from the virtual server is ignored. If it is included, the last two metrics (the number of OLSR packets and the total size of OLSR packets (in bytes)) increase, but the other three do not change. To suppress the increase in the first two metrics, we need to consider using a distributed algorithm; this is the most important goal of our future study. In our simulation, there is no difference in the number of HELLO messages when conventional MPR selection in OLSR is used and when shared MPR selection is used; in other words, HELLO messages are used to create partial two-hop neighbor information $G_{P\mathrm{2}}(v)$ for each node v, and MPR set $M(v)$ is broadcasted to the neighbors of v using HELLO messages.

We assume that the wireless multihop network is moderately dense (meaning that each node has about 5 to 10 one-hop neighbors). Statistically, the number of one-hop neighbors for each node, except for those close to the border of the $\mathrm{8}r\times \mathrm{8}r$ region, is $n^{\prime }=\pi \times \mathrm{25}{\mathrm{0}}^{\mathrm{2}}\times n/(\mathrm{2000}\times \mathrm{2000})$ as defined in (3). The number of strict two-hop neighbors is expected to be $E[|N_{\mathrm{2}}(v)|]$ based on (6). In networks of 300 nodes, there are statistically 14.7 one-hop neighbors and 34.2 strict two-hop neighbors for each node.

4.3. Simulation Results

Figures 5–10 show the simulation results for each metric. In each figure (except Figure 6), the results of conventional MPR selection and shared MPR selection are shown with the labels “Conventional” and “Shared,” respectively.

Figure 5

MPR ratio.

Figure 6

MPR and TC message redundancy.

Figure 7

Number of MPRs per node.

Figure 8

Number of TC messages per node per second.

Figure 9

Number of OLSR packets per node per second.

Figure 10

Size of OLSR packets (in bytes) per node per second.

The plot in Figure 5 shows that the MPR ratio for conventional MPR selection increases as the number of nodes increases (which is also discussed in Section 3.2). Wu et al. [5] have proved that this ratio will eventually increase to 1; however, the speed of increase shown in Figure 5 is rather slow.

By comparing the MPR ratios of conventional MPR selection with those of shared MPR selection (in Figure 5), we see that conventional MPR selection has over 10% redundancy in networks containing 100 or more nodes. Figure 6 charts MPR redundancy, which is defined in (13), thereby showing the redundancy more clearly. Based on the results shown in Figure 6, we determine that there is little redundancy in the low density networks of less than 50 nodes and large redundancy in moderately dense networks of over 100 nodes. In other words, when the average number of one-hop neighbors is greater than 5 ( $n^{\prime }=\mathrm{4.9}$ when $n=\mathrm{100}$ ), there is 10% redundancy in conventional MPR selection.

Figure 7 shows the average number of MPRs per node. Conventional MPR and shared MPR selection have almost the same results. The number of MPRs increases slowly when the number of nodes in the network increases. Even when $n=\mathrm{300}$ ( $n^{\prime }=\mathrm{14.7}$ ), no more than an average of 4.5 nodes are selected as MPRs by a node.

Figures 8 to 10 show the routing overhead results. These results are averaged per node and per second. Comparing conventional MPR selection to shared MPR selection, we find that, in all three metrics, shared MPR selection is able to reduce routing overhead in networks with 100 or more nodes.

When the number of nodes is greater than or equal to 80, the reduction ratio of shared MPR selection relative to conventional MPR selection is around 9%–12% in the number of TC messages (see Figure 8). More importantly, when the number of nodes is between 140 and 260, the reduction ratio is around 11%-12%. These results are also shown as TC message redundancy (defined in (14)) in Figure 6. From Figure 6, we observe that TC message redundancy is nearly proportional to MPR redundancy in networks of less than 200 nodes; however, we observe a different trend in networks of over 200 nodes. The reason for this different trend in high-density networks cannot be clearly explained, but it is possible that TC message redundancy decreases as networks increase in density. Future studies will examine this trend in greater detail to determine its cause.

Shared MPR selection also reduces the number of OLSR packets, depicted in Figure 9, and the reduction ratio here is even lower than that of the number of TC messages. Most likely, the ability to piggyback several messages into one packet causes the number of packets to decrease. The reduction ratio is around 9%-10% when the number of nodes is between 140 and 260 and around 5%–9% when the number of nodes is between 80 and 120.

Shared MPR selection also decreases the total size of OLSR packets (in bytes), as depicted in Figure 10, and the reduction ratio here is even lower than that of the number of TC messages and the number of OLSR packets. Although the headers of UDP, IP, and MAC will affect these results, the reduction ratio is around 7% when the number of nodes is between 140 and 260 and 4%–6% when the number of nodes is between 80 and 120.

To summarize the simulation results, we see that the MPR ratio increases slowly as the number of nodes in the network also increases, shared MPR selection maintains smaller MPR ratios and less routing overhead than does conventional MPR selection, and conventional MPR selection has room for improvement.

4.4. Comparison with CDS

To compare the MPR ratio with the CDS ratio, we refer to some results reported by Wu et al. [5]. Their evaluation simulates CDS within a $\mathrm{4}r\times \mathrm{4}r$ region. We increase the size of the CDS as the number of nodes in the network also increases. For networks of 30, 50, and 80 nodes, the CDS sizes are around 15 (50%), 20 (40%), and 25 (30%), respectively. The CDS ratio shown in parentheses is obtained by dividing the CDS size by the number of nodes in a network. Comparing the density of nodes in their $\mathrm{4}r\times \mathrm{4}r$ region with that in our $\mathrm{8}r\times \mathrm{8}r$ region, 30, 50, and 80 nodes in the former region have similar densities to 120, 200, and 300 nodes in the latter region.

In high-density networks (e.g., in our simulation, networks of 300 nodes), the MPR ratios of conventional MPR and shared MPR selection are 72% and 64%, respectively, and the CDS ratio of the corresponding network is only 30%. Thus, both MPR ratios in Figure 5 are higher than the CDS ratio.

In moderately dense networks of 200 nodes (see Figure 5), the MPR ratio of conventional MPR selection is 65% (that of shared MPR selection is 57%), and the CDS ratio is 40% in a network of similar density.

When the network is not so dense, the difference between the MPR and CDS ratios is small. In low-density networks (e.g., in our simulation, the network of 120 nodes ( $n^{\prime }=\mathrm{5.9}$ )), the MPR ratio of conventional MPR selection is 57% (that of shared MPR selection is 52%), and the CDS ratio is 50% in a network of similar density.

Consequently, if there is a feasible solution for calculating a CDS in a distributed manner and the network is dense, then the CDS will perform better than MPRs; however, the CDS does not guarantee the shortest path between any pair of nodes. Therefore, the next best choice is to find a feasible method for calculating shared MPRs in a distributed manner.

Comparing the MPR ratio with the CDS ratio, we see that the CDS achieves the smallest ratio and that shared MPR selection achieves the next smallest ratio.

5. Discussion

There are several distributed heuristic algorithms for calculating shared MPR sets, such as those put forth by Yamada et al. [7], Maccari and Lo Cigno [8], and ourselves [9]. However, in those studies, the sharing mechanism of MPR is not well analyzed and no bound is shown.

In Section 4, we simulate only a static environment; that is, nodes do not move in the simulation area. This limitation is the result of the high computational complexity associated with the centralized algorithm described in Section 4.1, which exists because the structure of the problem solved by the centralized algorithm is the same as the local MPR computation, which is an NP-complete problem [1]. Furthermore, the problem size increases; for example, $|\mathcal{N}|$ of (10) is larger than $|N(v)|$ if the graph $G=(V,E)$ is not a complete graph, and $|{\mathcal{N}}_{\mathrm{2}}|$ of (11) is about $|V|$ times larger than $|N_{\mathrm{2}}(v)|$ .

We employ the unit disk graph model for analysis and simulation. This model is valuable for theoretical discussions but does not represent the real environments of wireless communication. For an explanation of the differences between the model and real environments, we refer to the communication gray zones introduced by Lundgren et al. [15]. These zones are defined as areas where data messages cannot be exchanged—although HELLO messages indicate neighbor reachability—for various reasons including bit error rate, variable transmission rate, packet size, and different MAC layer handling between broadcast and unicast packets. To create simulations close to real environment, Chen et al. [16] and Pei and Henderson [17] have redesigned or tuned the IEEE 802.11 WLAN simulation model. More realistic evaluations can be performed with these models than with previous models. Furthermore, when we evaluate urban environments in our future study, obstacles should be modeled; for example, Sommer et al. [18] have proposed an empirical model of IEEE 802.11p path loss, including the attenuation of obstacles. For more realistic simulations, especially with mobile scenarios, these models will be valuable.

If nodes are allowed to move, then node mobility will be another important aspect to be considered in wireless multihop networks. Maccari and Lo Cigno [8] have proposed a stability-driven MPR choice strategy to minimize changes in the MPR selector sets in mobile scenarios. Minimizing these changes implies reducing the routing table calculation in each node. Musolesi and Mascolo [19] have also proposed a mobility model; theirs is based on community such as family members sharing a home or colleagues sharing an office. When mobile nodes are carried by humans, the community structures of humans strongly affect the dynamics of the mobile nodes. Therefore, the model put forth by Musolesi and Mascolo assigns each square area to a community. They have compared their mobility model with the Intel trace [20] and random waypoint mobility model in terms of intercontact times and contact durations. Our future work will include finding a suitable mobility model for evaluation.

6. Conclusion

In this paper, we explored MPR selection in moderately dense wireless multihop networks.

We have analyzed the distance to a two-hop neighbor in moderately dense networks and explained that nodes close to the border of a two-hop disk $D(v,\mathrm{2}r)$ , where r is a transmission range, have little probability of being a two-hop neighbor of v. From this observation, we expected that some small number of MPRs could cover all two-hop neighbors of a node, even in moderately dense wireless multihop networks. This expectation was confirmed by the simulation of up to 300 nodes in an $\mathrm{8}r\times \mathrm{8}r$ region.

We have also demonstrated the redundancy of conventional MPR sets and described a definition of shared MPR sets that minimizes the MPR ratio. We then provided a heuristic algorithm to select shared MPR sets. This heuristic is not applicable to the OLSR protocol, because it is not a distributed algorithm; however, the heuristic is valuable for showing the redundancy of conventional MPR selection. With this heuristic, we simulated some network topologies and measured the MPR ratio and routing overhead. Simulation results show that the redundancy in the number of TC messages, the number of OLSR packets, and the total size of OLSR packets is up to 12%, 10%, and 7%, respectively. We will continue to explore the feasibility of shared MPR selection as well as CDS schemes.