Competition-Based Device-to-Device Transmission Scheduling to Support Wireless Cloud Multimedia Communications

Abstract

Multimedia applications based on cloud services for mobile devices have recently gained considerable popularity. However, the increasing density of devices leads to a high level of interference, which reduces the performance of wireless communication between devices and cloud. In this paper, we propose a new approach which allows the network to adaptively find a transmission opportunity scheduling strategy by choosing the most valuable transmission request opportunity. In this approach, the transmission request selection strategy is optimized by considering multimedia distortion reduction, hidden node problem, transmission interference, and signal coverage. Simulation results show that the proposed request selecting strategy significantly improves the systems overall data transmission quality by exploring the tradeoff between communication node pair and their neighbor nodes.

1. Introduction

Thanks to the improvement in wireless communication technology, many new multimedia applications based on cloud technology for mobile devices have gained considerable popularity. These applications allow people to communicate with internet via their mobile devices, which is greatly convenient in various areas. On the other hand, the large volume of multimedia communications requested by these applications creates a higher requirement for communication quality of service. However, the increased density of a device-to-device (D2D) system causes more interference, in a channel, which reduces the transmission performance.

In this paper, we propose a new algorithm to improve the data transmission quality (i.e., the data distortion reduction) for a mobile multimedia cloud network (MMCN) in a Cloud-D2D communication fashion. The system model is composed of many mobile device nodes where all the nodes are laid in the same base station's coverage area and share the same channel. Each node has its own position and signal coverage and interference range. The communication between two nodes will cause interference to their neighbor nodes. In Figure 1 we show the MMCN system overview. A device in this system fetches data from cloud via either base station or nearby devices. To reduce the workload of the base station eNB (evolved Node B), D2D technology is applied. In the left bottom we show a D2D communication scenario under coverage of a single base station eNB, where the sharing channel model builds a competition relationship between each node. For example, in this figure, the data sender (star) will cause interference between its neighbors (cross) while sending data to the receiver (square). But there are some idle nodes that can still communicate with each other (round). So, the sender is competing with the cross nodes, but it is not competing with the idle nodes. By using this relationship, we can significantly improve system level data transmission quality, which is defined as the total multimedia distortion reduction per unit time under single eNB coverage.

Figure 1

Cloud-D2D communication system MMCN overview.

Recently, studies on mobile device level communications have significantly put effort on energy efficiency. Researchers in [1] proposed a transmission time control (TTC) scheme to reduce the transmitter energy consumption. Also, an adaptive gain control (AGC) scheme was adopted to make the receiver energy efficient. The paper showed significant energy efficiency improvements on both the sender side and receiver side. Based on the short operational time of mobile devices, researchers in [2] suggested using relay nodes between the source node and the destination node. The authors believed that the proposed solution will provide energy efficient cooperative communications between the transmitters and the receivers. Some of the researchers also believe that it is very hard to obtain huge improvement in traditional layer-based network protocol stack framework. By applying the cross-layer idea to optimize various solutions in different layers (i.e., from APP layer to PHY layer), many new research ideas have been reported. Researchers in [3] proposed a survey of energy efficiency solutions based on the cross-layer resource allocation idea. Because of the resource constraint of the mobile devices (including, but not limited to, battery size, device size, communication bandwidth, and computer power), the author believes energy efficiency is still the most challenging issue in multimedia communications. Researchers in [4] provided a new link selection strategy to improve the energy efficiency in a GMPLS (generalized multi-protocol label switching) network. Though the proposed strategy selection results with high energy efficiency, some researchers show that switching the node between working and sleeping mode also leads to high energy consumption.

Instead of improving energy efficiency, some studies focus on the transmission performance of mobile devices. They also focus on link selection strategy optimization. Authors in [5] improved transmission by implementing joint relay selection and link scheduling. Researcher in [6] evaluated the performance of multicarrier M-ary QAM for wireless high rate transmission requirement. The paper combines fading compensation and diversity reception to achieve high reliability on high bit rate data transmission. Also, many researches are focused on the improvement of existing protocols. Researchers in [7] proposed a MB-OFDM UWB communication system over a realistic multipath-fading framework to improve the throughput and transmission range. Their paper, based on IEEE 802.15.3a, was trying to optimize the performance of a UWB communication system. It also mentioned the concept of a wireless personal area network (WPAN) and pointed out that the applications will increase rapidly. Some analysis reports were also considered during our research. Performance analysis of IEEE 802.15.4 is reported in [8]. This research runs standard operating of IEEE 802.15.4 in the nonbeaconed mode and examined the latency and packet loss rate by changing some key parameters. By considering the signal interference, [9] provided an optimal rate selection to improve the transmission rate.

