Energy-Aware Fast Interest Forwarding for Multimedia Streaming over ICN 5G-D2D

Abstract

By providing extremely low delivery latency, very high data rate and significant improvement on network capacity, 5G wireless communications have paved the way for introducing high quality multimedia services such ultra HD videos into mobile Internet. The new emerging multimedia applications further spurs the ever growing mobile data traffic and diverse quality of service requirements, which has motivated the need to explore new data delivery paradigms and network architectures. Recently, the combined use of device-to-device (D2D) and information-centric networking (ICN) has been shown to be a promising approach for wide range of multimedia applications in 5G. However, a critical issue is how to select appropriate Interest forwarders in order to fast discover nearby content provider while remains low energy consumption. In this paper, we propose an energy-aware fast Interest forwarding scheme (EAFF) for multimedia streaming over ICN 5G-D2D. We firstly formulate the Interest forwarding problem to jointly optimize the energy consumption and forwarding coverage, and prove it to be NP-hard but submodular and monotonous. Then we propose a greed-based distributed forwarder selection algorithm which enables each node individually determines the next-hop forwarders during the Interest forwarding process. We also conduct a series of simulation tests to show that our proposed method achieves dramatically performance improvement with the respect to state-of-art solutions.

1 Introduction

The increasing wireless bandwidth and ubiquitously network accessing provided by the incoming of 5G [1,2,3] have further spurred the explosive growth of high quality video streaming applications such as ultra HD video [4] in mobile Internet. According to the VNI report of CISCO [5], the traffic of mobile video will conquered the 70% of the total mobile traffic. Due to the on-demand and bandwidth hogging features of video streaming, the rapid expanding of video traffic greatly challenges the backhaul capacity and require new technologies to further improve the backhaul efficiency. Device-to-Device (D2D) communications [6,7,8] enable mobile node directly communicate with other to offload traffics to edge and alleviate the pressures of backhaul networks, hence becoming a promising technology to cope with the growing demand of multimedia applications over future 5G networks.

However, if we still use the IP network as our underly architecture, which is originally designed for host communication instead of content distribution, current solutions such as traditional P2P [9] requires building overlays to distribute the video content, which introduces extra computation and communication costs. Besides, with the increasing scale of end users, P2P system also face the scalability issues due to the overlay maintenance cost. To handle the shifting of network function and provide efficient content sharing in future 5G network, recently emerged information-centric networks (ICNs) [10] redesign the network architecture by addressing the content rather than host, which not only provides efficient data sharing but also enables 5G-D2D targets including mobility, heterogenous accessing and multihoming. Hence, ICN has become a promising technologies for 5G-D2D scenarios [11, 12]. As Fig. 1 shows, in ICN 5G-D2D, each nodes equips with D2D communication interface and maintains three data structures: content store (CS), pending interest table (PIT) and forwarding information base (FIB). The receiving node of interest message firstly checks its CS which contains the local caching content. If Interest hits in CS, the receiving node returns the content directly, otherwise, it will checks the PIT. For Interest hits in PIT, the node will record incoming interface of Interest in PIT and then discard it. Otherwise, a new entry in PIT will be created for this Interest and node sends out Interest according to FIB (maintains the mapping between name prefix and next-hop). When the requested content flows back, the intermitted nodes can proactively cache the passing data into local CS in order to serve future same requests, which intuitively reduce the deliver latency as the content is already cached nearby.

As multimedia streaming requests (referred as Interests) in ICN is routed by name, the content lookup efficiency heavily relies on Interest forwarding strategy. Current solutions in D2D environment can be classified into unicast/broadcast-based methods. Unicast-based methods forward the Interest message to single next-hop node by maintaining the routing information. For instance, mobile nodes in RUFS [13] exchange the recent searching success information and use it to construct the neighbor satisfied list (NSL). For Interest receiving node that the requested content in not in its CS, it will forward Interest to next hop according to the maintained NSL. Our previously work PaFF [14] defines nodes with similar playback and movement behavior as cooperative partners and build high preferred content table (HPCT) by collecting the caching status of cooperative partners. Based on HPCT, a unicast forwarding strategy is proposed to fast locate user demand content. However, due to the high dynamic of mobile environment, mobile nodes in unicast-based methods need to frequently exchange routing information about content in order to maintain the validation of routing information, which quickly exhausts the battery life of energy constraint mobile device. Mobile nodes in broadcast-based methods broadcast Interest message to all one-hop neighbors. For instance, VNDN proposed in [15] employs a geo-based forwarding strategy which choose the neighbors with farthest distance as the forwarders to broadcast Interest. However, this solution requires mobile nodes wait a random delay before sending Interest, which results in extra delivery latency and it is difficult to discover the nearby content provider due to the limited broadcast coverage. As a consequence, to enable ICN in mobile environment with high dynamic and energy constraints, it is necessary to design light weight Interest forwarding strategy with fast content lookup low energy consumption.

