Average-Case Analysis of Greedy Matching for D2D Resource Sharing

We first describe our D2D resource sharing model that involves a large number of potential users to share resources with each other via local wireless links (e.g., short-range communications). In this model sharing takes place in repeated time intervals (or ‘rounds’). In each interval, we first run an algorithm to determine the pairs of users that are willing to exchange resources during the given round, and then realize the actual sharing of the corresponding resources as determined by the algorithm. The set of participating users and the available D2D links may be different for different rounds.

In each round, we form the ‘network graph’ $G=(U,E)$, where $U$ is the set of nodes corresponding to users that are participating in the given round, and $E$ is the set of D2D links between participating users that are feasible to establish with some minimum level of performance (e.g., signal strength, actual physical distance, etc., depending on the application). For each user $u_{i}\in U=\{u_{1},u_{2},\cdots,u_{n}\}$, the subset $A(u_{i})\subseteq U$ denotes the set of her neighbors in $G$, i.e., there is a feasible D2D link $e_{ij}\in E$ between $u_{i}$ and any $u_{j}\in A(u_{i})$. Note that different definitions of ‘feasibility’ for D2D links will imply a different set of edges $E$ between the users in $U$. Also the set $U$ is changing over time since new users may join the sharing economy and existing users may drop out after satisfying their needs or moving out of range.

With each edge $e_{ij}\in E$ there is an associated weight $w_{ij}\geq 0$ that models the (net) sharing benefit between this pair of users, if these users eventually transact with each other (i.e., are ‘matched’ in our terminology), converted in some monetary basis (say $\$$). Let $W=\{w_{ij}\}$ be the weight vector over all edges of $G$. Note that our model is very flexible and can fit to various applications of D2D resource sharing by allowing for different ways to define the values for $w_{ij}$. For example, in a secondary data-plan trading market [1, 2], user $u_{i}$ with data-plan surplus shares her personal hotspot connection with neighboring user $u_{j}$ with high roaming fee, and weight $w_{ij}$ models the difference between user $u_{i}$’s saved roaming fee and the sharing cost (e.g., energy consumption in battery) of user $u_{i}$. In another example of cooperative video streaming [4], user $u_{i}$ seeks user $u_{j}$’s assistance to download video segments for local sharing, and $w_{ij}$ becomes the difference between the QoE improvement of user $u_{i}$ and the download cost of user $u_{j}$.

In any given round, our sharing model corresponds to an instance of a random weighted graph $(G=(U,E),W)$. A simple interpretation of the model is that a typical user, when participating, corresponds to a random node in $G$. In particular, we don’t care for the actual identity of the participating users (after all, we care for the total value generated in the economy, summed over all participants). To simplify the model, we assume certain i.i.d. properties for the resulting stochastic process, i.e., in each round the set $U$ and the corresponding $E$, $W$ are i.i.d., with certain distributions. In particular, we assume that the weights $w_{ij}$ take values from a finite discrete set $V=\{v_{1},v_{2},\cdots,v_{K}\}$ according to the general probability distribution $Pr(w_{ij}=v_{k})=p_{k}$ with $\sum_{k=1}^{K}p_{k}=1$.¹¹1We can similarly extend our average-case analysis to continuous weight distributions, though it is unlikely to have any practical interest. Without loss of generality, we assume $0\leq v_{1}<v_{2}<\cdots<v_{K}$. A small-scale illustrative instance of the D2D resource sharing model is shown spatially on the ground in Fig. 1, which can be abstracted to a weight graph $(G=(U=\{u_{1},u_{2},\cdots,u_{7}\},E=\{e_{12},e_{17},e_{23},e_{25},e_{36},e_{45},e_{47}\}),W=\{w_{12},w_{17},w_{23},w_{25},w_{36},w_{45},w_{47}\})$.

