Enabling disaster-resilient communication using multi-hop device-to-device framework

Abstract

With the occurrence of a disaster, the conventional cellular network becomes non-functional. To provide connectivity to the affected users in such a scenario, we propose a novel multi-hop device-to-device (D2D) communication framework to connect to an active base station (BS). The goal of the proposed work is to maximize the number of covered users in the disaster-affected area within a given time frame. Joint routing and scheduling is imperative in a multi-hop network; however, the existing works on joint routing and scheduling optimization consider that the source–destination (user–BS) pairs are known beforehand or fixed. This is an inefficient approach when maximizing the number of covered users in a time-bounded communication set-up. Consequently, we propose a novel multi-hop D2D framework with joint source–destination pairing, routing and scheduling optimization. The optimization problem is formulated as an integer linear programming (ILP) problem. Further, due to the high time complexity of ILP, a low complexity graph-based scheduling constraint aware routing and pairing algorithm is proposed, resulting in a significant reduction in processing time compared to the optimal solution. The proposed algorithm also outperforms shortest path routing based scheduling in terms of users covered in the disaster-affected area.

1 Introduction

In the aftermath of a disaster, the worst-hit areas are the ones that require the most help. However, due to the traditional cellular network’s failure in the disaster-affected area, it is impossible for the rescue teams to disseminate important information to the local population and for the local population to contact the remotely located emergency control rooms. This disaster-affected area with no cellular network coverage is termed as the “dead spot”. Consequently, there is a need to set-up a disaster-resilient communication network in the dead spot [1]. In order to cater for the above, Releases 13–15 of 3rd Generation Partnership Project (3GPP) propose a device-to-device (D2D) communication framework wherein a device which is out of cellular network coverage can be assisted by another nearby device (as a relay) to communicate with the cellular network [2]. D2D has also been identified as a key enabler for fifth-generation (5G) cellular networks [3, 4]. Further, recent studies have shown that multi-hop D2D is a viable technique for alleviating the damage caused to the cellular network by reinforcing the cellular connectivity [5]. Multi-hop D2D ensures the extension of network coverage, improvement in energy efficiency, and reducing end-to-end delay, which are all crucial parameters in a dead spot.

The performance of multi-hop networks generally relies on the routing decisions as routing is responsible for establishing the inter-network communications. Therefore, routing in multi-hop D2D networks has received considerable attention from researchers everywhere. Multi-hop D2D networks have broadly two categories of routing: multi-hop D2D routing and multi-hop device-to-infrastructure/infrastructure-to-device (D2I/I2D) routing [6]. In multi-hop D2D routing, the source and destination are two user devices that route the information through intermediate D2D relays. In multi-hop D2I/I2D routing, a route is selected between a user device and a base station (BS). The route consists of intermediate D2D relays, also known as network relays. Further, in multi-hop D2I/I2D routing BS acts as the source and destination in downlink and uplink, respectively.

In a disaster scenario, a cellular user in the dead spot would like to immediately communicate with close relatives, remote emergency control room, emergency first responders, etc. Since most of the BSs in the dead spot are non-functional; hence, it is desirable to use the multi-hop D2I/I2D routing to connect to an active BS, which is present outside the dead spot [7]. In the proposed work, we jointly consider the problem of source–destination (user–BS) pairing, routing and scheduling to maximize the number of covered users in a dead spot within a given time frame.

1.1 Related work and motivation

In the literature, multi-hop D2D routing has been shown to be useful for offloading traffic, enhancing spectral efficiency and extending coverage of the cellular networks [8, 9]. Authors in [10] have analyzed the performance of the multi-hop D2D framework in the presence of co-channel interference from cellular and other D2D transmissions. They used the shortest-path routing (SPR) algorithm, both for uplink and downlink. The closed-form expressions for the number of hops and outage probability were presented in [10] for a tractable theoretical framework of multi-hop D2D underlaying cellular network. Although multi-hop D2D was shown to be reliable, the performance of cellular transmissions degraded. This motivated the researchers to investigate multi-hop D2D routing that is aware of the interference from the cellular transmissions [11]. For instance, authors in [12] proposed an interference-aware routing algorithm with an objective to minimize the hop-counts for a multi-hop D2D network. Similar to the work in [12], an emergency route selection framework during an urban terrorist attack was proposed for multi-hop D2D networks co-existing with a cellular network [13].