Fig. 1.

An illustration of content sharing over information centric 5G-D2D

In this paper, we propose an energy-aware Interest forwarding strategy (EAFF) for ICN 5G-D2D, which select limited numbers of nodes as forwarders in order to fast routing interest to provider while saving energy costs. Specifically, the main contributions of this paper are:

First, we model and formulate the Interest forwarding problem to jointly minimize the energy consumption and searching coverage. And we prove the problem is NP-hard and corresponding objective function is submodular and non-decreasing.

Second, based on the forwarding problem we formulated, we further propose a greedy-based distributed forwarder selection algorithm to choose forwarders with higher probability discover the requested content and larger residual battery lifetime.

Third, we also conduct a series of simulation test to validate the superiority of EAFF in terms of the delay in finding data, energy consumption and number of disseminated Interest with respect to state-of-art solutions.

The rest of the paper is organized as follows, Sect. 2 formulates the forwarder selection problem. Section 3 present the detail design of forwarder selection algorithm. Section 4 conduct a series simulation tests to validate the superiority of proposed algorithm. Section 5 concludes the paper and discuss the future works (Table 1).

Table 1. Update and conversion rate among states

2 Problem Formalization

We consider N mobile nodes communicate with each other via 5G-D2D connections with given topology, which can be modeled as an undirected graph $\mathcal {G}=\left( \mathcal {V},\mathcal {E}\right)$, where $\mathcal {V}=\{v_1, v_2, v_3, \ldots , v_n\}$ is the set of mobile nodes in networks. $\mathcal {E}=\{\left( v_i,v_j\right) |v_i,v_j \in \mathcal {V}\}$ denotes the set of connections among nodes in $\mathcal {V}$. In 5G-D2D environment, two nodes will have connection, i.e., $\left( v_i,v_j\right) \in \mathcal {V}$ only when they are in the communication range of each other, namely $v_i \in \mathcal {N}\left( v_j\right)$ and $v_j \in \mathcal {N}\left( v_i\right)$, where $\mathcal {N}\left( v_j\right)$ and $\mathcal {N}\left( v_i\right)$ denote the set of one hop neighbours of $v_i$ and $v_j$, respectively. By leveraging the broadcasting feature of wireless channel, the interest packets can be received by all neighbors, i.e., $\mathcal {S}\left( v_i\right)$ the receiving node set of $v_i$ is equal to $\mathcal {N}\left( v_i\right)$. In this context, we define the forwarding cover relationship between two nodes and forwarding coverage of one node as follows:

Definition 1

We say node $v_i$ forwarding covers $v_j$ if $v_j \in \mathcal {N}\left( v_i\right)$. Hence, the forwarding coverage of $v_i$ is $\mathcal {N}\left( v_i\right)$ and the size of forwarding coverage of $v_i$ is defined by $|\mathcal {N}\left( v_i\right) |$ the cardinality of $\mathcal {N}\left( v_i\right)$. Accordingly, $\mathcal {N}\left( \mathcal {V}_m\right)$ the forwarding coverage of node set $\mathcal {V}_m\left( \mathcal {V}_m\subset \mathcal {V}\right)$ can be also defined as union set of $\mathcal {N}\left( v_j\right)$ $\left( v_i \in \mathcal {V}_m\right)$, i.e., $\mathcal {N}\left( \mathcal {V}_m\right) =\cup _{v_i\in \mathcal {V}_m}\mathcal {N}\left( \mathcal {V}_i\right)$.

2.1 Optimization Problem