In typical practices of D2D sharing (e.g., energy transfer), a user is only matched to a single neighbor (if any) to finally transact with. Keeping this simple but practical case of single matching per user²²2Allowing more concurrent matchings might not greatly improve performance, since in practice most of the total benefit is usually obtained from one among the possible matchings (e.g., assume a Pareto distribution on the values of the possible matchings). Furthermore, obtaining the resources as a result of a single matching decreases the marginal benefit of the resources from more matchings., given a weighted graph $(G=(U,E),W)$, we would like to match the most valuable (with the highest value of $w_{ij}$) pairs of users to maximize the total sharing benefit (i.e., the ‘social welfare’). Assuming full and globally available information on $G$ and $W$, we formulate the social welfare maximization problem as a maximum weighted matching problem:

where $x_{ij}$ is the binary optimization variable denoting whether edge $e_{ij}$ is included in the final matching ($x_{ij}=1$) or not ($x_{ij}=0$). Constraint (1b) tells that any user $u_{i}$ can only be matched to at most one user in her set of neighbors $A(u_{i})$.

According to [7], to optimally solve the maximum weighted matching problem $\mathcal{P}_{1}$, one needs to centrally gather the weight and graph connectivity information beforehand. Further, searching for all possible matchings results in super-linear computation complexity, which is formidably high for a network with a large number $n$ of users. Alternatively, the greedy matching addresses these two issues by keeping information local and allowing the algorithm to be performed in a distributed fashion. Algorithm 1 outlines the key steps of the greedy matching algorithm (please see intuition in the text that follows).

Initialization: $U^{\prime}=U$; $A^{\prime}(u_{i})=A(u_{i}),\forall u_{i}\in U$; $x_{ij}$

$=0,\forall e_{ij}\in E$.

In each iteration, repeat the following two phases:

Proposal phase:

For each unmatched user $u_{i}\in U^{\prime}$:

• •

  User $u_{i}$ selects a user $u_{j^{*}}$ among her unmatched neighbors in $A^{\prime}(u_{i})$ with the maximum weight $w_{ij^{*}}$.

• •

  User $u_{i}$ sends to $u_{j^{*}}$ a matching proposal.

Matching phase:

For a user pair $(u_{i},u_{j})$ that both $u_{i}$ and $u_{j}$ receive proposals

from each other:

• •

  Match $u_{i}$ and $u_{j}$ by updating $x_{ij}=1$ and $U^{\prime}=U^{\prime}\setminus\{u_{i},u_{j}\}$.

• •

  Make $u_{i}$ and $u_{j}$ unavailable for matching with others, by updating $A^{\prime}(u_{k})=A^{\prime}(u_{k})\setminus\{u_{i}\}$ for any $u_{k}\in A^{\prime}(u_{i})$, and similarly for $u_{j}$.

Algorithm 1 is randomized³³3It randomizes in the selection of preferred neighbors in case there are multiple equally best choices in the proposal phase. A way to simplify this and make the algorithm deterministic is to assume that nodes are assigned unique IDs and that a node assigns priority in the case of ties to her neighbor with the highest ID value. This avoids loops and guarantees termination in $O(|E|)$ steps. In the rest of the paper we can assume this deterministic version for Algorithm 1. and can be implemented distributedly: at each time, each user uses local information to choose the unmatched neighbor with the highest weight as her potential matching partner; she will stop once this preference becomes reciprocal, or there are no available unmatched neighbors. This algorithm calculates a matching with total weight at least $1/2$ of the optimum (see [9]). This worst-case approximation ratio of $1/2$ is achieved in a three-edge instance where the middle edge has slightly larger weight than its two adjacent edges, since the greedy matching chooses the middle edge while the optimal matching chooses the two side edges.

Though the approximation ratio of Algorithm 1 is $1/2$ with half efficiency loss in the worst case, this ratio is achieved in the three-edge instance only when the middle edge has slightly larger weight than its two adjacent edges. In a large network instance, given the i.i.d. assumption regarding the choice of the weights, it is improbable that the graph will consist of an infinite repetition of the above special weighted three-edge pattern which leads to the worst-case performance. Hence, we expect the average performance ratio of the greedy matching to be much above $1/2$. We next provide the necessary definitions for our average performance analysis.

By taking expectation with respect to the weights in $W$ that are i.i.d. with a general discrete distribution $Pr(w_{ij}=v_{k})=p_{k},\forall k=1,\ldots,K$, we define the average performance ratio $PR(G)$ of Algorithm 1 for a given graph $G$ as follows:

where $f^{\star}(G,W)$ and $\hat{f}(G,W)$ denote the total weights (i.e., social welfare) under the optimal matching and the greedy matching, respectively, $\{x^{\star}_{ij}\},\{\hat{x}_{ij}\}$ being the corresponding matchings. Since over time the algorithm is repeated for new instances, the numerator and denominator correspond to the time-average of the social welfare obtained by running the greedy and the optimal algorithms, respectively.

We next evaluate the performance ratio for several special forms of practical interest for $G$ that corroborate the excellent performance of the greedy matching, including 2D grids and the more general random graph $G(n,p)$ networks. In the case of random graphs, we must take expectation in (2) over both $G$ and $W$. Besides, we will also prove the sub-linear computation complexity to run Algorithm 1 for these networks.

It is impossible to obtain the exact value of the average total weight $\mathbb{E}_{W}[f^{\star}(G,W)]$ under the optimal matching due to the exponential number of the possible matchings. Instead, we propose a method to compute an upper bound for the denominator $\mathbb{E}_{W}[f^{\star}(G,W)]$ in (2) using a methodology that holds for general graphs. This upper bound will be used to derive a lower bound for the average performance ratio $PR(G)$ in (2) later.

In any graph $G=(U,E)$, each matched edge $e_{ij}\in E$ adds value $w_{ij}$ to the final matching. Equivalently, we can think of it as providing individual users $u_{i}$ and $u_{j}$ with equal benefit $w_{ij}/2$. For any user $u_{i}$, this individual benefit does not exceed half of the maximum weight of its neighboring edges. Using this idea and summing over all users, the total weight of the optimal matching is upper bounded by

By taking expectation over the weight distribution, we obtain the closed-form upper bound of the average total weight.

The proof is given in Appendix A.

We next turn in the calculation of the average total weight of the greedy matching, i.e., the numerator $\mathbb{E}_{W}[\hat{f}(G,W)]$ in (2). In the case of 2D grid networks we cannot directly use dynamic programming since matching users does not divide the grid into sub-grids. Instead, we start by considering the simplest $1\times n$ grid where each user $u_{i}$ locally connects with two adjacent users $u_{i-1}$ and $u_{i+1}$ (except for starting and ending users $u_{1}$ and $u_{n}$). In such linear networks, for notational simplicity we use $e_{i}$ instead of $e_{i,i+1}$ to denote the connection between users $u_{i}$ and $u_{i+1}$, and similarly use weight $w_{i}$ instead of $w_{i,i+1}$. Without loss of generality, we assume that each user facing the same weights of the two adjacent edges assigns higher priority to match with the left-hand-side neighbor. This implies that Algorithm 1 becomes deterministic and returns a unique solution.

We prove that given the weight set size $K$, an edge $e_{i}$ that has the local maximum weight (i.e., $w_{i}>w_{i-1},w_{i}\geq w_{i+1}$ ) and will certainly match in Algorithm 1 can be found within the first $K$ edges of the linear network graph. Further, by considering all the $K^{K}$ weight combinations $\{w_{1},\cdots,w_{K}\}$ of the first $K$ edges and the existence of edge $e_{i}$ that will certainly match, we derive the recursive formula for $\{a_{n}\}$ where $a_{n}$ denotes the average total weight of the greedy matching in the linear graph with $n$ users. An illustrative example for $K=2$ is shown in Fig. 2 and the recursive formula averaged with respect to the probabilities is given by

Based on that, we derive $a_{n}=\frac{p_{1}^{2}v_{1}+(p_{2}+p_{1}p_{2})v_{2}}{2p_{2}+2p_{1}^{2}+3p_{1}p_{2}}n+o(n)$ when $n$ is large by using asymptotic analysis. Similarly, for an arbitrary $K\geq 3$, we can also obtain the general formula for the sequence $\{a_{n}\}$ as a function of $V=\{v_{1},v_{2},\cdots,v_{K}\}$ and $P=\{p_{1},p_{2},\cdots,p_{K}\}$.