Multi-hop D2I/I2D routing can be utilized to connect to an active BS, which is present outside the dead-spot. For instance, in [14], the authors studied the benefits of multi-hop D2D in extending the coverage area of BS in public safety scenarios. It was shown that the average energy and spectral efficiencies due to multi-hop D2D are enhanced when the number of hops is increased. Like [10], they have utilized the SPR algorithm. Authors in [15] proposed a routing scheme utilizing the ant colony optimization to maximize the end-to-end throughput for all the data flows originating from the area without cellular network coverage. However, the aforementioned works of multi-hop D2I/I2D using SPR, for public safety and disaster scenarios, result in inefficient use of wireless radio resources in the presence of self-interference or contention among different users [16]. This is due to the fact that they have overlooked the half-duplex nature of the D2D relays, i.e., a D2D relay can either transmit or receive so that the transmitted and received data flows do not interfere while making the routing decisions. Further, it is important to restrict the data flows that can be transmitted or received simultaneously by a D2D relay to limit the contention among different flows/users [17]. Hence, it is imperative to jointly address the problem of routing and scheduling in the multi-hop D2D network. Joint routing and scheduling algorithms have been widely discussed in the literature in the context of ad-hoc wireless networks [16, 18,19,20,21,22,23,24,25,26]. For instance, in [18] and [19], authors have maximized the end-to-end data flow by solving the joint routing and scheduling problem. Authors in [16] propose a joint optimal design of cross-layer congestion control, routing and scheduling for ad-hoc networks. In [20], authors considered the nodes to be equipped with multi-radios. Hence, they solve the problem of routing and scheduling for multi-radio ad-hoc networks. Similar to [20, 26] also considers multi-radio ad-hoc network. The work in [21] considers the wireless mesh network constituting the backbone of third-generation (3G) networks. In this work, the problem of joint routing and scheduling has been solved in the presence of directional antenna equipped nodes. In [22], authors have proposed routing and scheduling policies that optimize network throughput in multi-hop wireless networks where nodes are powered by renewable energy sources.

However, the above works on routing and scheduling generally involve a single destination or fixed source–destination pairs. When the source–destination pairs are fixed prior to routing and scheduling, the users who are in close proximity may contend for the same wireless link to connect to the same active BS. Consequently, on applying the existing joint routing and scheduling algorithms to a time-bounded disaster-resilient communication network, less number of users will get covered.

In the proposed framework, a user is said to be covered by the network once it establishes connectivity with any of the active BSs within the given time frame. Hence, there is a possibility of an optimal selection of BS with which a user can be paired. By exploiting the above, we propose a joint optimization of source–destination pairing, routing and scheduling in order to maximize the number of covered users within a given time frame in the dead spot. To the best of our knowledge, the existing literature has not dealt with joint source–destination pairing, routing and scheduling for a multi-hop D2D network in a disaster scenario.

1.2 Contributions

In this work, we present a disaster-resilient multi-hop D2D network that employs a joint source–destination pairing, routing and scheduling framework to maximize the number of users that can be covered in the dead spot by an active BS within a given time frame. Unlike the prior works on multi-hop D2I/I2D routing in a disaster scenario, for a coverage maximization problem within T time slots, routing, scheduling and pairing are jointly optimized. The formulated optimization problem is an integer linear programming (ILP) problem and is computationally expensive. The existing routing and scheduling algorithms are not applicable as they do not decide the source–destination pairings. Consequently, we have proposed a low complexity graph-based scheduling constraint aware routing and pairing (SCARP) algorithm. SCARP is, as the name suggests, aware of the scheduling constraints and jointly determines the source–destination pairings and scheduled paths for the multi-hop D2D network. Further, SCARP results in up to 92% reduction in processing time as compared to the optimal solution.

The major contributions of the proposed work are summarized below:

• We propose a joint source–destination pairing, routing and scheduling framework for a multi-hop D2D communication in the dead spot.

• The maximization of covered users in the dead spot is formulated as an ILP. We show that the ILP is NP-hard; hence, a low complexity scheduling constraint aware routing and pairing (SCARP) algorithm is proposed to perform joint pairing, routing and scheduling unlike the existing algorithms.

• The reduction in the processing time required to obtain a solution to the ILP with SCARP as compared to the optimal solution is also demonstrated.

• In addition, we also compare SCARP with an SPR based scheduling. In case of SPR based scheduling, we have considered fixed as well as unknown user–BS pairings.¹ The improvement in the number of covered users is recorded in SCARP w.r.t. SPR based scheduling and pairing schemes.

The rest of the paper has been organized as follows: Sect. 2 presents the model for the disaster-resilient multi-hop D2D communication network. Section 3 formulates the problem of maximizing the number of users covered in the dead spot. Section 4 presents the proposed SCARP algorithm for solving the formulated problem and explains the working of SCARP. Section 5 discusses the results obtained on applying the optimal solution and the proposed SCARP algorithm on a disaster-resilient communication network. In the same section, the performance of SCARP is also compared with the SPR based scheduling and pairing. Finally, Sect. 6 concludes the paper. The list of variables used in the paper is provided in Table 1.