Also, many studies now start solving the maximum coverage problem by considering interference and cooperation issues. Based on current cellular networks, Researchers in [10] proposed a new interference management strategy. Based on cellular network property, this paper combined the conventional mechanism and its own δ D-interference limited area (ILA) control scheme to manage the interference from cellular networks to D2D system. In that paper, the wireless communication channel resource was allocated on the uplink within cellular network frequency range. Since this resource has been already allocated, an algorithm to insure limited interference to original communication should be provided. Similar uplink resource allocation was found in [11], which provided an analytical characterization-based resource sharing strategy to avoid the interference. The authors believed that, in multiuser cellular system, it is very hard for the distributed algorithm to guarantee the original transmission quality while allocating resources in D2D network. Instead of using any distributed strategy, they used the base station eNB as a central node and run global optimization on it. Instead of allocating channels, the authors in [12] used power control to reduce the interference caused by D2D communication with remarkable throughput improvement.

The D2D discussion is not only focused on a single hop scenario, but also on D2D relay scenarios. As reported in [13], by using the D2D technology in a traditional cellular network, one can improve both the network throughput and the network coverage. The authors showed a higher percentage of the cell edge throughput capacity by applying Monte Carlo simulation techniques in both uplink and downlink. Even through the relays can improve coverage, more research works favor improving transmission performance. Researchers in [14] pointed out that we need to consider the tradeoff between multichannel diversity and multicast gain. The authors started with adjusting the number of relays and building the connection with minimal time-frequency resource cost. By adaptively selecting the number of cooperative relays, they enhanced the retransmission throughput. Results showed high improvement in resource utilization. Researchers in [15] analyzed the transmission rate of D2D network and deduced their own relay selection rule. Based on this rule, they apply KM algorithm and greedy algorithm to select different relay nodes. Their simulation result shows that KM algorithm shows high performance in relay selection.

Fundamentally different from existing research, we focus on space utilization in wireless communication. By applying multitransmission technology in transmission request selection, we intend to achieve a higher transmission performance based on a new transmission efficiency evaluation. We begin by mathematically formulating the competing relationship between neighbor nodes into a transmission cost and transmission gain model. By using this model, we optimize the transmission request selection strategy by adapting the cost and gain. The complexity of the algorithm is also being considered.

The rest of this paper is organized as follows. In Section 2, we mathematically formulate the problem as a constraint optimization problem. In Section 3, the constraint and objective function are analyzed. In Section 4, we show numerical simulation results and in Section 5 we draw conclusions. Table 1 summarizes the symbols used in the equations in this paper.

Table 1

Symbol definition.

Symbol	Notation
$S_i$	Transmission request selection strategy in time slot i
$D_{\text{total}}$	Overall transmission quality
$\mathrm{\Gamma }({\delta }_m,{\delta }_n)$	Interference check function
$\{{\delta }_j\}$	Transmission request state set
${\alpha }_j$	Sender node index
${\beta }_j$	Receiver node index
${\omega }_j$	Approve state
$D_j$	Transmission quality gain
Range $(x,y)$	Signal coverage check function
$\mathrm{\Phi }({\delta }_j)$	Silence quality
$\mathrm{\Delta }({\delta }_j)$	Transmission efficiency

2. Problem Statement

In this paper, our objective is to get the overall system level transmission quality as high as possible in such a single eNB D2D communication environment. The algorithm should work well even though the node density is very high. Here, we assume the data packet length is the same and the routing strategy of each packet is known. Also, a time slot has been defined as the time cost of transmitting one data packet, as the physical layer modulation and coding strategies are determined. The optimization process is to achieve the highest quality of transmission with lowest overall distortion. Thus the overall problem can be formulated as a transmission request selection problem in each time slot with s signal interference constraint.

Let $S_i$ denote the transmission request selection strategy in time slot i, let N denote the count of time slot, and let $D_{\text{total}}$ denote the overall transmission quality; then the overall problem can be formulated as follows:

