Fast and Energy Efficient Multihop D2D Routing Scheme

Abstract

Device-to-device (D2D) communications are expected to offload cellular networks and enhance public safety. In addition to the capability of direct communication between devices, the capability of delivering data over multihops in an ad hoc manner by autonomous decision of each device is highly desired to expand application areas of D2D communications. To address this issue, we propose a fast and energy efficient D2D multihop routing method using the geographic locations of nodes. To expedite data delivery while saving transmission powers of nodes, we devise the next hop selection method considering the congestion levels of potential next hops. In addition, we devise a detour scheme to move around a routing hole that is encountered when a node cannot find a neighbor that is closer to the destination of a packet than itself. We also propose management procedures so that each node acquires the locations of destinations and its neighboring nodes. Through extensive simulations, we validate the proposed method by comparing the performance of the proposed method with those of maximum progress method (MaxP), cost over progress method (CoP), and congestion-aware forwarder selection method (CAFS). Even though the number of hops obtained by the proposed method is larger than those obtained by MaxP and CAFS, our method is superior to them in terms of the probability of successfully delivering packets to destinations and total amount of energy consumption. We also show that our method can reduce end-to-end delay considerably compared with CoP.

1. Introduction

The amount of wireless data traffic has been surged over several years [1]. This is mainly due to the rapid proliferation of smart handheld devices used by people. In addition, as the era of Internet of Things is coming up, not only do people produce and consume data traffic by using the infrastructures that provide the capability of ubiquitous information exchange and acquisition but also the amount of traffic exchanged between machines is expected to increase substantially [2]. Thus, the amount of data transferred wirelessly will keep increasing over the near future [3]. The traffic demands have been accommodated by increasing the bandwidth of communication links. However, it becomes more and more difficult to use the traditional way of absorbing traffic demands because the throughput achievable at the physical layer is approaching its theoretical limits. As an alternative means, device-to-device (D2D) communications have attracted much attention not only from an academia and an industry but also from a public sector.

In the industry, D2D communications are expected to provide an efficient way of offloading cellular traffic, increasing spectral efficiency, and providing robustness [4]. In cellular networks, D2D communications are developed to provide proximity services [5, 6] by reusing the spectrum of cellular networks. Since D2D communications use the same radio frequencies with base stations, the researches on D2D in cellular networks have focused on the interference management [7] and resource management [8, 9].

Generally, transmission ranges of D2D nodes are short because the transmit powers of D2D nodes are low so as not to interfere base stations. In addition, D2D communications in a cellular network are controlled by network operators. As a result, D2D communications in a cellular network typically assume 1-hop or 2-hop relay [5, 10]. However, to fully utilize the potential of D2D communications, providing multihop D2D networks that operate autonomously is highly required.

In a public sector, D2D communications are expected to increase the public safety by providing a communication path when communication infrastructures are not available (e.g., in an area where disasters occurred) [11–14]. In such a region, even though communication infrastructure is not available, displaced people have communication devices at hand that are equipped with multiple wireless network interface cards. In addition, there are many communication devices around them such as smartphones, laptops, and tablets [11], and for some cases rescue teams can deploy resource units to support data relay [15]. If the devices can relay messages, the probability of saving lives will increase.

Reflecting the interest in multihop D2D communications from an industry and a public sector, D2D routing methods have been proposed for various types of applications. Routing protocols at the network layer that have been proposed for ad hoc and sensor networks are adopted for multihop D2D networks [16, 17]. Even though a delay-tolerant data delivery is required for some applications [18, 19], a fast and energy efficient routing method is required to expand the application areas of multihop D2D networks.

In [20], an interference-aware routing method is proposed to minimize hop count. The method aims to decrease the delay for D2D connections and power consumptions by minimizing hop count from a source to a destination. The similar idea is proposed for packet radio networks, where the node that can make the maximum progress to the destination of a packet is selected as the next hop [21]. However, it is noted in [22] that the transmit power decreases as $1/d^{\alpha }$ , where d is the distance from a sending node and α (≥2) is the path loss exponent given by a path loss model. Since received signal strength decreases exponentially as d increases, the maximum progress method requires high transmit power to deliver a packet to the farthest neighbor.