Table 1 List of variables

Fig. 1

Disaster-resilient network model

2 Disaster-resilient network model

We consider an uplink multi-cell network where a part of the network has been impacted due to disaster resulting in a dead spot containing non-functional BSs and users without any network connectivity, as shown in Fig. 1. Let us denote the set of users inside and outside the dead spot as $D_1$ and $D_2$, respectively. In the aftermath of the disaster, at a given time instance, let there be a subset of the local population and/or emergency first responders (EFR) termed as “D2D sources” in the dead spot who are trying to communicate with close relatives, remote emergency control room, etc. Hence, the D2D sources will have to route their information to an active BS outside the dead spot. With the assistance of multi-hop D2D communication, a D2D source can expect to be connected to a BS in set B of active BSs, creating a disaster-resilient communication network. Let DS be the set of D2D sources where $DS \subset D_1$. Rest of the users in $D_1$ and the idle users in $D_2$ will constitute the set D of D2D relays. Figure 1 shows the set D of D2D relays distributed across the multi-cell network. A connection between a D2D source and an active BS is assumed to be successful only when an active BS receives a data packet from the D2D source within time frame ${\mathcal {T}}$ via multi-hop D2D communication. Let time frame ${\mathcal {T}}$ consist of T time slots. It may be noted that in the present context, one time slot corresponds to one hop of communication. Further, in a disaster scenario, users will generally have limited mobility and are usually confined to specific locations. In a dead spot, it is reasonable to assume that the affected users will be given higher priority for establishing a connection as compared to cellular users outside the dead spot. Consequently, the D2D communication in the dead spot is allocated R resource blocks (RBs) where one RB is assigned to each D2D source and $R>|{{DS}}|$ where |.| denotes the cardinality of a set. In a disaster scenario, there is a need to take centralized routing decisions as suggested in [15]. Hence, the joint pairing, routing and scheduling decisions are assumed to be carried out at a central emergency control room. We assume D2D sources and D2D relays in the dead spot can be localized and this information is available at the control room. For instance, UAV networks can be utilized for such localization [27]. The details regarding the handling of the control-related traffic is out-of-scope of the present work. The disaster-resilient communication network in Fig. 1 can be modeled as a contact graph G(N, E) where D2D sources, D2D relays and active BSs constitute the set of nodes N, and E is the set of edges. An edge will exist between any two nodes in the graph if the nodes are within each other’s D2D transmission range. The weight of each edge is equal to w because all the edges satisfy the D2D transmission range criteria. Let $L_{D2D}$ and $L_{D2B}$ denote the set of links between D2D relays, and D2D relays and active BSs respectively. There is a set of links $L^{m}_{DS2D}$ between a D2D source m and D2D relays. Let $L^{m}$= $L_{D2D} \cup L_{D2B} \cup L^{m}_{DS2D}$ be the set of all links through which D2D source m can possibly reach any active BS. As mentioned above, the motivation of the proposed work is to maximize the number of users covered in the dead spot, i.e., to facilitate more end-to-end connections from D2D sources in the dead spot to active BSs within T time slots. This optimization problem has been formulated as an ILP problem and is shown below to be NP-hard. Consequently, this paper proposes a novel SCARP algorithm for multi-hop D2D in a disaster-resilient network.

3 Problem formulation

In this section, we formulate an optimization problem where the objective function is to maximize the number of users that can be covered in the dead spot using multi-hop D2D within a deadline of T slots. A D2D source is said to be covered if there is an end-to-end connection from the D2D source routed through the D2D relays to an active BS within T slots. In the following, we introduce some key variables used in the problem formulation. Further, the details of the objective function and constraints of our problem are provided.

3.1 Variables

Let $(i,k) \in E$ be the link present between node i and k where $i, k \in N$. $F^{m}_{i,k} \in \{ 0, 1 \}$ is the flow variable which is ‘1’ when there is a flow of a data packet through (i, k)th link originated at D2D source m and ‘0’ otherwise. Further, let $A^{m}_{i,k} (t) \in \{0,1\}$ be the scheduling variable which is ‘1’ when the link (i, k) is scheduled to route the flow of D2D source m in time slot $t \in {\mathcal {T}}$ or ‘0’ otherwise.

3.2 Objective function