Note that a simple extension of the previous result to $n\times n$ grid by dividing it into $n$ sub-grids of size $1\times n$ provides a bad lower bound because all the vertical edges become unavailable to match. Instead, we split the grid network into sub-grids in a way that keeps half of the vertical edges, and then estimate a lower bound of the average total weight. For illustration purpose, we treat the case of weight set size $K=2$, $v_{1}<v_{2}$. Our procedure involves the following three steps (as illustrated in Fig. 3), and it is easy for the reader to generalize for $K>2$.

The above procedure allows us to find a lower bound on the matching obtained by Algorithm 1. This is obtained by i) eliminating from the set of edges that may be matched the vertical edges in step 1 (see Fig. 3), ii) analyzing the greedy matching of the two horizontal linear networks in the resulting $2\times t$ sub-grids (using similar analysis as in (5)), and leaving out the possible matching of the rest vertical edges in step 3. By combining this lower bound for the performance of Algorithm 1 with the upper bound for the optimal matching in (9) we obtain the following bound for the average performance ratio.

The proof is given in Appendix B. Observe that here we consider the case of weight set $V=\{1,2\}$ (‘low’ and ‘high’) and uniform weight distribution $P=\{\frac{1}{2},\frac{1}{2}\}$ for illustration purpose. The analysis can be extended for any possible $V$ and $P$.

In this subsection, we focus on analyzing the parallel running time of Algorithm 1, where a unit of time corresponds to one iteration of the steps of Algorithm 1. Similarly, we start with the simplest $1\times n$ grid. Let $H(u_{i})$ denote the length of the longest chain (sequence of edges) that has non-decreasing weights and starts from $u_{i}$ towards the left or right side. Suppose that $w_{i-1}\leq w_{i-2}\leq\cdots\leq w_{i-H(u_{i})+1}\leq w_{i-H(u_{i})}>w_{i-H(u_{i})-1}$ is such a longest chain. We claim that $u_{i}$ will terminate running Algorithm 1 (i.e., by being matched or knowing that there is no unmatched neighbors) within $H(u_{i})/2$ time. This is easy to see since starting from time 0, the edge $e_{i-H(u_{i})}$ will be included in the total matching in iteration 1, $e_{i-H(u_{i})+2}$ in iteration 2, etc. Hence, in less than $H(u_{i})/2$ steps, all neighbors of $u_{i}$ will have resolved their possible preferences towards users different than $u_{i}$, and subsequently $u_{i}$ will either be matched with one of her neighbors or be left with an empty unmatched neighbor set. As Algorithm 1 terminates when all users make their final decision, if the probability of any user in $G$ having a chain longer than $c\log n$ (i.e., $\max_{u_{i}\in U}H(u_{i})>c\log n$) for some constant $c$ is very small, then the parallel execution of Algorithm 1 will terminate within $O(\log n)$ time with very high probability.

Then, we extend our analysis to the $n\times n$ grid. Note that the number of possible chains that start from any given node $u_{i}$ and have non-decreasing weights is no longer two (toward left or right) as in $1\times n$ grid networks, but exponential in the size of the chain (since from each node there are $4-1=3$ ‘out’ ways for the chain to continue), and such chains now form with non-negligible probability. This problem is not an issue for Algorithm 1 since every node will need to use priorities over ties among neighbors whose edge has the same weight. This significantly reduces the number of possible chains that are relevant to a user’s decisions and we can prove the following proposition.

The proof is given in Appendix C. In conclusion, our distributed matching algorithm has low complexity and provides a great implementation advantage compared to the optimal but computational-expensive centralized matching.

Given $p$ remains a constant, as $n$ increases, each user will have an increasing number of neighbors with the largest possible weight value $v_{K}$. Since such edges are preferred by greedy matching, as $n$ goes to infinity, the greedy matching will almost surely provide the highest possible total matching value of $nv_{K}/2$ ($n/2$ pairs of users with weight value $v_{K}$).

The proof is given in Appendix D. In this result, in the definition of the average performance ration $PR$ we have taken expectation over both $G$ and $W$. Note that the computation complexity is not anymore $O(\log n)$ in this case due to the increasing graph density. An obvious bound is $O(|E|)$ proved in [9]..