To reduce the amount of energy consumption of a sending node, a method called cost over progress (CoP) is proposed [23, 24]. A node selects the node that has the smallest transmit power over progress made to the destination as the next hop. Since CoP decreases the distance between the current sender and the next hop, it can reduce the amount of transmit power while the number of hops taken from a source node to a destination node increases. In addition, since CoP does not consider the congestion levels of potential next hops, it can bring about large end-to-end (e2e) packet transfer delay.

A congestion-aware forwarder selection method (CAFS) is proposed in [25]. CAFS uses multiple metrics to choose the next hop. By using the congestion levels of neighboring nodes among the metrics, CAFS attempts to find a balance between the cost (i.e., energy consumption) and the gain (i.e., e2e packet transfer delay). However, CAFS does not incorporate a void handling method that handles the situation where a node cannot find a potential next hop that can make progress to the destination of a packet.

In this paper, we propose a fast and energy efficient multihop D2D routing method using the geographic locations of nodes. Our method is focused on efficiently providing mobile services while offloading cellular networks. Since a server maintaining the profiles of mobile users is an integral part of a general mobile service platform, we exploit the server to obtain the locations of users. Using the location information, we propose a D2D routing method that can enhance the end-to-end packet delivery ratio while reducing energy consumption. The proposed method is composed of two distinct procedures. The first procedure is activated when a node does not face a routing void while the second procedure called a detour procedure is initiated when there is a routing hole. In the first procedure, potential next hops are filtered according to their congestion levels. Among the filtered nodes, the node that requires the minimum amount of transmit power compared to the progress that can be made to the packet is chosen as the next hop. In the detour process, a node that can provide the maximum detour success probability is selected as the next hop.

The rest of the paper is organized as follows. In Section 2, we review related works on multihop D2D networks. In Section 3, we propose a multihop D2D routing framework. We evaluate the performance of the proposed routing method through simulations in Section 4. Section 5 concludes the paper.

2. Related Works

Multihop D2D networks have been investigated in various aspects, from performance evaluations at MAC layer to practical services at application layer. In [26], the capacity of D2D multihop communications in an LTE-A network is studied when multiple idle user equipment acts as relay nodes. In [27], the outage probability of multihop D2D communications is analyzed theoretically when the transmissions from other D2D links and cellular networks interfere each other.

Clustering methods have been proposed for efficient multihop D2D communications. In [28], a simple clustering method is designed for multihop cooperative D2D communications where macrobase stations control the clusters of relay nodes. In [29], a distributed cluster-based routing protocol is proposed to improve the network energy efficiency by borrowing the idea of routing protocols in wireless sensor networks. To offload cellular traffic, a peer-to-peer (P2P) data sharing paradigm is introduced to D2D networks [18]. On the other hand, social network services and opportunistic D2D data sharing methods are applied to alleviate mobile traffic [19].

An attempt to combine the content-centric networking (CCN) paradigm with multihop D2D communications has been made. In [30], a MANET-aware CCN algorithm is proposed to disseminate messages efficiently. In [31], a CCN-like cooperative caching method is adopted for multihop wireless D2D networks.

Considering the link qualities and service quality required by each user, an optimal transmission scheduling and congestion control method is proposed for multihop D2D networks [32]. The authors in [16] test four ad hoc routing methods to show the possibility of multihop D2D routing over Wi-Fi Direct.

Experimental verification of D2D networking is made in [33]. The authors propose a framework and application toolkits for opportunistic wireless mesh networking and demonstrate a chat program and file exchange applications with several Android smartphones and tablets. For disaster relief applications, a multihop D2D routing method that combines the optimized link state routing protocol (OLSR) and an epidemic routing is proposed in [11]. The authors also identify important ingredients for multihop D2D communications and show the feasibility of their approach through field experiments.

Unlike these methods, we take a geographical approach for multihop D2D routing. In addition, in terms of the system model, we use a presence server to acquire location information of nodes. We also propose a detour process when a node faces a routing hole which can increase the end-to-end packet delivery ratio.

3. Multihop D2D Routing Framework

In this section, we describe a fast and energy efficient D2D multihop routing framework. We assume that each node registers its profile in a presence server. The profile of a node $n_i$ is customized for $n_i$ and it contains the list of nodes that $n_i$ has intent to exchange data with and their state information such as their locations and indicators that show the online states of the nodes.

3.1. System Model and Management Procedures