The main goal of Interest forwarding is to fast discover the potential provider while maintains low network resource consumption. According to the Definition 1, as the relay nodes of interest message forwarding covers all its one-hop neighbours and data can be returned immediately when relay nodes forwarding covers a content provider of corresponding data. Intuitively, the more forwarders chosen, the higher probability of discovering the requested content in next hop. And the content can be definitely found once the forwardingcoverage of forwarder set $\mathcal {V}_{f_i}$ of source i equal to the whole node set, namely $\mathcal {N}\left( \mathcal {V}_{f_i}\right)$, as Fig. 2(a) shows. However, one mobile node may receive repetitive interest message from same source when it covered by multiple forwarders, as Fig. 2(b) illustrates. According to the design idea of NDN, such redundancy interest will be discard, which not only makes no contribution to efficiency of content lookup but also consumes precious energy resource of mobile devices. Therefore, it is necessary to limit the size of forwarder set while forwarding covers as much node as possible. Another critical issue is mobile nodes in 5G-D2D consume their own battery life to forward the receive Interest message, choosing node with low remaining battery lifetime may accelerate the battery running out, which may not preferred by mobile users. Therefore, it is also necessary to take the remaining battery lifetime into consideration when design forwarding strategies.

Fig. 2.

(a) The forwarding coverage equals to the whole networks; (b) One node receives redundancy Interest from multiple forwarders

Based on above discussions, the optimization problem of interest forwarding in 5G D2D scenarios can be formulated as follows

$$\begin{aligned} \mathbf {min}&\quad \sum \limits _{v \in \mathcal {V}_{f_i}}\frac{1}{r_v} \end{aligned}$$

(1)

$$\begin{aligned} \mathbf {s.t}&\quad \cup _{v \in \mathcal {V}_{f_i}}\mathcal {N}\left( v\right) =\mathcal {V} \end{aligned}$$

(2)

where $r_v$ denotes the residual battery lifetime of mobile node v. The reason of forming optimization problem in such way can be explained as follows: $r_v$ can be considered as the cost of choosing node v as the forwarder. As a result, node with lower battery lifetime will have higher cost, and the objective function of (1) indicates the total cost of choosing set $\mathcal {V}_{f_i}$ as the forwarding set. Hence, in order to minimize the Eq. (1) under the constraints Eq. (2), forwarding set $\mathcal {V}_{f_i}$ should contains fewer nodes which has higher battery lifetime and forwarding coverage.

According to the form of above optimization problem, we have following proposition:

Proposition 1

The proposed optimization problem (1)(2) is NP-hard.

Proof

We consider a special case of Eq. (1) when all $r_v\left( r_v \in V_f\right)$ are equal to 1, this special case can be formed as follows:

$$\begin{aligned} \mathbf {min}&\quad |\mathcal {V}_{f_i}|\end{aligned}$$

(3)

$$\begin{aligned} \mathbf {s.t}&\quad \cup _{v \in \mathcal {V}_{f_i}}\mathcal {N}\left( v\right) =\mathcal {V} \end{aligned}$$

(4)

where the $|\mathcal {V}_{f_i}|$ is the cardinality of $\mathcal {V}_{f_i}$. The optimization problem (3)(4) is a set cover problem, which has already been proved as NP-hard [16]. Therefore, the NP-hardness of (1)(2) is proven.

To solving this NP-hard problem (1)(2), a possible way is traversing all subset of $\mathcal {V}$, as there are $2^\mathcal {V}$ subsets and therefore the complexity of this algorithm is $O\left( 2^\mathcal {V}\right)$, which is not a polynomial-time algorithm. Besides, it is also require each source node have the knowledge of global topology of $\mathcal {G}$, which is unrealistic in D2D communication environments. Hence, we separate the forwarding set selection problem into a distributed optimization problem which enable each selected forwarders individually choosing next-hop forwarders according to the 2-hop neighbors information. This is mainly because two-hop neighbor information can be easy obtained since mobile device constantly broadcast the Hello message to detect the one-hop neighbors in communication range. The problem of select next-hop forwarders at each forwarder e can be formed as follows:

$$\begin{aligned} \mathbf {min}&\quad \sum \limits _{v \in \mathcal {V}_{f_e}}\frac{1}{r_v} \end{aligned}$$

(5)