The objective is to maximize the total number of covered users. If a D2D source m is getting covered $F_{i,k}^{m}$ will be ‘1’ for a link $(i,k) \in L_{D2B}$ else $F_{i,k}^{m}$ will be ‘0’ $\forall (i,k) \in L_{D2B}$. Hence, the total number of users covered is represented using $\sum _{m \in DS}^{}\sum _{(i, k)}^{} F_{i,k}^{m}$. In other words, $F_{i,k}^{m} = 1$ for $(i,k) \in L_{D2B}$, denotes that D2D source m will be paired with BS $k \in B$. The objective function is as given below:

$$\begin{aligned} {\text {maximize}} \quad {\sum _{m \in DS}^{}\sum _{(i, k)}^{} F_{i,k}^{m}, \; (i, k) \in L_{D2B}. } \end{aligned}$$

(1)

3.3 Constraints

In the following, we will discuss the constraints of our problem.

Constraint 1 In the considered graph-based network model, at each D2D relay, the flow constraints must be met, i.e., the amount of incoming flow of data must be equal to the outgoing flow of data and is formulated as:

$$\begin{aligned}&\sum _{k:(i, k)}^{} F_{i,k}^{m}- \sum _{l:(l, i)}^{} F_{k,i}^{m} = 0 , \nonumber \\&\quad \quad \forall i \in D, \; (i, k), (l,i) \in L_{D2D}, \; \forall m \in DS. \end{aligned}$$

(2)

Constraint 2 There is a possibility that a D2D source is not covered by any BS. Hence, the flow constraint at a D2D source is as follows:

$$\begin{aligned} \sum _{k:(i, k)}^{} F_{i,k}^{m} \le 1, \; (i, k) \in L^m_{DS2D} , \quad \forall m \in DS. \end{aligned}$$

(3)

Constraint 3 It is not known beforehand which BS will receive D2D source m’s data. This flow constraint is as follows:

$$\begin{aligned} \sum _{i:(i, k)}^{} F_{i,k}^{m} \le 1 , \quad \forall k \in B, \; (i, k) \in L_{D2B}, \; \forall m \in DS. \end{aligned}$$

(4)

The above constraint implies that at most one D2B link will be active for the mth D2D source.

Constraint 4 During the time frame ${\mathcal {T}}$ link (i, k) can be active for a D2D source m at most once. This is because within ${\mathcal {T}}$ a D2D source will be sending out only one packet of data. This scheduling constraint is formulated as:

$$\begin{aligned} \sum _{t \in {\mathcal {T}}}^{} A_{i,k}^{m} (t) = F_{i,k}^{m}, \quad \forall m \in DS, \; (i, k) \in L^{m}. \end{aligned}$$

(5)

Constraint 5 There can be at most |DS| data flows in the network originating from |DS| D2D sources. In order to allow the reception of single data flow, originating from a single D2D source, at a D2D relay at a given time slot t, below reception constraint is added:

$$\begin{aligned} \sum _{m \in DS}^{}\sum _{i:(i, k)}^{}&A_{i,k}^{m} (t) \le 1, \quad \forall t \in {\mathcal {T}}, \nonumber \\&\forall k \in D, \; (i, k) \in L^{m}_{DS2D}\cup L_{D2D}. \end{aligned}$$

(6)

Constraint 6 In order to allow transmission of single data flow from the D2D sources and D2D relays at a given time slot t, a transmission constraint is introduced as follows:

$$\begin{aligned}&\sum _{m \in DS}^{}\sum _{k:(i, k) }^{} A_{i,k}^{m} (t) \le 1, \quad \forall t \in {\mathcal {T}}, \nonumber \\&\quad \forall i \in D \cup DS, \; (i, k) \in L^{m}_{DS2D}\cup L_{D2D}. \end{aligned}$$

(7)

Constraint 7 The constraint to limit simultaneous transmission/reception in order to avoid self-interference at a node is given as follows:

$$\begin{aligned}&\sum _{m \in DS}^{}A_{i,k}^{m} (t)+ \sum _{m \in DS}^{} A_{k,l}^{m} (t) \le 1, \quad \forall t \in {\mathcal {T}} , \; \forall k \in D, \nonumber \\&\quad (i, k), (k,l) \in L^{m}_{DS2D}\cup L_{D2D} . \end{aligned}$$

(8)

This constraint is applicable for the links in $L_{D2D}$ and $L^{m}_{DS2D}$.

Constraint 8 In the first time slot, it is obvious that no link can be established between the D2D relays, and a D2D relay and BS. This has been taken care of in the constraint given below:

$$\begin{aligned} A_{i,k}^{m} (1) = 0, \quad \forall m \in DS, \; \forall (i, k) \in L_{D2D}\cup L_{D2B} . \end{aligned}$$

(9)