Figure 1 shows our system model. Each node updates its states by sending a presence message (PRES) to a presence server through an infrastructure network. The PRES message contains the coordinates of the node sending the message. The PRES message can be sent periodically or when the states of a node are changed. For example, when a node does not move around, PRES message is sent periodically at large time scale. Conversely, when a node $n_i$ logs off or the location of $n_i$ is changed, $n_i$ sends a PRES message to update its state.

Figure 1

System model.

Each node periodically 1-hop broadcasts a keep-alive message with a period $T_K$ . A keep-alive message includes the identifier of the node that sends the keep-alive message. If we denote the maximum queue size of a node $n_i$ as $Q_{\left[i,M\right]}$ and the amount of packets stored in the queue of a node $n_i$ at time t as $Q_i(t)$ , a keep-alive message also contains $Q_i(t)$ and $Q_{[i,M]}$ .

A node $n_i$ maintains two databases. One database is a target node DB (called TNDB) that contains a list recording the states of the nodes that $n_i$ is interested in exchanging data with. The other database is a neighbor DB (NDB) that stores the states of 1-hop neighboring nodes. A node maintains its TNDB by exchanging management packets with a presence server whereas a node maintains its NDB by hearing keep-alive messages periodically sent by other nodes.

Figure 2 shows the finite-state machine definitions for a node. A node $n_i$ updates its TNDB by sending a presence update request message (PUREQ) to a presence server. When a presence server receives a PUREQ, it finds the profile of a node that sends the PUREQ. Then, the presence server checks whether there is an update from the list in the matched profile. If there is no update, the presence server sends a presence update response message (PURSP) to a node $n_i$ which says the TNDB of $n_i$ is the newest. Otherwise, it sends a PURSP by constructing the list of nodes that changed their states and their updated state information. When a node $n_i$ receives a PURSP from a presence server, it updates its TNDB. If $n_i$ cannot find a record in its TNDB that matches with the identifier of a node in PURSP, it creates a record for the node and stores the information contained in the PURSP. On the contrary, if the identifier of a node in PURSP is already in the TNDB, it updates the corresponding record in the TNDB by replacing the information contained in the record with the information in PURSP.

Figure 2

Finite-state machine definition for a node.

When a node $n_i$ receives a keep-alive message, it updates its NDB. A node checks whether the identifier contained in the keep-alive message (node_ID) can be found in its neighbor list. If the node_ID is not included in the neighbor list, a node creates a record for the node that sends the keep-alive message in its NDB and stores the information contained in the keep-alive message. On the contrary, if a record for the node_ID exists already, a node $n_i$ updates its neighbor list by replacing the record for the node that sends the keep-alive message with the information contained in the keep-alive message. If a node $n_i$ cannot hear a keep-alive message from the nodes in its NDB K times successively, it removes the record for the node.

When a node $n_i$ has a packet to send to one of the nodes in its TNDB, it constructs a data packet and sends it through a multihop D2D network. The data packet contains the identifier of $n_i$ , the coordinates of $n_i$ , the identifier of the destination node, the coordinates of the destination node, and the message body.

3.2. Routing Procedures

Each node should relay a packet sent by other nodes. A flowchart for a node to send a message is presented in Figure 3. When a node $n_i$ has a packet to send, it checks whether it has a neighbor node by investigating its NDB. If the neighbor list is empty, a node $n_i$ 1-hop broadcasts a probe message that contains the identifier of a node $n_i$ and the time when it sends the probe message. Then a node $n_i$ starts a wait timer ( $W_P$ ) which is set to the twice time taken for a packet to travel from a node $n_i$ to its maximum transmission distance and waits for a response until $W_P$ expires. If a node $n_j$ receives a probe message, it records the message reception time and calculates the message transmission delay from a node $n_i$ to a node $n_j$ $({\tau }_{ij})$ . After delaying ${\tau }_{ij}$ , a node $n_j$ sends a probe response message to a node $n_i$ . If a node $n_i$ does not receive any probe response message within $W_P$ , it abandons the transmission of a packet.

Figure 3

Nodal behavior when a node sends a packet.