$$\begin{aligned} \mathbf {s.t}&\quad \cup _{v \in \mathcal {V}_{f_e}}\mathcal {N}\left( v\right) =\mathcal {N}\left( \mathcal {N}\left( e\right) \right) \end{aligned}$$

(6)

where $\mathcal {V}_{f_e}$ is the next-hop forwarder set of e, $\mathcal {N}\left( \mathcal {N}\left( e\right) \right)$ denotes the two-hop neighbours of e. The optimization problem (5)(6) indicates each forwarder should choose a number of nodes as forwarders that forwarding covers its two-hop neighbors. Intuitively, the solution of optimization problem (1)(2) can be approximated by the recursion of optimization (5)(6).

Although similar to the optimization problem (1)(2), the distributed forwarder selection problem (5)(6) is still NP-hard as the two-hop cover set problem can be considered as a special case of this problem, a near optimal solutions still can be derived in polynomial time due to the submodularity and monotonicity of (5).

Theorem 1

The objective function of optimization problem (5)(6) is submodular and nondecreasing.

Proof

Let two set $\mathcal {V}_a, \mathcal {V}_b \in \mathcal {V}$, $z\left( \mathcal {V}_a\right) =\sum \limits _{v\in \mathcal {V}_a}\frac{1}{r_v}$ and $z\left( \mathcal {V}_b\right) =\sum \limits _{v\in \mathcal {V}_b}\frac{1}{r_v}$, we consider following two cases:

 

Case 1: :

If $\mathcal {V}_a\bigcap \mathcal {V}_b=\emptyset$, namely $z\left( \mathcal {V}_a\bigcap \mathcal {V}_b\right) =0$, we have

$$\begin{aligned} \begin{aligned} z\left( \mathcal {V}_a\right) +z\left( \mathcal {V}_b\right)&=\sum \limits _{v\in \mathcal {V}_a}\frac{1}{r_v}+\sum \limits _{v\in \mathcal {V}_b}\frac{1}{r_v} =\sum \limits _{v\in \mathcal {V}_a\bigcup \mathcal {V}_b}\frac{1}{r_v}=z\left( \mathcal {V}_a\bigcup \mathcal {V}_b\right) \\&=z\left( \mathcal {V}_a\bigcup \mathcal {V}_b\right) +z\left( \mathcal {V}_a\bigcap \mathcal {V}_b\right) \end{aligned} \end{aligned}$$

(7)

Case 2: :

If $\mathcal {V}_a\bigcup \mathcal {V}_b\ne \emptyset$, according to the inclusion-exclusion principle of two sets, we have

$$\begin{aligned} \begin{aligned} z\left( \mathcal {V}_a\bigcup \mathcal {V}_b\right)&=\sum \limits _{v\in \mathcal {V}_a\bigcup \mathcal {V}_b}\frac{1}{r_v} =\sum \limits _{v\in \mathcal {V}_a}\frac{1}{r_v}+\sum \limits _{v\in \mathcal {V}_b}\frac{1}{r_v}-\sum \limits _{v\in \mathcal {V}_a\bigcap \mathcal {V}_b}\frac{1}{r_v}\\&=z\left( \mathcal {V}_a\right) +z\left( \mathcal {V}_b\right) -z\left( \mathcal {V}_a\bigcap \mathcal {V}_b\right) \end{aligned} \end{aligned}$$

(8)

 

Therefore, for both cases, we have

$$\begin{aligned} z\left( \mathcal {V}_a\right) +z\left( \mathcal {V}_b\right) =z\left( \mathcal {V}_a\bigcup \mathcal {V}_b\right) +z\left( \mathcal {V}_a\bigcap \mathcal {V}_b\right) \end{aligned}$$

which satisfies the definition of submodular set function [17] and therefore prove the submodularity of Eq. (5).

For $\forall \mathcal {V}_a\subseteq \mathcal {V}$ and $\forall k\in \mathcal {V}/\mathcal {V}_a$, we have

$$\begin{aligned} \begin{aligned} z\left( \mathcal {V}_a\bigcup \{k\}\right) -z\left( \mathcal {V}_a\right)&=\sum \limits _{v\in \mathcal {V}_a\bigcup \{k\}}\frac{1}{r_v}-\sum \limits _{v\in \mathcal {V}_a}\frac{1}{r_v} =\sum \limits _{v\in \mathcal {V}_a}\frac{1}{r_v}+\frac{1}{r_k}-\sum \limits _{v\in \mathcal {V}_a}\frac{1}{r_v}\\&=\frac{1}{r_k}>0 \end{aligned} \end{aligned}$$