$$\begin{array}{cc}& {\left\{S_i\right\}}_{i\in 1,\dots ,N}=\arg \hspace{0.17em}\max \left\{D_{\text{total}}\right\}.\end{array}$$

(1)

Let set $\{{\delta }_j\}$ denote the transmission request state set in a certain time slot and let function $\mathrm{\Gamma }({\delta }_m,{\delta }_n)$ denote the interference between two transmission requests; then the interference constraint can be formulated as follows:

$$\begin{array}{cc}& \forall {\delta }_m,{\delta }_n\in \left\{{\delta }_j\right\},\hspace{1em}\mathrm{\Gamma }\left({\delta }_m,{\delta }_n\right)=\mathrm{0}.\end{array}$$

(2)

In the next section, we will analyze the optimization problem and provide our solution to optimize transmission request selection.

3. Proposed Solution

For a transmission request state ${\delta }_j$ , let ${\alpha }_j$ denote the sender, ${\beta }_j$ the destination, ${\omega }_j$ the approval state, and $D_j$ the transmission quality gain of this request which can be determined from application layer; then the request state can be formulated as follows:

$$\begin{array}{cc}& {\delta }_j=\left(\left({\alpha }_j,{\beta }_j\right),{\omega }_j,D_j\right).\end{array}$$

(3)

Let function $\text{Range}(x,y)$ denote whether node x and node y will cause interference if they are in working mode at the same time. Two transmission requests are not affected by each other, if and only if

• (a)

at least one of the requests is not approved,

(b)

any node in one of the requests is not in the range of the nodes in the other request.

According to the two conditions above, we have

$$\begin{array}{l}\mathrm{\Gamma }\left({\delta }_m,{\delta }_n\right)=\left({\omega }_n\wedge {\omega }_m\right)\\ \hspace{1em}\wedge (\text{Range}\left({\alpha }_m,{\alpha }_n\right)\vee \text{Range}\left({\alpha }_m,{\beta }_n\right)\\ \hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{0.17em}\vee \mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Range}\left({\alpha }_n,{\beta }_m\right)\vee \text{Range}\left({\beta }_n,{\beta }_m\right)).\end{array}$$

(4)

Based on the assumption that wireless communication needs a clear channel environment, we propose a factor named silence quality (SQ) to evaluate the transmission cost. During the transmission, some nodes keep quiet to guarantee that the bit error rate is at a low level for neighboring nodes. This means that the transmission requests related to these nodes will be blocked at the same time. Here we define SQ as the overall transmission quality of the blocked requests while certain transmission request is being handled. Let $\mathrm{\Phi }({\delta }_j)$ denote the SQ of ${\delta }_j$ and let M denote the count of current request. Then we have