In this subsection, we consider that the connection probability is $p=d/n$ and hence each user has a constant average number of neighbors $d(n-1)/n\to d$ as $n$ becomes large. We first prove low parallel complexity for Algorithm 1 as long as each user has a small enough number of neighbors to pair with that depends on the distribution of the edge weights.

The proof is given in Appendix E. Note that this condition is always satisfied when $d<1$ as the weight probability $p_{k}\leq 1$ for any $k$.

Next, we focus on studying the average performance ratio $PR$ for sparse random graphs $G(n,d/n)$. The average total weight of the optimal matching can be upper bounded by (9), which works for any graph. Then, we only need to study the average total weight $\mathbb{E}_{G\sim G(n,d/n),W}[\hat{f}(G,W)]$ of the greedy matching. Note that when matching any graph $G$, we can equivalently view that the weight of any matched edge is equally split and allocated to its two end-nodes. Then we can rewrite the above expression as follows:

where $x_{i}(G,W)$ is half of the weight of the matched edge corresponding to each user $u_{i}$ under the greedy matching.

We cannot use dynamic programming directly to compute the average weight $\mathbb{E}_{G\sim G(n,d/n),W}[x_{i}(G,W)]$ per user in (6) since $G(n,d/n)$ may have loops and it cannot be divided into independent sub-graphs. Given that $n$ is large and assuming $d<1$, then graph $G(n,d/n)$, with very high probability, is composed by a large number of random trees without forming loops. In this case the matching weight $x_{i}(G,W)$ of user $u_{i}$ only depends on the connectivity with other users in the same tree. To analyze $x_{i}(G,W)$, we want to mathematically characterize such trees which turn out to be ‘small’ because $d<1$. Note that, in $G(n,d/n)$, each user has $n-1$ independent potential neighbors, and its random neighbor number follows a binomial distribution $B((n-1),d/n)$ with mean $(n-1)d/n\rightarrow d$, as $n$ becomes large. This binomial distribution can be well approximated by the Poisson distribution $Poi(d)$ (with mean $d$). We define $T(d)$ as a random tree where each node in the tree gives birth to children randomly according to the Poisson distribution $Poi(d)$.

The proof is given in Appendix F. We will show numerically later that the approximation in (7) yields trivial performance gap and remains accurate as long as $d\leq 10$. By substituting (7) into (6), we obtain approximately the average total weight $\mathbb{E}_{G\sim G(n,d/n),W}[\hat{f}(G,W)]$. Hence, it remains to derive the form of $\mathbb{E}_{T\sim T(d),W}[x_{root}(T,W)]$. Given the recursive nature of trees, we are able to use dynamic programming techniques.

The root node may receive multiple proposals from its children corresponding to different possible edge weights in the set $\{v_{1},v_{2},\cdots,v_{K}\}$, and will match to the one (of them) with the maximum weight. We define $y_{k}$, $k\in\{1,2,\cdots,K\}$, to denote the probability that the root node receive a proposal from a child who connects to it with an edge of weight $v_{k}$. Then, by considering all the possible weight combinations of the root’s children, we can compute the probability to match a child with any given weight, using the proposal probabilities $y_{k}$. In a random tree $T(d)$, given the root node is matched with one of its children, the remaining graph can be divided into several sub-trees which are generated from the grand-child or child nodes of the root node. In any case, a sub-tree starting with any given node has the similar graph structure and statistical property as the original tree $T(d)$. Thus, we are able to analytically derive the recursive equations for finding the proposal probabilities $\{y_{k}\}$ for the root node.

The proof is given in Appendix G. Though not in closed-form, we can easily solve (8) using bisection, and then compute the probability that the root node matches to a child with any given weight. Based on that we derive the average matching weight $\mathbb{E}_{T\sim T(d),W}[x_{root}(T,W)]$ of the root for (7) and thus $\mathbb{E}_{G\sim G(n,d/n),W}[\hat{f}(G,W)]$ in (6). Finally, by comparing with (9) under the optimal matching, we can obtain the average performance ratio of Algorithm 1.