On the contrary, if a node $n_i$ has neighboring nodes, it filters the neighboring nodes according to the distance to a destination node ( $n_t$ ). Let us denote the set of neighboring nodes of a node $n_i$ that are closer to the destination node than a node $n_i$ by $F_i$ . If $F_i$ is not empty, a node $n_i$ selects the next hop node among the nodes in $F_i$ . Specifically, a node $n_i$ sorts the nodes in $F_i$ according to $Q_i(t)$ in an ascending order and constructs a set $Z_i$ that contains the top Z nodes in the sorted $F_i$ . Then, $n_i$ select the next hop $n_j^{\ast }$ that satisfies

$$\begin{array}{cc}& n_j^{\ast }=\underset{n_j\in Z_i}{\arg }\min \left(\frac{{‖i,j‖}^{\alpha }}{‖i,t‖-‖i,j‖}\right),\end{array}$$

(1)

where $‖i,j‖$ is the Euclidean distance between nodes $n_i$ and $n_j$ . After selecting the next hop node, a node $n_i$ attempts to get a chance to send a packet (a specific method for a node to get a chance to send a packet depends on the medium access control protocol adopted for the network interface card used. Various MAC protocols can be used for D2D communications and optimal way of getting a transmission chance can be devised under a specific MAC protocol which is beyond the scope of this paper. Since we are focusing on the packet delivery procedure, we assume that a node can get a chance to send a packet within a reasonable time). Since radio propagation conditions vary dynamically, a packet may not be delivered to the selected next hop. In the case that a node uses a medium access control protocol (MAC) that dictates a node to send an acknowledgement packet (ACK) when it receives a packet, a packet transmission error can be handled easily. In other words, if a sending node $n_i$ does not receive an ACK after sending a packet, it retransmits a packet. After attempting to retransmit a packet M times, $n_i$ gives up packet transmission. For the case that a MAC does not support an ACK, we devise a retransmission strategy by taking advantage of the broadcast nature of a wireless channel. After a node $n_i$ sends a packet, it overhears the channel. If it can hear a packet that it sent within $W_P$ , it considers that the packet it sent is delivered successfully to the next hop. If it cannot overhear the same packet it sent, $n_i$ retransmits the packet. The node $n_i$ attempts to retransmit a packet M times. After that, it gives up retransmission.

If $F_i$ is empty, a node $n_i$ attempts to detour the routing hole. To devise a detour procedure, we adopt our previous work in [34] that relates the position of nodes with a detour success probability. A geometric approach is taken to derive a detour success probability. Using Figure 4, we derive the probability that a node $n_i$ detours successfully through a node $n_j$ . We denote $d_{A,B}$ as the Euclidean distance between points A and B. We assume that a node $n_i$ is located at the point S, $n_j$ is located at the point X, and the destination node $n_t$ is located at the point D. Since the unit disk graph model is assumed, all nodes have the identical transmission radii of r. We denote the point where the circle whose radius is r and is centered at S intersects with the circle whose radius is $d_{S,D}$ and is centered at D by A. Similarly, we denote B as the intersection point between the circle which is centered at X and has a radius of r and the circle which is centered at D and has a radius $d_{S,D}$ . We also denote the intersection point of two circles by C. One circle is centered at S and has a radius of r and the other circle is centered at X and has a radius r.

Figure 4

Detour success area.

The area covered by the circular arcs $AB$ , $AC$ , and $BC$ is defined by the detour success area when $n_i$ selects $n_j$ as the next hop ( $X_{DS}(n_j)$ ). To derive $X_{DS}(n_j)$ , we introduce the following notations. $R_1(n_j)$ is the region covered by the triangle $ABC$ . $R_2(n_j)$ is the area surrounded by the fan shape $BXC$ minus the area covered by the triangle $BXC$ . $R_3(n_j)$ is the region surrounded by the straight line $AB$ and an circular arc $AB$ . $R_4(n_j)$ is the area covered by the straight line $AC$ and an circular arc $AC$ . $R_1(n_j)$ is derived as

$$\begin{array}{cc}& R_{\mathrm{1}}\left(n_j\right)=\sqrt{P_{\mathrm{1}}\left(P_{\mathrm{1}}-d_{A,B}\right)\left(P_{\mathrm{1}}-d_{A,C}\right)\left(P_{\mathrm{1}}-d_{B,C}\right)},\end{array}$$

(2)

where $P_1=(d_{A,B}+d_{A,C}+d_{B,C})/2$ . $R_2(n_j)$ is derived as