$$\begin{array}{l}\mathrm{\Phi }\left({\delta }_j\right)=\sum _k{D}_k\times (\text{Range}\left({\alpha }_j,{\alpha }_k\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\vee \text{Range}\left({\alpha }_j,{\beta }_k\right)\vee \text{Range}\left({\beta }_j,{\alpha }_k\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\vee \mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Range}\left({\beta }_j,{\beta }_k\right)).\end{array}$$

(5)

Let $\mathrm{\Delta }({\delta }_j)$ denote the efficiency of transmission request j; according to (3) and (5), the efficiency would be

$$\begin{array}{cc}& \mathrm{\Delta }\left({\delta }_j\right)=\frac{D_j}{\mathrm{\Phi }\left({\delta }_j\right)}.\end{array}$$

(6)

Finally, we can see that the relationship between each transmission request of neighbor nodes is a competing relationship. Thus, we can use a greedy algorithm combined with an interference constraint to optimize the request selection strategy. Algorithm 1 shows the details of our proposed optimization process.

Algorithm 1: Quality-compete transmit request selection.

Define Input:

Transmission request count  N

Node count  M

Transmission request array   $\delta [N]$

Signal coverage array   $Range[M,M]$

Efficiency Calculate:

Init cost array   $\mathrm{\Phi }[N]=zeros(N)$ ;

Init efficiency array   $\mathrm{\Delta }[N]=zeros(N)$ ;

For   $j=\mathrm{1}:N$   do

  Sender = $\delta [j]·$  GetSender();

  Receiver = $\delta [j]·$  GetReceiver();

  For   $k=\mathrm{1}:N$   do

    If   $k==j$   then

     Continue();

    End if

    TestSender = $\delta [k]·$  GetSender();

    TestReceiver = $\delta [k]·$  GetReceiver();

    If   $Range[Sender,TestSender]==true$   or

      $Range[Sender,TestReceiver]==true$   or

      $Range[Receiver,TestSender]==true$   or

      $Range[Receiver,TestReceiver]==true$   then

       $\mathrm{\Phi }[j]\hspace{0.17em}+=D[k]$ ;

    End if

  End for

   $\mathrm{\Delta }[j]=\frac{\delta [j]·GetQualityGain()}{\mathrm{\Phi }[j]}$ ;

End for

Apply Greedy Algorithm:

Sort   $\delta [N]$   by   $\mathrm{\Delta }[N]$

For   $m=\mathrm{0}:N$   do

   $IfApprove=true$ ;

  For   $n=\mathrm{0}:m$   do

    If   $\mathrm{\Gamma }(\delta [m],\delta [n])==true$   then

      $IfApprove=false$ ;

     Break;

    End if

  End for

   $\delta [n]·Approved=IfApprove$ ;

End for

As shown in the pseudocode above, our algorithm has two major steps. First, for each transmission request, we calculate their transmission efficiency in order to rank them. The profit is their transmission quality gain, and the cost is the sum of transmission quality of their neighbors. Second, we apply greedy algorithm on the result of sorted transmission efficiency. Here we use the available nodes (we can also treat the available nodes as space resource) as the budget of the greedy algorithm. Then we can get a set of transmission requests as our optimized solution. These transmission requests are optimal because they are approved by eNB and run at the same time without any interference.

4. Overhead Analysis

In this section we discuss the potential overhead associated with the proposed approach. The essential overhead is twofold: the extra computing complexity and the increased communication information exchange. In fact, any optimization algorithm will take some computing time. Since the time restriction of our problem is very high, we need to provide our solution with reasonable time limit in practice. The overall time consumption is the sum of computing time and data transmission time. Our proposed algorithm is a global optimization based on a centralized node eNB, which is a centralized node with relatively high computer capability. Compared with the data transmission time, the computing time is very short which can be approximately neglected. So, if we can have a good solution on improving the transmission performance, the limited computing time should not be a major problem. However, the computing time will be a linear function with the complexity of the algorithm, so we still need to consider how the time complexity goes when request count increased. We will discuss this problem in next section.

On the other hand, since this is a global optimization, we need the local and neighboring information which is distributed on each node to be transmitted to the central node eNB. These data transmissions would cause additional network workload which will reduce the performance. Our problem is to address efficient multimedia D2D issue, which aims at solving the huge video data transmission problem. Here each device will have several transmission requests and each transmission request is related to bunch of data packets. Compared with these data packets, our optimization only required the source, destination, and quality information for each request. This means that we can group many transmission requests information in one time frame, and this information can be used in optimizing a mass of packet transmission requests. So, the traffic we used in exchanging data packets information would be in a very low rate compare with overall D2D multimedia traffic load. If we improved the network transmission efficiency, the additional traffic load cause by optimization can be ignored.

5. Simulation

In this section we perform numerical simulation to show the performance of our proposed algorithm. The performance is evaluated in terms of distortion reduction. The complexity of the algorithm is also studied. The simulation environment is set up as follows. All nodes are laid on a 2D coordinate system. The position of each node is known before optimization. The transmission environment is stable and clean, so the bit error rate can be regarded as 0. Each node has one transmission request that needs to be approved. The packet length of each request is the same and will start transmission at the same time. The transmission requests in different time slots have different distortion reductions and destinations. For comparison, we also present two algorithms, the Best Node Only (BNO) algorithm and the Exhaustion algorithm.

Figure 2 shows the parallel node count that works in each time slot. Since the BNO algorithm only allows one transmission request in one time slot, in each time slot only one packet is transmitted. This causes severe waste in space domain. In fact, when one transmission request is granted and running, there is a very high possibility to allow some other transmission request working concurrently, as long as these transmission requests are not in the interference range to each other. On the other hand, our algorithm and the Exhaustion algorithm allow several transmission requests to work at the same time, which improves the usage of wireless transmission space. Since our solution is based on greedy algorithm, the optimization sometimes does not always perform the same as the best solution which is proved by Exhaustion algorithm (e.g., time slot 3, 7, 9, 10). Also, more request transmission concurrently does not necessarily mean higher performance gain. The transmission performance is a weighted combination of request count and transmission quality of each request. We will discuss it in next several paragraphs.

Figure 2

Transmission node pair count over time.

Figure 3 shows the average distortion reduction in each time slot. Since the BNO always selects the transmission request with highest transmission quality, we can see that the average distortion reduction is much higher. The other two algorithms guarantee concurrently transmission, which means some of the average transmission request's quality is reduced due to granted services of some other low quality transmission request. However, these low quality transmission requests do not cause any interference to the major transmission request. Despite such quality degradation impacts, the overall transmission quality would be still increased. After analyzing the average transmission quality, we move on to the systems overall transmission data.

Figure 3

Average distortion reduction over time.

Figure 4 shows the systems overall distortion reduction in each time slot. As we discussed above, although the average distortion reduction is low, Exhaustion algorithm and our algorithm produced a higher overall transmission performance which allows for multiple concurrent transmissions. Also, the Exhaustion algorithm provides the best solution since it searches all the possible choices. Contrarily, the BNO algorithm can only produce a lower performance. Also we can see in this figure that the transmission quality of the Exhaustion algorithm and our algorithm is changed a lot from time slot to time slot. These changes are caused by the individual property of the transmission request in each time slot. If we combine Figure 2 with Figure 4 together we can see that the overall transmission quality has a high relationship with the number of current working transmission request in that time slot. If we focus on time slot 9, we can see that even though our algorithm has higher concurrent transmission request (5 in time slot 9), the overall transmission quality is still lower than Exhaustion algorithm (which has 4 concurrent transmission requests in time slot 9).

Figure 4

Transmission quality over time.

In Figure 5, the overall simulation results show that our algorithm and the Exhaustion algorithm produce a higher potential performance gain than the BNO algorithm. Compared with the Exhaustion algorithm, our algorithm has 98% performance gain. So we can see that, though it is not the best solution, our algorithm still provides a very high transmission quality for this network.

Figure 5

Overall transmission quality.

Our problem is based on D2D wireless multimedia communication quality optimization; we also performed some studies on device energy consumption. The energy performance simulation results are shown in Figure 6. Because the BNO algorithm only selects the transmission request with the most valuable data packet to transmit and dropping other transmission requests, the energy efficiency is about 30% higher than the other two algorithms. Comparing our algorithm and the Exhaustion algorithm, we found they have very close energy efficiencies. The energy efficiency here that we have shown is the system overall energy efficiency. If we focus on the energy efficiency of one single node, the energy efficiency issue will be different. Most of the time, mobile device such as smart phone will pay more attention on quality of service performance than energy saving. However, if the user needs to work in energy saving mode, the algorithm selection can be switched for different requirements.

Figure 6

Energy efficiency.

The complexity of the Exhaustion algorithm is in the $O({\mathrm{2}}^n)$ level, where n refers to the request count. On the other hand, the complexity of our algorithm is in the $O(n^{\mathrm{2}})$ level. Figure 7 shows the time cost of each algorithm after it runs once. In this figure, we can see that when the request count is over 25, the time consumption of Exhaustion algorithm is increased quickly. When transmission request is over 30, the time consumption is thousands of times of the other two algorithms. In addition, in the implementation situation, every central node needs to handle hundreds to thousands data transmission requests. Then the computing complexity is inconceivably high. As we discussed in Section 4, though the computing speed of the central node is not a major issue, it still cannot afford such a high computation workload. Even though Exhaustion algorithm provides a better optimization result in terms of overall transmission quality gain, it is not a practical solution in implementation.

Figure 7

Algorithm time cost.

6. Conclusion

In this paper we focused on the wireless multimedia traffic bottleneck of the cloud applications in MMCN and proposed a new transmission request selection approach to improve multimedia transmission quality in wireless Cloud-D2D communication systems. To select the best transmission scheduling strategy at the eNB side, we built a new mathematical model to provide the competition relationship between each transmission request. The signal interference constraint was also considered in such modeling. We also analyzed the energy efficiency and computational complexity of the algorithms in the performance study. Simulation results demonstrated that our algorithm improved the multimedia transmission quality significantly, which provides a new way for solving the high volume of wireless traffic problem caused by cloud multimedia applications.