Next, we conduct numerical analysis for sparse random graphs with $d<1$ and random graphs with finite $d\geq 1$. To do that by using analytic formulas, we need to approximate the random graph by random trees, and one may wonder if the approximation error is significant (when $d>1$). To answer this question, we consider large network size of $n=10,000$, with edge weights uniformly chosen from the weight set $V=\{1,2\}$ (‘low’ and ‘high’). Our extensive numerical results show that the difference between the simulated average matching weight $\mathbb{E}_{G\sim G(n,\frac{d}{n}),W}[x_{i}(G,W)]$ and the analytically derived average matching weight $\mathbb{E}_{T\sim T(d),W}[x_{root}(T,W)]$ in the approximated tree $T(d)$ is always less than $0.05\%$ when $d<1$ and is still less than $1\%$ even for large $1\leq d\leq 10$. This is consistent with Proposition 6.

Fig. 4 shows the average performance ratio of Algorithm 1, which is greater than $79\%$ for any $d$ value. It approaches $100\%$ as $d$ is small in the sparse random graph regime. Intuitively, when the average neighbor number $d$ is small and users are sparsely connected, both Algorithm 1 and the optimal algorithm try to match as many existing pairs as possible, resulting in trivial performance gap. When $d$ is large, each user has many neighbors and choosing the second or third best matching in the greedy matching is also close to the optimum. This is consistent with Proposition 4 for dense random graphs.

The $G(n,d/n)$ network studied in Section IV assumes users connect with each other with the same probability $p=d/n$, and hence the average performance of Algorithm 1 in $G(n,d/n)$ is characterized by the average neighbor number $d$. However, in practice, the connectivity distribution of users can follow different laws due to the structure of the environment and the D2D communication limitations. To validate our analysis on real scenarios, we run our algorithm on graphs corresponding to realistic mobile user data and compare the numerical results with our analytically derived results for $G(n,d/n)$ using Propositions 6 and 7.

We use the real dataset in [15] that records users’ position information in a three-story university building. We choose three instances in the peak (in terms of density) time from the dataset and each instance contains hundreds of users. For these users, we assume that any two of them can share resources with each other when they are in the same story and the distance between them is less than the D2D sharing range $L$. By setting different values for $L$ the structure of the graph changes and the average number $d(L)$ of neighbors per node increases. In Fig. 5, we show the average matching weight (per user) of the greedy matching versus the average neighbor number $d$ (instead of versus $L$) for the three practical instances of the realistic user network and its $G(n,d/n)$ approximation. We observe that the average matching weight increases in $d$ since increasing $d$ (by increasing $L$) provides more sharing choices for each user and our performance measure obtained for $G(n,d/n)$ approximates well the performance for the realistic network, especially for large $d$.

Our numerical results from the previous section suggest that, as expected, the average matching weight of the greedy matching increases with the D2D sharing range $L$. We wonder whether a large $L$ always benefits resource sharing. In fact, for two users who are connected and share resources via a D2D wireless link, a communication failure may occur due to the long-distance transmission or the mutual interference among different matched pairs. In our experiment, we consider that the resource sharing transmission between any two users fails with a probability that increases in the distance between them based on a practical path-loss model and the number of interfered pairs in proximity [16]. In our simulation experiment, we consider a large number $n=10,000$ of users uniformly distributed in a circular ground cell with radius of $R=1000$ meters and we can adjust the maximum sharing range $L$ inside which two users can apply D2D resource sharing.

In Fig. 6, we depict the average matching weight (per user) of the greedy matching versus the maximum D2D sharing range $L$ for two cases depending on whether or not we consider communication failures. Under communication failures, this weight first increases and then decreases. Intuitively, when the sharing range $L$ is small, each user has few potential users to share resources or interfere and failures occur rarely to be an issue. But when $L$ is large, since most of the neighbors are located remotely and the channels between matched pairs may cross each other, there is a high chance for the algorithm to choose such a remote neighbor to incur large path loss or interference. Then, if communication fails, this results in adding zero value to the total matching. This is in contrast to the case without failures, where the performance of the system is always increasing in $L$.