$$\begin{array}{cc}& R_{\mathrm{2}}\left(n_j\right)=\frac{r^{\mathrm{2}}}{\mathrm{2}}{\cos }^{-1}\left(\frac{d_{B,X}^{\mathrm{2}}+d_{C,X}^{\mathrm{2}}-d_{B,C}^{\mathrm{2}}}{\mathrm{2}{d}_{B,X}{d}_{C,X}}\right)-\sqrt{P_{\mathrm{2}}\left(P_{\mathrm{2}}-d_{B,X}\right)\left(P_{\mathrm{2}}-d_{C,X}\right)\left(P_{\mathrm{2}}-d_{B,C}\right)},\end{array}$$

(3)

where $P_{\mathrm{2}}=(d_{B,X}+d_{C,X}+d_{B,C})/2$ . Similarly $R_{\mathrm{3}}(n_j)$ is given by

$$\begin{array}{cc}& R_{\mathrm{3}}\left(n_j\right)=\frac{d_{S,D}^{\mathrm{2}}}{\mathrm{2}}{\cos }^{-1}\left(\frac{d_{A,D}^{\mathrm{2}}+d_{B,D}^{\mathrm{2}}-d_{A,B}^{\mathrm{2}}}{\mathrm{2}{d}_{A,D}{d}_{B,D}}\right)-\sqrt{P_{\mathrm{3}}\left(P_{\mathrm{3}}-d_{A,D}\right)\left(P_{\mathrm{3}}-d_{B,D}\right)\left(P_{\mathrm{3}}-d_{A,B}\right)},\end{array}$$

(4)

where $P_{\mathrm{3}}=(d_{A,D}+d_{B,D}+d_{A,B})/2$ . Finally, $R_{\mathrm{4}}(n_j)$ is derived as

$$\begin{array}{cc}& R_{\mathrm{4}}\left(n_j\right)=\frac{r^{\mathrm{2}}}{\mathrm{2}}{\cos }^{-1}\left(\frac{d_{A,S}^{\mathrm{2}}+d_{C,S}^{\mathrm{2}}-d_{A,C}^{\mathrm{2}}}{\mathrm{2}{d}_{A,S}{d}_{C,S}}\right)-\sqrt{P_{\mathrm{4}}\left(P_{\mathrm{4}}-d_{A,S}\right)\left(P_{\mathrm{4}}-d_{C,S}\right)\left(P_{\mathrm{4}}-d_{A,C}\right)},\end{array}$$

(5)

where $P_4=(d_{A,S}+d_{C,S}+d_{A,C})/2$ . Then, $X_{DS(n_j)}$ is derived as

$$\begin{array}{cc}& X_{DS}\left(n_j\right)=R_{\mathrm{1}}\left(n_j\right)+R_{\mathrm{2}}\left(n_j\right)+R_{\mathrm{3}}\left(n_j\right)-R_{\mathrm{4}}\left(n_j\right).\end{array}$$

(6)

If the area covered by a D2D network is $R_{TA}$ and n nodes are uniformly distributed over $R_{TA}$ , the probability that a node exists within $X_{DS}(n_j)$ becomes $p(n_j)=X_{DS}(n_j)/R_{TA}$ . Therefore, the probability that a node $n_i$ detours successfully through a node $n_j$ becomes

$$\begin{array}{cc}& p_i\left(n_j\right)=\mathrm{1}-{\left(\mathrm{1}-p\left(n_j\right)\right)}^{n{X}_{DS}\left(n_j\right)/R_{TA}}.\end{array}$$

(7)

Since n and $R_{TA}$ are global variables, each node cannot know them. However, since $p_i(n_j)$ is the increasing function of $X_{DS}(n_j)$ , a node $n_i$ selects the node $n_k^{\ast }$ as a detour node that satisfies

$$\begin{array}{cc}& n_k^{\ast }=\underset{n_k\notin F_i}{\arg }\max \left(X_{DS}\left(n_j\right)\right).\end{array}$$

(8)

4. Performance Evaluation