Constraint 9 The flow of data originating at m arriving at $k \in D$ through any link (i, k) during ${\mathcal {T}}$, can be denoted by $\sum _{i:(i, k)}^{} F_{i,k}^{m}$. Since, there is a possibility that a D2D source is not covered by a BS $\sum _{i:(i, k)}^{} F_{i,k}^{m}$ can be ‘0’ or ‘1’. Let $\sum _{i:(i, k)}^{} F_{i,k}^{m} = 1$ and say data has not arrived at k till $t-1$ slots, i.e., $\sum _{{\bar{t}} = 1}^{t-1}\sum _{i:(i, k)}^{}A_{i,k}^{m}({\bar{t}}) =0$. Therefore, any link $(k,l) \in L_{D2D}\cup L_{D2B}$ must not be scheduled for m’s flow, i.e., $A_{k,l}^{m} (t)$ must be 0. To ensure the above causality constraint, i.e., a node k cannot transmit in the tth slot unless it has received data in the previous $(t-1)$ the below condition needs to be satisfied:

$$\begin{aligned}&\sum _{{\bar{t}} = 1}^{t-1}\sum _{i:(i, k)}^{} A_{i,k}^{m}({\bar{t}}) + \big (1-A_{k,l}^{m} (t)\big ) \ge \sum _{i:(i, k)}^{} F_{i,k}^{m} , \quad \forall t \in {\mathcal {T}}, \nonumber \\&\quad \forall m \in DS, \; (i,k)\in L^{m}_{DS2D} \cup L_{D2D}, \; \forall (k,l) \in L_{D2D}\cup L_{D2B}. \end{aligned}$$

(10)

Hence, the formulated optimization problem is given as follows:

$$\begin{aligned} {\text {maximize}}&{\sum _{m \in DS}^{}\sum _{(i, k)}^{} F_{i,k}^{m}, \; (i, k) \in L_{D2B}} \nonumber \\ {\text {subject to}}&(2){-}(10) \end{aligned}$$

(11)

3.4 Problem complexity

The NP-hardness of our optimization problem can be proven by reducing from the preemptive scheduling problem in [28], which is proven to be NP-hard. In the preemptive scheduling problem, a set P of tasks is scheduled within a deadline. Each task $p \in P$ is subdivided into sub-tasks $p_1, p_2, \ldots , p_k$. The duration of each task is the sum of the duration of the sub-tasks. The scheduling of sub-task $p_i$ precedes the scheduling of $p_{i-1}$. Let the set of tasks P be the set of the routing paths of the D2D sources willing to connect to any active BS. Each task p will be a routing path and sub-tasks $p_1$ to $p_k$ will be the links on the routing-path p. Consequently, preemptive scheduling maps to our problem. Hence, our problem is NP-hard with high time complexity.

4 Scheduling constraint aware routing and pairing (SCARP) algorithm

In this section, we present the intuition behind the proposed SCARP algorithm. Then, we explain in detail the working of SCARP and illustrate it using an example. Further, we also evaluate the time complexity of SCARP.

4.1 Key intuition

As shown above, the formulated ILP problem is NP-hard. Hence, an alternate approach is required to solve the formulated problem with lower complexity. For the considered time-bounded communication, SPR can find the routing paths with the minimum number of hops as the network links in the path are equally weighed. Given a single D2D source and corresponding destination, SPR seems to be an obvious approach to get the D2D source covered within time frame ${\mathcal {T}}$. However, when there are multiple D2D sources in the network, SPR will not ensure maximum coverage as it takes the routing decisions without considering the scheduling possibilities of the shortest paths within time frame ${\mathcal {T}}$ [29]. Hence, we propose a SCARP algorithm that utilizes the shortest path algorithm in a recursive manner (explained in detail below) to select non-overlapping shortest paths to take care of the scheduling constraints. Further, SCARP also accounts for the fact that, in the formulated problem, the source–destination pairs are not known beforehand and decides the D2D source–BS pairing. SCARP is given G(N, E) as input, and each D2D source’s scheduled path is obtained as output, which gets stored in ${\mathcal {P}}$ where ${\mathcal {P}}$ is the list containing the scheduled paths of each D2D source. The scheduled paths for each D2D source are obtained recursively to keep re-selecting a scheduled path for a D2D source until it meets the scheduling constraints. Assuming a distance-dependent path loss, the proposed SCARP algorithm considers the link distances of the user pairs (D2D sources and D2D relays), and the user–BS pairs.

4.2 Detailed working of SCARP