(9)

hence, Eq. (5) is nondecreasing.

3 Distributed Energy-Aware Fast Forwarding Algorithm

According to the discussion above, the forwarding set selection problem of a given source i can be solved by a decentralized fashion, namely, forwarders in each hop can decide the next-hop by solving the optimization problem (5)(6), which only require two-hop neighbor information. Since Eq. (5) is submodular and monotonous according to Theorem 1, a 1-$\varepsilon$ optimal solution that can be found in polynomial time by greed-based method [17]. Therefore, we propose a greed-based distributed energy-aware fast forwarding algorithm as following.

To be aware of the two-hop neighbours and residual battery lifetime of one-hop neighbors, mobile nodes periodically exchange the set of neighbours and residual battery lifetime by smuggling such information into hello message. Once a mobile node is selected as the forwarder¹, it will individually select forwarders from one-hop neighbors in order to minimize the objective (5) with constraint (6). To search the next-hop forwarder by greed method, we first introduce the concept of weighted coverage as follows:

$$\begin{aligned} \mathcal {D}_v=r_v|\mathcal {N}\left( v\right) | \end{aligned}$$

each node calculate the $\mathcal {D}_v$ by collecting the “hello” message of its neighbour nodes and rank its neighbours according to the descending of value of $\mathcal {D}_v$. Let $C\left( i\right)$ as the candidate forwarder set of i and a candidate forwarder information base (CFIB) will be created, which maintains the neighbour nodes information of one-hop nodes.

Mobile node i first select the one-hop neighbour v with maximum value of $\mathcal {D}_v$ and update CFIB and $C\left( i\right)$ according to following process: (1) Omit v from CFIB and $C\left( i\right)$; (2) Omit all nodes in $\mathcal {N}\left( v\right)$ from the neighbor node set of other nodes in CFIB; (3) Re-sort the node in $C\left( i\right)$ according to $\mathcal {D}_v$.

Then the forwarder will continue select the node with maximum value from $C\left( i\right)$ and update the CFIB and $C\left( i\right)$ again. The above process will repeat until the constraint (6) satisfied, and the selected nodes will be considered as the forwarders. The pseudo code of the algorithm is given as Algorithm 1.

Table 2. Simulation parameter setting

3.1 Complexity Analysis

According to the pseudo code of algorithm, the time complexity partially depends on number of selected forwarders $|\mathcal {V}_{f_e}|$ as the algorithm will execute in loop to select the forwarders. The node sort process also influences the time complexity of the algorithm. For the case of using heap sort, the time complexity of this sort step is ranging from $O\left( |\mathcal {N}\left( i\right) |\log |\mathcal {N}\left( i\right) |\right)$ to $O\left( 1\right)$, since the number of pending sort nodes is decreased by one in each iteration of forward selection. Paralleled with sorting process, node will also performs the delete operation to omit the neighbors CFIB, whose time complexity is $O\left( |\mathcal {N}\left( i\right) \mathcal {N}\left( v\right) |\right)$. Based on above discussion, the overall time complexity of the algorithm is

$$\begin{aligned} O\left( |\mathcal {V}_{f_e}|\max \left( |\mathcal {N}\left( i\right) |\log |\mathcal {N}\left( i\right) |,|\mathcal {N}\left( i\right) \mathcal {N}\left( v\right) |\right) \right) \end{aligned}$$

4 Performance Evaluation

Our simulation is based on NDNSIm, which is an open source ICN simulation tools based on network simulator 3 (NS-3). We consider a $1500*1000 \left( m^2\right)$ scenarios which is extracted from digital map of Beijiing and 300 mobile nodes are moving in this scenarios according to the real mobility trace in T-Drive [18]. The movement speed of each node is set in the range of $\left[ 20,40\right]$ km/h. Each mobile node is equipped with 5G-D2D modular in order to communicate with each other and the parameter setting of MAC layer is given as Table 2.