In this section, we evaluate the performance of our multihop D2D routing method. We build an event driven simulator using C language for the performance evaluation. Specifically, we compare the performance of the proposed method with the maximum progress method (MaxP), the cost over progress method (CoP), and the congestion-aware forwarder selection method (CAFS), in terms of the end-to-end packet delivery success ratio ( $S_{\mathrm{e}\mathrm{2}\mathrm{e}}$ ), the amount of energy consumed in the network ( $E_c$ ), end-to-end packet transfer delay ( $D_{\mathrm{e}\mathrm{2}\mathrm{e}}$ ), and the number of hops taken from a source node to a destination node ( $H_{\mathrm{e}\mathrm{2}\mathrm{e}}$ ).

We randomly deploy n nodes in 200 m by 200 m rectangular area. The location of each node is configured according to the uniform distribution. In other words, the x-coordinate and the y-coordinate of a node are randomly selected from $[\mathrm{0,200}]$ according to the uniform distribution so as to configure a network topology as a random graph. Since we are focusing on the performance of routing protocols, we do not consider a specific radio interfaces. However, since we are considering a situation where a large number of devices are contending for D2D communication channel, both the cochannel interferences and the interchannel interferences are severe and effective data sending rate of a NIC that is used for multihop D2D communication is far from the maximum transmission rate of the NIC. In addition, we also assume that radio propagation environments are harsh. Thus, we configure the maximum effective transmission distance of a node as $r=10$  m and set an effective packet service rate of a node as 256 Kbps. To reflect the harsh radio propagation environment we also configure $\alpha =4$ and ${\sigma }_{dB}=7$ according to [35]. We set the size of a data packet as 100 bytes. It is common in an ad hoc routing protocol that a node assumes that one of its neighbor nodes does not exist if it does not receive a keep-alive message from the neighbor 3 times successively. Following the practice, we set $K=3$ and $M=K+1$ . After beginning simulations, all the results are obtained after each node constructs its TNDB.

For a given network topology, we randomly select a source node and a destination node. For a given source node and a destination node pair, we apply four different routing methods to deliver a packet under the same condition. For fair comparison, we apply our detour method and reliability method to the other routing schemes. We repeat the same experiment 1,000 times under the same network topology and routing strategy. For each multihop D2D routing trial, we collect $S_{\mathrm{e}\mathrm{2}\mathrm{e}}$ , $E_c$ , $D_{\mathrm{e}\mathrm{2}\mathrm{e}}$ , and $H_{\mathrm{e}\mathrm{2}\mathrm{e}}$ . Then we reconfigure the network topology by randomly deploying n nodes again and repeat the same experiments. We reconfigure the network topology 10 times and calculate the 95th percentiles of the performance metrics with all the simulation results.

Figure 5 shows the end-to-end packet delivery success ratio. The x-axis shows node density which is defined as the average number of nodes within a circle with a radius r. Since MaxP method selects a node that is farthest away from the current sending node as the next hop, it is the most vulnerable to the random fading in a wireless channel. Therefore, $S_{\mathrm{e}\mathrm{2}\mathrm{e}}$ is the smallest when MaxP is applied. On the contrary, CoP selects the next hop by considering the ratio between the transmission power and the progress made to the destination. Therefore, the distance between the current sending node and the next hop becomes the smallest when CoP is used. Since the signal strength decreases as a power of $\alpha =4$ with the distance between a sender and a receiver, the probability that error occurs during packet transmission becomes the smallest when CoP is used. Correspondingly, $S_{\mathrm{e}\mathrm{2}\mathrm{e}}$ is the highest when CoP is applied. The CAFS uses multiple metrics to select the next hop node. In CAFS, the cost metric is inversely proportional to the progress that can be made to the destination whereas it is linearly proportional to the congestion levels of neighbors, forwarding direction, and energy needed to send a packet. Therefore, the progress made to the destination is more influential than the other metrics, which makes the distance between the current sending node and the selected next hop becomes larger than those obtained by CoP and the proposed method. The congestion levels of neighboring nodes have the highest priority when the proposed method selects the next hop. Thus, as the node density increases, it becomes more likely that the distance between the current sending node and the selected next hop obtained by the proposed method is smaller than that obtained by CAFS. Therefore, as the node density increases, $S_{\mathrm{e}\mathrm{2}\mathrm{e}}$ obtained by CAFS becomes smaller than that obtained by the proposed method.

Figure 5

End-to-end packet delivery success ratio.