The proposed SCARP algorithm is presented in Algorithm 1. The working of the algorithm is as follows. G(N, E) is provided as input to the algorithm. As mentioned above, the weight of each link is initialized with the same value w. The algorithm is executed only when $T\ge 2$, equivalent to a minimum of two hops that are required to establish a multi-hop D2D communication as direct communication between an active BS and a user in the dead spot is not feasible. For a D2D source m, function ${\mathtt{Main}}()$ is called which has the arguments: G(N, E), ${\mathcal {P}}$ and ${\mathcal {N}}$ where ${\mathcal {N}}$ is the list of D2D sources connected to each BS in B. Within ${\mathtt{Main}}$, the shortest path to each of the active BSs is calculated based on the sum of weights of the links between source m and each BS, and stored in $shortest_{paths}$. Finding the shortest paths with respect to each of the BSs takes into account the fact that the destination of each D2D source is not known beforehand. The function ${\mathtt{weight}}()$ finds the sum of the link weights of each shortest path and is stored in $B_{weights}$. Function ${\mathtt{Function min}}()$ provides the minimum of $B_{weights}$.

If the minimum of $B_{weights}$ is less than T, i.e., the shortest path can be scheduled within T slots, the information of the BSs having minimum $B_{weights}$ is stored in $C_{m}$. Otherwise, no optimal path is possible for the D2D source m. In case $C_{m}$ contains more than one BS, the BS with the minimum sum of link distances from m is selected using ${\mathtt{Select}}()$ function. Now, it has to be checked whether the selected BS is already selected as a destination for other D2D sources. This is because if any two D2D sources have a common destination (BS), higher is the possibility of having overlapping shortest paths. ${\mathcal {N}}_{j} \in {\mathcal {N}}$ is the set of D2D sources using BS j. If the mth and other D2D sources have a common destination (BS) ${\bar{j}}$, the number of hops in their paths to the common BS are compared. Here, $H_{m}$ and $H_{{\mathcal {N}}_{{\bar{j}}}(k)}$ are the number of hops in the path of D2D source m and kth D2D source present in ${\mathcal {N}}_{{\bar{j}}}$. In Algorithm 1, Nodes consist of the D2D sources with $|H_{m}- H_{{\mathcal {N}}_{{\bar{j}}}(k)}| < 2$. This step is required to meet the scheduling constraints, i.e., the constraints on simultaneous transmission and reception, and simultaneous multiple transmission/reception at a node. If m and any D2D source in ${\mathcal {N}}_{{\bar{j}}}$ fails to meet the scheduling constraints, i.e., $|Nodes| >0$, then re-selection of the scheduled path of m or $S_{re}$ is performed. Prior to making the decision which D2D sources’ path needs to be re-selected, the D2D source m is added to the set Nodes. If there is only one D2D source in Nodes with the minimum sum of link weights, i.e., $|S_{DS}| <2$, $S_{re}$’s path is re-selected. However, if there is more than one D2D source with the minimum sum of weights, i.e., $|S_{DS}| >1$, there is a re-selection of the path for m. The function ${\mathtt{Find}}()$ has $S_{re}$ or m and a D2D source in $Nodes -\{S_{re}\}$ or $Nodes - \{m\}$ as the input arguments (at steps 23 and 31) and outputs the common relays between their paths to the common destination ${\bar{j}}$, which is stored in $C_{relays}$. Using function ${\mathtt{Update}}$ the weights of all the edges that connect to the relays in $C_{relays}$ are updated to a higher weight $w'>> w$. Updating the links with a higher weight will ensure that the previously chosen path for n is not selected again. This is due to the fact the previously chosen path for m or $S_{re}$ will no longer be the shortest path to fulfill the criteria in line 7 of Algorithm 1. However, if $C_{relays}$ is empty in case of m’s path re-selection, then ${\mathcal {P}}$ is updated with the currently selected path of the D2D source m. In the above, the process of finding the shortest path is repeated recursively.

Correctness SCARP algorithm schedules the D2D sources within the deadline of T slots. For a D2D source m, function Main() is called for obtaining the scheduled path. If the condition in line 7 is not met for a D2D source, the function Main() is exited. Then, SCARP moves on to the next D2D source. The algorithm terminates when the value of m equals to $\vert DS\vert$ or when $T<2$.

Fig. 2

Network example for showing the route selection in SCARP and SPR

Figure 2 shows the routing decisions taken by the SCARP algorithm and SPR for the network. In the case of SPR, Route 1 and Route 3 are selected for D2D sources $DS_1$ and $DS_2$, respectively, which have overlapping intermediate D2D relays. Consequently, for $T=3$, at the time of scheduling $DS_2$ will not be covered by any active BS. On the other hand, for $T = 3$, in case of SCARP, $DS_1$ and $DS_2$ are paired with $B_2$ and $B_1$ respectively and their multi-hop paths can be scheduled within $T=3$.

4.3 Time complexity of SCARP