Figure 3 compares the delay in finding data (DFD), which is measured by the time span between sending Interest and receiving data. As figure shows, the EAFF achieves better performance in terms of DFD than other two solutions, and the superiority of EAFF expands when number of mobile nodes growing. Figure 4 shows the energy consumption of forwarding Interest packets, where the number of mobile nodes varies from 150 to 300. From the figure, we observe that EAFF achieves the lowest energy consumption among three solutions when the system scale is small (before number of nodes increasing to 200). With the increasing of number of mobile nodes, the energy consumption of EAFF is slightly higher than VNDN but far more lowest than flooding-based strategy. Figure 5 compares the number of generated Interest packet during the simulation process, the number of mobile node is set to 200. As figure shows, the number of Interest generated per-second in EAFF is lower than that of VNDN and flooding-based method. Figure 6 compares the playback freeze during the simulation time, which is one of the important performance indexes for video streaming service. As figure shows, EAFF achieves the lowest the playback freeze times among three solutions. The curves corresponding to the VNDN is higher than the one of EAFF at stable phase (i.e., after 250 s). The flooding-based method reveals a linear increasing trend, which reaches 9 after 900 s.

Fig. 3.

DFD vs. number of mobile nodes

Fig. 4.

Interest forwarding energy consumption vs. number of mobile nodes

Fig. 5.

Number of disseminated Interest vs. simulation time

Fig. 6.

Playback freeze vs. simulation time

EAFF leverages a greed-based distributed forwarder selection method to select nodes with higher forwarding coverage and residual battery lifetime as next-hop forwarders. As nodes with higher forwarding coverage also have higher probability of discovering asked content in one-hop range, which therefore speeds up the content searching process. Besides, EAFF also limits the number of forwarders and selects nodes with higher residual battery lifetime as forwarders. Hence, avoid broadcast storm and alleviate the consumption of forwarding Interest. Therefore, EaFF achieves low DFD, energy consumption and number of generated Interest as Figs. 3, 4 and 5 show. Since the EAFF has the lowest DFD, or equivalently, has the lowest delivery latency, hence it has the minimum number of playback freeze times. VNDN select the farthest node as Interest forwarder in each hop. VNDN selects one node in each hop to forward Interest in order to mitigate the consumption of Interest forwarding. However, due to the limited forwarding coverage in each hop, the probability of locating a nearby content provider is low, namely lengthen the content searching delay. In addition, because each node requires waiting a random delay to detect whether a farther node exists, which introduces extra delay when forwarding the Interest. Besides, due to the randomness searching feature of VNDN, the performance of playback freeze experiences a vibration at the beginning of simulation due to the variation of delay in finding data, as Fig. 6 depicts. Consequently, although VNDN has low energy consumption and number of Interest generated, this is at the cost of content delivery latency, which bring huge negative effects to the QoE of end users, hence also result in high frequency of playback freeze. In flooding-based method, all mobile nodes that receiving the Interest will broadcast this Interest in one-hop range, which discover the content providers by fast traversing the network. However, flooding-based method results in Interest broadcasting storm which not only consume huge bandwidth but also higher the energy consumption of mobile nodes. As a result, flooding-based method has highest energy consumption and number of Interest as Figs. 4 and 5 show. Besides, flooding-based method also higher the risk of network congestion. Hence, with the simulation time increasing, the network congestion is becoming more and more serve when using flooding-based method and therefore higher the playback freeze frequency.

5 Conclusion

In this paper, we focus on video sharing in information centric 5G-D2D networks and proposed EAFF, a energy-aware fast Interest forwarding to support fast content sharing in ICN 5G-D2D which aims to fast search demand content with low energy consumption. We firstly formulate the Interest forwarding in ICN 5G-D2D as an optimization problem which is NP-hard but submodular and monotonous, namely a 1-$\varepsilon$ approximation solution can be found within polynomial time by greedy method. Then, we proposed a greed-based distributed forwarder selection algorithm which enable mobile nodes individually selecting neighbours with higher forwardering coverage and battery lifetime as next-hop forwarders. Simulation results show how EAFF achieves better performance in terms of delay in finding data, forwarding energy consumption, Interest cost and playback freeze than sate-of-art solution VNDN and flooding-based method. Future work will consider how to jointly optimize Interest forwarding and content caching in order to achieve higher efficiency of content sharing in ICN 5G-D2D.