Figure 6 shows the amount of energy consumed in the network. Since CoP considers the amount of energy needed to send a packet, the amount of energy consumed in the network is the smallest when CoP is used. In the case of the proposed method, the congestion levels of potential next hops are considered first. Therefore, $E_c$ obtained by the proposed method is higher than that obtained by CoP. However, as the number of nodes increases, it becomes more probable that the proposed method selects the node that is closer to the current sending node. Accordingly, $E_c$ becomes smaller as the node density increases.

Figure 6

The amount of energy consumed in the network.

Figure 7 shows the end-to-end packet transfer delay and Figure 8 shows the number of hops taken from a source to a destination. The results are obtained from the packets that are delivered successfully end-to-end. Since MaxP attempts to increase the progress made to the destination as long as possible, it selects the neighboring node that is the closest to a destination (i.e., the farthest neighbor from the current sender) as the next hop. Therefore, $H_{\mathrm{e}\mathrm{2}\mathrm{e}}$ obtained by MaxP is the smallest compared to the other $H_{\mathrm{e}\mathrm{2}\mathrm{e}}$ s obtained by other routing strategies. However, as the distance from a sender to a receiver increases, the received signal strength is more subjected to random errors involved in a wireless channel. Correspondingly, the number of packet retransmissions increases as the distance from the current sender to the next hop increases. In the case of CoP, the next hop is determined not only by the progress made to a packet but also by the amount energy needed to make that progress. Thus, CoP tends to select the node that is close to the current sending node as the next hop. Therefore, the number of hops taken from a source to a destination is the highest when CoP is used. In addition, CoP does not consider nodal delay when it selects the next hop. Therefore, the end-to-end packet transfer delay is the longest when CoP is used.

Figure 7

End-to-end packet transfer delay.

Figure 8

The number of hops taken from a source to a destination.

CAFS selects the next hop by considering multiple metrics. However, CAFS puts more weight on the progress made to a packet than other metrics. On the contrary, the proposed method considers the congestion levels of neighboring nodes first when it selects the next hop. Thus, the distance between the current sending node and the node selected as the next hop by the proposed method may be smaller than those obtained by MaxP and CAFS, which leads to more $H_{\mathrm{e}\mathrm{2}\mathrm{e}}$ . To scrutinize the length of a routing path, we depict the distance ratio in Figure 9. If we denote the set of nodes that comprise a path from a node $n_i$ to a node $n_t$ by $P_{i,t}=\left\{n_i,n_{i+1},\dots ,n_{t-1},n_t\right\}$ , the distance ratio is defined as ${\sum }_{(j=i)}‖j,j+1‖/‖i,t‖$ . We can see that the proposed method takes a roundabout way compared to other methods. Therefore, $H_{\mathrm{e}\mathrm{2}\mathrm{e}}$ obtained by the proposed method is longer than those obtained by MaxP and CAFS. However, since the proposed method minimizes the nodal delay by considering the congestion levels of neighbor nodes, $D_{\mathrm{e}\mathrm{2}\mathrm{e}}$ obtained by the proposed method is the smallest. Specifically, the proposed method can half $D_{\mathrm{e}\mathrm{2}\mathrm{e}}$ on average, compared with CAFS.

Figure 9

The distance ratio ( ${\sum }_{j=i}‖j,j+1‖/‖i,t‖$ ).

5. Conclusions

In this paper, we proposed a fast and energy efficient D2D multihop routing framework. In the framework, the roles of an infrastructure network and a multihop D2D network are separated. In our framework, management packets related to identifying the states of nodes are transferred though an infrastructure network. Since we are using a presence server, there can be a single point of failure problem. However, data packets between nodes are delivered through multihop D2D network to alleviate the burden of an infrastructure network.

In the framework, we also proposed a fast and efficient multihop D2D routing method for a D2D network. The proposed method operates based on the geographic locations of nodes. To expedite the delivery of data packets, the proposed method selects the node that is less congested as the next hop node. In addition, we devised a reliable data transfer algorithm by taking advantage of broadcast nature of a wireless channel for the case where an unreliable medium access control protocol is used.

Through extensive simulation studies, we showed that even though the proposed method takes a roundabout way compared to the other methods, it can reduce the end-to-end packet transmission delay substantially, which leads to the increase in the probability of delivering a packet successfully end-to-end while saving energies of nodes in a D2D network.