The time complexity of the for loop at step 3 of Algorithm I is ${\mathcal {O}}(|DS|)$, where |DS| is the number of D2D sources in dead spot. The shortest path to each BS is calculated at step 6. Using Dijkstra’s algorithm, the time taken is ${\mathcal {O}}(|B||E|\log |N|)$, where |B|, |E| and |N| are the number of BSs, edges and nodes respectively in the network. Further, for D2D source m, there are $(|DS|-1)$ D2D sources with whom m can have overlapping paths. Therefore, in the worst case, for D2D source m function ${\mathtt{Main}}()$ will be called |DS| times and hence, the time complexity of SCARP algorithm is ${\mathcal {O}}(|DS|^2|B||E|\log |N|)$.

5 Results and discussion

In this section, we evaluate the performance of the proposed framework in a disaster-resilient communication network. The simulation set-up is described below:

5.1 Simulation set-up

For each network realization, we have assumed a fixed number of active BSs having fixed locations that surround the dead spot. D2D sources in the dead spot are assumed to have random locations. D2D relays in the network are considered to follow a Poisson point process (PPP). The simulated network area is $2 \times 2$ sq. km. Unless otherwise stated, number of BSs, |B| = 9; number of D2D sources, |DS| = 5; density of D2D relays = $50/{\mathrm {km}}^2$ and number of time slots, T = 3. For the graph-based network model, initial edge weight, $w =1$ and updated edge weight (in Step 34, Algorithm 1), $w'=100$. We have assumed a distance-dependent path loss model. Let the maximum transmission range of each BS and D2D device be 450 m and 150 m, respectively. The optimal solution to the formulated problem has been obtained using the IBM CPLEX solver.

Fig. 3

Network graph for a specific network realization

Fig. 4

Processing time w.r.t. density of D2D relays

Fig. 5

Users covered w.r.t. number of D2D sources

The network simulations and SCARP algorithm execution have been done on MATLAB. All the above tasks have been run on an i5 CPU with 4 GB RAM and 64-bit operating system. The optimal solution and results corresponding to the SCARP algorithm have been demonstrated for a network with less number of D2D sources. However, the proposed SCARP algorithm can be implemented for large scale networks as well. The results shown in this section have been averaged over 100 network realizations. Network graph for a specific network realization with 9 BSs, 4 D2D sources, and D2D relays with density $20/{\mathrm {km}}^2$ is shown in Fig. 3.

Fig. 6

Box plot with $|DS| = 10$, $T=4$ and density of D2D relays a $40/{\mathrm {km}}^2$ b $50/{\mathrm {km}}^2$ and c $60/{\mathrm {km}}^2$

5.2 Performance evaluation of SCARP

In the following, we have analyzed the processing time for the optimal solution using CPLEX solver and proposed SCARP algorithm. Figure 4 compares the processing time for the optimal solution and SCARP. It can be observed that with the increase in the density of the D2D relays from $40/{\mathrm {km}}^2$ to $80/{\mathrm {km}}^2$ the processing time for the optimal solution is increasing rapidly. This is due to the fact that with the increase in the number of D2D relays in the network, the number of edges in the graph will increase. Consequently, the constraints in the formulated problem (11) will have to account for increasing number of nodes and edges. The optimal solution’s processing time will increase exponentially. Unlike the exponential processing time for the optimal solution, the SCARP algorithm has a polynomial processing time.

Figure 5 shows the plot for the number of users that can be provided access to the cellular network in the dead spot on using SCARP and the optimal solution. It can be observed that with an increase in the number of D2D sources from 2 to 5 in the dead spot, the number of users that can access the cellular network increases for both SCARP and optimal solution. However, there is a slight performance gap (up to 5.5%) between SCARP and optimal solution. This slight degradation in performance comes with a reduction of about 92% (as shown in Fig. 4) in the processing time on using SCARP. Therefore, SCARP provides a good low complexity alternative solution for the optimization problem.

5.3 Comparison with existing work

As mentioned in Sect. 4, SPR used in the prior works on multi-hop D2D for a disaster scenario results in a minimum number of hops. For a time-bounded communication network considered in this work, SPR may appear to be efficient; however, it does not consider the necessary transmission/reception constraints (6)–(8). In SPR based scheduling, it is highly likely that D2D sources are assigned overlapping shortest paths to an active BS j. However, at the time of link scheduling, taking the transmission/reception constraints into account, only a few D2D sources with overlapping paths will access the cellular network within the desired deadline. Herein, we will compare the performance of SPR based scheduling with the proposed framework that utilizes SCARP. In our evaluation, we compare three approaches, namely: “SPR-fixed” (SPR with fixed pairings), “SPR-U” (SPR with unknown pairings) and “SCARP”. In SPR-fixed, the disaster-affected area is divided into |B| pie-shaped areas. These |B| pie-shaped areas are assigned one BS each. Hence, a D2D source lying in a given area will be paired with the BS assigned to that area. In SPR-U, as the source-destination pairs are not known beforehand, a D2D source m is paired with the destination $j \in B$, where j results in a minimum hop path to m among all the BSs in B.

Figure 6 presents the box plots to illustrate the impact of D2D relay density on the number of D2D sources covered in the dead spot for SPR-fixed, SPR-U, and SCARP at $T=4$ and $|DS|= 10$. It can be seen that with the increase in the density of D2D relays, the gap between the range of D2D sources covered in SPR-fixed, SPR-U, and SCARP increases. SPR-fixed and SCARP perform the worst and best, respectively. This is because, in SCARP, due to the increased presence of D2D relays, the feasibility of non-overlapping paths from D2D sources to an active BS will increase.

Let us now analyze the performance of the above three approaches with respect to T. Figure 6(b) ($T = 4$) and Fig. 7 ($T=5$) demonstrate the impact of T on the network set-up. With the increase in deadline T, the gap in the range of the number of users covered users decreases. However, the average number of users covered in SPR-fixed and SPR-U is still lower than SCARP.

The gain in the number of users covered using SCARP over SPR-U is small at higher T. However, there is another advantage of SCARP. It results in lower energy consumption at user devices on using SCARP at higher T as compare to SPR-U. To demonstrate this, we evaluate the energy consumption for SPR-U and SCARP. The expression for the average energy consumption per active D2D relay within T slots can be given as follows:

$$\begin{aligned} T_{energy} = \frac{\sum _{l}^{}{\omega _{l} \delta _E}}{\delta _E|D_{a}|},\quad \forall {l \in D_{a}} \end{aligned}$$

(12)

where $\delta _E$ is the energy consumed per transmission and reception of a packet at a D2D relay. $D_{a}$ is the set of active D2D relays within T slots. $\omega _{l}$ is the number of times relay, $l \in D_{a}$ is re-used within T. In Fig. 8, the plot for average energy consumption (normalized w.r.t. $\delta _E$ ) per active D2D relay node within T slots has been presented w.r.t. T, where T varies from 3 to 6, for SCARP and SPR-U. With an increase in T, both SCARP and SPR-U will increase the number of users gaining access to the cellular network via multi-hop D2D. This is because the routing paths with more number of hops can be scheduled easily within higher T. Despite the above fact, it can be seen from Fig. 8 that the average energy consumption per active D2D relay is lower for the proposed SCARP algorithm as compared to SPR-U. This can be explained as follows. As mentioned above, SPR-U tends to assign overlapping shortest paths to the D2D sources. With the increase in T, the chances of overlapping paths being scheduled within T will increase. This will result in the re-use of relays in overlapping paths. In the case of SCARP, we minimize the selection of overlapping paths. Consequently, SPR-U has up to 21% $\left( = \frac{(1.63-1.35) \times 100 \%}{1.35}\right)$ more energy consumption at higher T. Instead of re-using a set of D2D relays repeatedly, the proposed SCARP algorithm limits the overlap of the set of D2D relays corresponding to each data flow and hence results in spatially distributed energy consumption. This is beneficial for enhancing the longevity of the multi-hop D2D networks deployed for disaster-resilient communication.

Further, at lower values of T (such as T = 3), the chances of overlapping paths being scheduled within T are less, i.e., D2D sources covered are low, and the re-use of D2D relays may not be possible. Consequently, the average energy consumption per active D2D relay for SCARP is comparable at lower values of T.

Fig. 7

Box plot with $|DS| = 10$ at $T = 5$ and density of D2D relays = $50/{\mathrm {km}}^2$

Fig. 8

Average energy per active D2D relay node

6 Conclusion

In this paper, we proposed a novel joint routing, scheduling and pairing framework for a disaster-resilient communication network based on multi-hop D2D. An optimization problem to maximize the number of users covered in the dead spot within a deadline of T time slots is formulated. The formulated problem is shown to be NP-hard. Hence, we proposed SCARP that shows a 92% reduction in processing time compared to the optimal solution with an acceptable performance gap of 5.5% in terms of maximum users covered. It is also demonstrated that the proposed algorithm outperforms the widely used SPR based scheduling in terms of users covered at lower values of T (tighter deadline) and energy consumption per active D2D relay at higher values of T. This is because the D2D relays selected using SCARP are more spatially distributed, which reduces wireless link contention at lower values of T and lowers energy consumption at higher values of T. Further, the gain in users covered on using SCARP w.r.t. SPR based scheduling becomes more prominent with an increase in the density of D2D relays.