# Energy-Efficient Data Transmission in Mobility-Aware Wireless Networks

Authors: Mengmeng Xu; Guixiang Zhang; Xinpei Liang; Hai Zhu; Juanjuan Wang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Data transmission scheme is an effective mode to improve the energy-efficiency in packet delivery. In this paper, we investigate the energy-efficient data transmission over reliable links and unreliable links in mobility-aware wireless networks. The network topologies in mobility-aware wireless networks are changed from one time slot to another, and they could be described by a sequence of static graphs. We first model these network topologies in a time period as a virtual space-time graph. On the virtual space-time graph, energy-efficient data transmission problems over reliable links and unreliable links are defined. The aim of the two data transmission problems is to find a spatial-temporal path with the minimum energy cost. Next, we propose an Energy-Efficient Data Transmission algorithm over Reliable Links (EEDT-RL) to find the optimal space-time path. Based on EEDT-RL, we also develop a heuristic data transmission protocol over unreliable links (named EEDT-UL), in which the path reliability is taken into consideration. Simulation results show that our proposed algorithms perform well in terms of energy cost and transmission count compared with some existing algorithms.


---

## Body

## 1. Introduction

Data transmission scheme is an effective manner to reduce the energy consumption of packet delivery in wireless networks. However, many intractable problems have been imposed in data transmission because of nodes’ mobility, i.e., the network topologies are changed from one time slot to another, which is an inherent characteristic of wireless networks. Specially, the topology connectivity of the mobile network in each time-slot and even the existence of a routing path between two remote nodes could not be guaranteed. Opportunistic or epidemic transmission schemes are effective forwarding manners for packet transmissions between two remote nodes [1–4], in which data packets are forwarded by utilizing the sporadic contacts between two mobile nodes. However, packet transmissions using opportunistic or epidemic transmission schemes may result in plenty of copy transmissions. Actually, opportunistic or epidemic transmission schemes do not exploit the full potential of the mobility. Although the problem of the absence of routing path could be alleviated through opportunistic or epidemic transmission schemes, how to select the relay nodes, i.e., making forwarding decision over time-varying network topologies is still an intractable problem in mobility-aware wireless networks. Therefore, it is imperative to investigate the data transmission problem in mobility-aware networks.In the past decades, energy-efficient data transmission protocols over reliable and/or unreliable links in static networks have been widely investigated, as shown in [5–8]. However, these network protocols are not suitable for the applications in mobile wireless networks due to the frequent link breakage and rebuilding. In mobile wireless networks, most of the researches for routing design have concentrated on the stable and reliable path selection which may have a long duration [9–12]. In these research works, node mobility is assumed in terms of some classical random mobility models, such as random direction model and random way-point model. Due to the high randomness, these researches have overmuch emphasis on the path duration in the packet delivery but neglect the importance of another factor—energy consumption.In the human-centric mobile networks, the temporal characteristics of network topology in many network scenarios could be known a priori. Actually, in [13], the authors show that the potential predictability for human mobility can reach up to 93%. The literature [14] found that about 78%-99% of the vehicle location is predicable. Thanks to the development of cloud computing technique, the authors in [15, 16] investigated the mobility prediction in bike-sharing systems and in public bus systems, respectively. For perpetual trajectory tracking, the authors in [17] propose an energy and mobility-aware scheduling framework to improve the long-term tracking performance. All of these researches validate that the strong regularities are existed in the daily human and vehicle mobility. In these mobility-aware wireless networks, the literatures [18–20] proposed some mobility-aware energy-efficient data transmission schemes. However, these proposed algorithms are based on the connect network topology, and the temporal information of topology change from one time slot to another is not involved explicitly. By exploiting vehicle mobility trajectories, the authors in [21] developed an efficient multicast algorithm in wireless vehicular networks. Using machine learning for mobility prediction, the literature [22] proposed a centralized routing scheme to minimize the overall vehicular service delay. Some other mobility-aware-based network protocols could be found in [23, 24] for low-cost topology control, in [25] for location management, in [26] for clustering, and in [27] for resource allocation.In this paper, we investigate the energy-efficient data transmission problems in mobility-aware wireless networks over reliable links and unreliable links. A series of network topologies, each of which is disconnected with high probability, is modeled as a virtual space-time graph. In this space-time topology graph, a spatial link refers as to a wireless link between two nodes at one time slot; while a temporal link means that a node carries its data packet from one time slot to the next time slot. Data transmission problems over reliable links and unreliable links on the virtual space-time graph are defined, in which the space-time path with minimum energy cost needs to be found. An Energy-Efficient Data Transmission algorithm over Reliable Links (EEDT-RL) is proposed to solve the data transmission problem over reliable links. By extending the EEDT-RL, we also develop a heuristic transmission algorithm over unreliable links, i.e., EEDT-UL. Some simulations are performed to study the performances of our proposed algorithms. Compared with our conference paper in [28], many new research results are added, such as the optimal data transmission algorithm over reliable links, more elegant optimal objective over unreliable links, and more simulation results.The remainder of this paper is organized as follows. We review some of the related works in Section2. Section 3 presents the network model, link model, and energy model. Energy-efficient data transmission over reliable links and unreliable links are investigated in Sections 4 and 5, respectively. We provide some simulations to illustrate our algorithm in Section 6 and conclude the paper in Section 7.


## 2. Related Works

In this section, we summarize some up to date research works related with routing protocol or data transmission in mobility wireless networks.In delay-tolerant mobile networks, the authors in [1] provided a detailed survey of opportunistic transmission algorithms to study the nature of mobility. Specially, it revealed that human mobility is not random at all but have a definite and repetitive pattern. Actually, using opportunistic transmission, a single packet transmission may result in plenty of copies of the packet message. The authors in [29, 30] focused on the controlling two-hop forwarding polices, where the problem concerned the decision on whether or not forwarding a given packet to a specific mobile node. By restricting the number of transmission hops, the proposed algorithms in [29, 30] could markedly reduce the copies in packet dissemination. In UAV-assisted vehicular delay-tolerant networks, the literature [31] developed a routing protocol to improve the reliability of packet transmission by considering both the encounter probability and the persistent connection time. In [32], theoretical upper and lower bounds for the information propagation speed were derived, in which store-carry-forward routing model was used. Considering wireless transmissions and sojourns on node buffers, the authors in [33] computed the packet speed and cost according to utility-based routing rules. However, most of the research results obtained in delay-tolerant mobile networks are based on the assumption of random mobility and do not exploit the full potential of the mobility traces.In mobility-aware networks, a novel graph metric named mobile conductance was conceived to evaluate the information spreading time in [34]. The mobility-connectivity tradeoff was also quantitatively analyzed in [34] to determine how much mobility may be exploited to compensate for network connectivity deficiency. Bedogni et al. in [35] developed a methodology to infer complete trajectories of individual vehicles and then proposed some temporal connectivity algorithms for packet transmissions. In [36], the authors introduced a concept of energy-aware temporal reachability graph (ETRG) and proposed an algorithm to calculate ETRG. According to ETRG, these results revealed the fundamental relations among the system metrics of energy budget, tolerable delay, and data size on the network performance. In [23], a reliable topology design was investigated in delay-tolerant networks with unreliable links. According to the known or predictable network topology, several heuristic algorithms were proposed to build reliable and low-cost network topologies. Nevertheless, the energy-efficient data transmission protocol does not involve explicitly in these works.For data transmission or routing design in mobility-aware networks, the authors in [20] developed a relay selection strategy by utilizing partially predictable mobility, in which the directional correlation of destination movement was considered. Simulations showed that the proposed forwarding strategy could achieve a higher delivery utility compared with a forwarding scheme without mobility prediction. In [21], a trajectory-based multicast (TMC) routing was proposed for efficient multicast in vehicular networks. By exploiting vehicle trajectories, TMC routing could achieve a delivery ratio close to that of the flooding-based approach while the cost is reduced by over 80%. Li et al. in [37] concentrated on the communication services of passengers in the train from the base station. According to the regular mobility of the train, the authors in [37] proposed a quality-of-service-distinguished power allocation algorithm to meet each user’s data rate requirement. In [38], a novel social-based routing approach was proposed, in which a new metric of social energy was introduced by exploiting social behaviors of nodes. Liu et al. in [39] proposed a mobility-aware transmission scheduling scheme, which consists of a relay path planning algorithm and a global time scheduling algorithm. Extensive simulations under realistic human mobility trajectories showed that the transmission scheduling scheme in [39] could achieve high throughput transmission. An aeronautical ad hoc network with rapidly changing topology was modeled as a dynamic graph in [40], and then data transmission problem was formulated as an integer nonlinear programming. A detailed review work is available in the literature [41]. Different from these works, this paper investigates the energy-efficient data transmission problem in mobility-aware wireless networks. Specially, a series of dynamic network topologies is modeled as a virtual space-time graph, which is similar to the literature [23]. The space-time graph model is also utilized in wireless duty-cycle sensor networks for data transmission, as shown in [42, 43]. In our new data transmission problems, both reliable and unreliable links are involved.


## 3. System Models

In this section, we present the network model, link model, and energy consumption model. A description of the key notations is listed in Table1.Table 1
List of key notations.
NotationDescriptionTTime periodGtNetwork topology at time-slotti,jWireless link between nodesi and jGSpace-time graphit−1,jt⟵Spatial linkit−1,it⟵Temporal linkpi,jReliability probability for linki,jpπReliability of pathπNNumber of bits per messageErx,etx,βEnergy consumption parametersαPath attenuation factor


### 3.1. Network Model

In mobile wireless networks, the locations of network nodes are changed over time, resulting in topology evolutions. To describe such evolution, a sequence of static graphs is introduced. Let a period of timeT be divided into discrete and equal time slots, i.e., 1,2,⋯,T. Define the network topology at time-slot t as an undirected graph GtV,Lt, where V=1,2,⋯,n is the set of nodes, and i,j∈Lt represents the wireless link between nodes i and j at time-slot t. The dynamic network over a period of time T could be modeled as a sequence of static graphs Gtt=1,2,⋯,T, which describes the topology evolutions due to node mobility. Figure 1(a) provides an example to show the sequence of snapshots of the network topology at each time slot. Note that the topology connectivity at each time slot in mobile wireless networks could not be guaranteed, which incurs the data transmission over them intractable. Here, we assume that the moving track of each node (such as the smart device in public bus) is known in advance, i.e., the topology graph Gt at time-slot t is predictable.Figure 1
An example of network model.
(a)
A sequence of topology snapshots at each time slot(b)
Virtual space-time topological graphWe introduce a new graph structure associated with the sequence of network topologiesGtt=1,2,⋯,T, named virtual space-time graph GV,L. In this virtual graph G, the virtual node it is the virtualization of node i∈V at the end of time slot t∈0,1,⋯,T. As a consequence, each node i∈V is replaced with T+1 associated virtual nodes. The number of nodes in virtual graph G is equal to nT+1, i.e., V=nT+1. If i,j∈Lt, t=1,⋯,T, two directed edges (or links) are generated in G, that is, it−1,jt⟵∈L and jt−1,it⟵∈L. This kind of link it−1,jt⟵ refers as to a spatial link, meaning that one node i can forward a message to node j at time-slot t. And besides, another kind of link it−1,it⟵, referred as to a temporal link, is defined in the link set L, representing that the node i∈V can carry the message in the t-th time slot. The virtual space-time graph G clearly includes both the spatial information in each time slot and the temporal information due to topology change. Figure 1(b) illustrates the virtual space-time graph of the sequence of topologies in Figure 1(a). In this example, the red path in Figure 1(b) is a space-time path from 40 to 13. That is, the message transmission from node 4 to node 1 needs 3 time slots: node 4 holds its packet at t=1 and sends it to node 3 at t=2, and then node 3 sends it to node 1 at t=3. Note that at most one message could be transmitted within one time slot. That is, we assume that the time slot is only long enough for one message transmission.


### 3.2. Link Model

A wireless linki,j exists at time-slot t, i.e., i,j∈Lt, if and only if the two mobile nodes i and j are located within the transmission range of each other at time-slot t. We assume that a mobile node i always fails to transmit its packet to another node j which is beyond node i’s transmission range, while packet delivery within each other transmission range succeeds with a probability. We define a reliability probability pi,j for each link i,j∈Lt, which means node j can successfully receive a packet sent from node i. The values of reliability probability are influenced by the stochastic nature of wireless channel and/or imperfect mobility prediction. According to the value of pi,j, we define two link models as follows, i.e., reliable link model and unreliable link model.In the reliable link model, if a wireless link isi,j∈Lt, we have pi,j=1; otherwise, pi,j=0. Under this model, data packets transmitted within the transmission range are always succeeded.In the unreliable link model, a wireless linki,j∈Lt connecting two nodes i and j at time-slot t is not necessarily reliable. That is, if a wireless link is i,j∈Lt, we have 0<pi,j≤1; otherwise, pi,j=0. Under this model, data packets were transmitted from node i to node j over a wireless link i,j with a successful reception probability pi,j.A wireless linki,j∈Lt associates with two spatial links, i.e., it−1,jt⟵∈L and jt−1,it⟵∈L, in space-time graph G. Therefore, the reliability probability pi,j of wireless link i,j∈Lt could be converted into pit−1,jt⟵ and pjt−1,it⟵, and we have
(1)pit−1,jt⟵=pjt−1,it⟵=pi,j.For each temporal linkit−1,it⟵ in space-time graph G, it may also have a reliability probability for successfully holding its data packet over one time slot. Actually, if buffer overflow or energy depletion incurs at a mobile node, the node may fail to hold its data packet. However, the failures in holding a packet over one time slot are seldom compared with those in data transmission over spatial link. Therefore, it is reasonable to assume that all temporal links are reliable, i.e., pit−1,it⟵=1 for each i∈V, t∈0,1,⋯,T. We define the reliability of a space-time path π as the production of all links’ reliability in π, i.e., pπ=∏l∈πpl.


### 3.3. Energy Consumption Model

Both sending a message over a spatial link and holding a message over a temporal link incur energy consumption. The energy cost for holding one bit of data message in one time slot for any node is assumed to be a fixed valueE0, i.e., for any temporal link l∈L, the corresponding energy cost for holding a message is El=NE0, where N is the number of bits per message. The energy consumption for sending a massage over a spatial link comes from two parts: transmission and reception. Let Erx be the amount of energy consumption required to receive one bit of data message. The amount of energy consumption for transmitting one bit of data message to r meters away is Etxr. From [44], we have
(2)Etxr=etx+βrα,where etx is the energy consumed by the sender circuit, β is the antenna output energy to reach the receiver unit distance away, and α∈2,4 is the path attenuation factor. We define the energy cost for sending a message over a spatial link l=it−1,jt⟵∈L as
(3)El=NErx+Etxdije−ρt,where dij is the distance between nodes i and j at time-slot t, and ρ is the discount rate in time. The energy cost of a space-time path π is the summation of all links’ energy cost in π, i.e., Eπ=∑l∈πEl.In next two sections, we firstly define the data transmission problems over reliable links and unreliable links in space-time graph and then develop two algorithms to solve the proposed transmission problems.


## 3.1. Network Model

In mobile wireless networks, the locations of network nodes are changed over time, resulting in topology evolutions. To describe such evolution, a sequence of static graphs is introduced. Let a period of timeT be divided into discrete and equal time slots, i.e., 1,2,⋯,T. Define the network topology at time-slot t as an undirected graph GtV,Lt, where V=1,2,⋯,n is the set of nodes, and i,j∈Lt represents the wireless link between nodes i and j at time-slot t. The dynamic network over a period of time T could be modeled as a sequence of static graphs Gtt=1,2,⋯,T, which describes the topology evolutions due to node mobility. Figure 1(a) provides an example to show the sequence of snapshots of the network topology at each time slot. Note that the topology connectivity at each time slot in mobile wireless networks could not be guaranteed, which incurs the data transmission over them intractable. Here, we assume that the moving track of each node (such as the smart device in public bus) is known in advance, i.e., the topology graph Gt at time-slot t is predictable.Figure 1
An example of network model.
(a)
A sequence of topology snapshots at each time slot(b)
Virtual space-time topological graphWe introduce a new graph structure associated with the sequence of network topologiesGtt=1,2,⋯,T, named virtual space-time graph GV,L. In this virtual graph G, the virtual node it is the virtualization of node i∈V at the end of time slot t∈0,1,⋯,T. As a consequence, each node i∈V is replaced with T+1 associated virtual nodes. The number of nodes in virtual graph G is equal to nT+1, i.e., V=nT+1. If i,j∈Lt, t=1,⋯,T, two directed edges (or links) are generated in G, that is, it−1,jt⟵∈L and jt−1,it⟵∈L. This kind of link it−1,jt⟵ refers as to a spatial link, meaning that one node i can forward a message to node j at time-slot t. And besides, another kind of link it−1,it⟵, referred as to a temporal link, is defined in the link set L, representing that the node i∈V can carry the message in the t-th time slot. The virtual space-time graph G clearly includes both the spatial information in each time slot and the temporal information due to topology change. Figure 1(b) illustrates the virtual space-time graph of the sequence of topologies in Figure 1(a). In this example, the red path in Figure 1(b) is a space-time path from 40 to 13. That is, the message transmission from node 4 to node 1 needs 3 time slots: node 4 holds its packet at t=1 and sends it to node 3 at t=2, and then node 3 sends it to node 1 at t=3. Note that at most one message could be transmitted within one time slot. That is, we assume that the time slot is only long enough for one message transmission.


## 3.2. Link Model

A wireless linki,j exists at time-slot t, i.e., i,j∈Lt, if and only if the two mobile nodes i and j are located within the transmission range of each other at time-slot t. We assume that a mobile node i always fails to transmit its packet to another node j which is beyond node i’s transmission range, while packet delivery within each other transmission range succeeds with a probability. We define a reliability probability pi,j for each link i,j∈Lt, which means node j can successfully receive a packet sent from node i. The values of reliability probability are influenced by the stochastic nature of wireless channel and/or imperfect mobility prediction. According to the value of pi,j, we define two link models as follows, i.e., reliable link model and unreliable link model.In the reliable link model, if a wireless link isi,j∈Lt, we have pi,j=1; otherwise, pi,j=0. Under this model, data packets transmitted within the transmission range are always succeeded.In the unreliable link model, a wireless linki,j∈Lt connecting two nodes i and j at time-slot t is not necessarily reliable. That is, if a wireless link is i,j∈Lt, we have 0<pi,j≤1; otherwise, pi,j=0. Under this model, data packets were transmitted from node i to node j over a wireless link i,j with a successful reception probability pi,j.A wireless linki,j∈Lt associates with two spatial links, i.e., it−1,jt⟵∈L and jt−1,it⟵∈L, in space-time graph G. Therefore, the reliability probability pi,j of wireless link i,j∈Lt could be converted into pit−1,jt⟵ and pjt−1,it⟵, and we have
(1)pit−1,jt⟵=pjt−1,it⟵=pi,j.For each temporal linkit−1,it⟵ in space-time graph G, it may also have a reliability probability for successfully holding its data packet over one time slot. Actually, if buffer overflow or energy depletion incurs at a mobile node, the node may fail to hold its data packet. However, the failures in holding a packet over one time slot are seldom compared with those in data transmission over spatial link. Therefore, it is reasonable to assume that all temporal links are reliable, i.e., pit−1,it⟵=1 for each i∈V, t∈0,1,⋯,T. We define the reliability of a space-time path π as the production of all links’ reliability in π, i.e., pπ=∏l∈πpl.


## 3.3. Energy Consumption Model

Both sending a message over a spatial link and holding a message over a temporal link incur energy consumption. The energy cost for holding one bit of data message in one time slot for any node is assumed to be a fixed valueE0, i.e., for any temporal link l∈L, the corresponding energy cost for holding a message is El=NE0, where N is the number of bits per message. The energy consumption for sending a massage over a spatial link comes from two parts: transmission and reception. Let Erx be the amount of energy consumption required to receive one bit of data message. The amount of energy consumption for transmitting one bit of data message to r meters away is Etxr. From [44], we have
(2)Etxr=etx+βrα,where etx is the energy consumed by the sender circuit, β is the antenna output energy to reach the receiver unit distance away, and α∈2,4 is the path attenuation factor. We define the energy cost for sending a message over a spatial link l=it−1,jt⟵∈L as
(3)El=NErx+Etxdije−ρt,where dij is the distance between nodes i and j at time-slot t, and ρ is the discount rate in time. The energy cost of a space-time path π is the summation of all links’ energy cost in π, i.e., Eπ=∑l∈πEl.In next two sections, we firstly define the data transmission problems over reliable links and unreliable links in space-time graph and then develop two algorithms to solve the proposed transmission problems.


## 4. Energy-Efficient Data Transmission over Reliable Links

We now define the energy-efficient data transmission problem over reliable links on the virtual space-time graphGV,L.Definition 1.
Given a source nodes∈V, a destination node d∈V, the aim of energy-efficient data transmission over reliable links is to find a space-time path π with the minimum energy cost from node s0∈V to node dt∈V,0<t≤T.Let the space-time graphG over a period of time T be connected, such that the space-time path π from source node s to destination node d could be found over the time period T. Here, a space-time graph G is connected over time period T if and only if there exists at least one space-time path for each pair of nodes vi0,vjTi,j∈V.Note that, if the time periodT is small, the number of selectable space-time paths is less. For example, in Figure 1(b), if T is equal to 2 time slots, the space-time path between source node s=4 and destination node d=3 is just one, i.e., 40⟶41⟶32. If T is equal to 3 time slots, another selectable path between s=4 and d=3 is added, i.e., 40⟶41⟶42⟶33. With the increasing of time period T, the number of selectable paths is nondecreasing, and then the optimal space-time path which has the minimum energy cost should be found. Therefore, the energy-efficient data transmission problem in a time period T can also be viewed as a tradeoff between energy consumption and transmission delay.Algorithm 1: EEDT-RL.
Input: Gt,s,d,T;Output: π∗,Emin;1: Compute space-time graphG=V,L According to a series of static graph Gt and time period T;2:for each node mt∈Vdo3:Rmt=∅ and Emt=∞4:end for5:k=s0, Ek=0, and N=k6:whilek≠dTdo7:temp=∞;8:for each node it∈V−Ndo9:ifl≜k,it∈Lthen10:    CalculateEl according to the Subsection 3-C;11:else12:El=∞;13:end if14:ifEk+El≤Eitthen15:Rit=Rk∪l;16:Eit=Ek+El;17:end if18:ifEit<tempthen19:temp=Eit and k′=it;20:end if21:end for22:k=k′ and N=N∪k23:end while24: LetEdt be the minimum of Ed1,⋯,EdT25:returnπ∗=Rdt, Emin=Edt.In the data transmission problem over reliable links on the virtual space-time graphGV,L, all virtual nodes i0,i1,⋯,iT in the space-time graph G associate with one node i∈V but at different moment. Therefore, each space-time path π in G that connects node s0 and anyone node dt,0<t≤T constitutes the candidate path set Π. That is, the source node s could transmit its data packet to destination node d at time-slot t across the space-time path π. The solution of data transmission problem over reliable links is to find the space-time path π∗ in Π which has the minimum energy cost. Next, Energy-Efficient Data Transmission algorithm over Reliable Links (EEDT-RL) is developed to solve the new data transmission problem. Algorithm 1 shows the detailed procedure of EEDT-RL.In EEDT-RL, we firstly convert the sequence of static network graphsGtt=1,2,⋯,T into a space-time graph G=V,L. Then, on the space-time graph G, an extension of Dijkstra’s algorithm is implemented to find the space-time path with minimum energy cost from node s0 to dT. In EEDT-RL, Rit is comprised of the links of the optimal space-time path from source node s0 to node it with the minimum energy cost Eit. In our assumption, the space-time graph G over a period of time T is connected. Thus, the space-time path π from node s0 to node dT could be found over the time period T, which means EdT<∞. Finally, we find the minimum value of Ed1,⋯,EdT and denote it by Edt. Then, the optimal space-time path from source node s to destination node d over the time period T is Rdt with the minimum energy consumption Edt. Since the space-time graph G has nT+1 virtual nodes, the computational complexity of EEDT-RL is On2T+12=On2T2 in the worst case. Note that the link l∈L is a directed link, and the arrow is omitted in the EEDT-RL algorithm.


## 5. Energy-Efficient Data Transmission over Unreliable Links

In this section, energy-efficient data transmission problem over unreliable links is defined on the virtual space-time graphGV,L.Definition 2.
Given a source nodes∈V, a destination node d∈V, the aim of energy-efficient data transmission over unreliable links is to find a space-time path π with the minimum energy cost and the maximum path reliability from node s0∈V to node dt∈V,0<t≤T.The energy-efficient data transmission problem over unreliable links has two optimal objectives: the minimum energy cost(4)Eπ∗=∑l∈π∗El=minEππ∈Πand the maximum path reliability
(5)pπ∗=∏l∈π∗pl=maxpππ∈Π.Here,Π is the candidate path set in which each space-time path connects node s0 and anyone node dt,0<t≤T. To solve the biobjective optimization problem, the second objective is rewrote as
(6)−ln∏l∈π∗pl=∑l∈π∗−lnpl=min−lnpππ∈Π.By following a popular approach used to deal with biobjective optimization problems, the two objectives (4) and (6) have been transformed into a single objective, using an importance weight factor λ [45]. Then, define a composite link weight for each link l∈L as
(7)wl=λEmaxEl−1−λlnpminlnpl,where Emax and pmin are the maximum of El and the minimum of pl for l∈L, respectively. Note that Emax and pmin are normalization factors used to have the same range for the two objectives.Based on minimizingwπ=∑l∈πwl on the space-time graph G, an extension version of Dijkstra’s algorithm could be employed, which is similar to Algorithm 1. If the optimal space-time path Rdt with minimum composite weight is found, the corresponding energy cost and path reliability could be further calculated. It should be noted that, because of the link unreliability, if the data packet from source node s is failed to be forwarded to the next node by one intermediate node j at time-slot t, this intermediate node j will become the source node at time-slot t+1 and find the optimal space-time path again in the remaining time-slots. We call this heuristic data transmission method over unreliable links as EEDT-UL. In the worst case, each transmission has failed, and then the path finding algorithm needs to be executed T times. Therefore, the computational complexity of EEDT-UL is On2T3.


## 6. Simulations

In this section, some simulations are provided to illustrate the proposed EEDT-RL and EEDT-UL algorithms. In a500×500m2 network region, some mobile nodes are distributed randomly at the beginning. A sequence of network topologies is generated in the following manner. All nodes move according to the random direction mobility model. That is, each node moves from the current position to the next position with an arbitrary direction and a random velocity selected from the range 0,50m per time slot. When the mobile node hits the network region boundary, its mobile direction is reversed. By recording each node’s position at each time slot, a sequence of static network graphs could be derived according to the maximum transmission range rmax of each node. The source and destination pairs are selected randomly for each topology instance. Note that the trajectory prediction is not within the scope of this paper. Thus, in our simulation, the random direction mobility model is employed just for generating each node’s mobility trajectory in a time period. Some other important simulation parameters are listed in Table 2 [23, 44].Table 2
Values of various parameters in simulations.
ParameterValueNumber of nodes (n)10~30Time period (T)10 time slotsEnergy for holding a messageE05 nJ/bitEnergy for receiver circuitErx180 nJ/bitEnergy for transmitter circuitetx80 nJ/bitPath attenuation factorα2Antenna output energyβ100 pJ/bitNumber of bits per messageN256 bytesMaximum transmission rangermax150 mTime discount rateρ0Figure2 provides an example of topology evolutions at some consecutive time slots with the number of nodes n=20. It can be seen that the network topology is varied from one time slot to another and is often disconnected in each time slot. Therefore, it is impossible to transmit data packet in a single time slot between two remote nodes. We should consider a sequence of network topologies in multiple time slots for the design of data transmission scheme.Figure 2
An example of topology evolutions at four consecutive time slots.
(a)(b)(c)(d)The proposed EEDT-RL and EEDT-UL algorithms are evaluated according to the following performance metrics: energy cost, actual transmission count, and path reliability. Actual transmission count between source and destination is equal to the number of spatial links in the space-time path, while path reliability is the production of all links’ reliability, which is defined in Subsection3.2. We compare these performance metrics with two common algorithms, which are often employed for data transmission in mobility networks, i.e., epidemic-based transmission and distance-based transmission. These two common algorithms have many versions in different literatures [3, 46]. In our simulation, we extract the main idea of these two algorithms and make appropriate modifications to fit the space-time graph model. In epidemic-based transmission, the nodes carrying data packet infect the nodes which do not receive the packet utilizing the communication opportunity at each time slot, until the destination node receives this packet. In distance-based transmission, a node, which does not receive the packet, with the minimum distance to the destination is selected as the next forwarding node.


### 6.1. Simulations on EEDT-RL

In this simulation, we first increase the number of nodes from 10 to 30 and keep time period at 10 time slots. Figures3(a) and 3(b) show the variation trend of energy cost and transmission count versus number of nodes. Before executing the proposed EEDT-RL and two comparison algorithms, a sequence of static topology graphs should be converted into a space-time graph, as shown in Subsection 3.1. These algorithms are implemented on 1000 various space-time graphs, and in each space-time graph, one source-destination pair is selected randomly. From Figure 3, the proposed EEDT-RL has the minimum energy cost and the minimum transmission count compared with the epidemic-based and distance-based algorithms. Actually, EEDT-RL can select better communication opportunities for data transmission and hold data packet (do not transmission) for saving energy when the communication opportunities is worse. With the increase of number of nodes, the two metrics of energy cost and transmission count are stable relatively in EEDT-RL and distance-based algorithm, while these two metrics are increasing rapidly in epidemic-based algorithm.Figure 3
Performance metrics of EEDT-RL vs. number of nodes.
(a)
Energy cost(b)
Transmission countThe time periodT is varied from 8 to 12 time slots to study the impact of time period on energy cost and transmission count. The curves of energy cost and transmission count vs. time period are reported in Figures 4(a) and 4(b), in which the number of nodes is 20. Similarly, the proposed EEDT-RL generates the most energy-efficient space-time path. From Figure 4(a), the energy cost decreases gradually with the increase of time period in EEDT-RL; that is, a longer time period will induce a more energy-efficient data transmission.Figure 4
Performance metrics of EEDT-RL vs. time period.
(a)
Energy cost(b)
Transmission count


### 6.2. Simulations on EEDT-UL

For the unreliable link model, the reliability probability of a spatial link is assigned a random value from 0.6 to 1 in this simulation. We first investigate the tradeoff between energy cost and path reliability of the proposed EEDT-UL by varying the weight factorλ from 0.1 to 0.9. The time period and number of nodes are set as T=10 time slots and n=20. Figures 5(a) and 5(b) plot the curves of energy cost and path reliability vs. weight factor λ, respectively. The link weight changes from 0.1 to 0.9, reflecting the ever-increasing importance of energy cost in data transmission. From Figure 5, the reduction of energy cost comes at the expense of path reliability. We can see the tradeoff between energy cost and path reliability via the adjustment of weight factor λ. It should be noted that the energy cost of the space-time path generated by EEDT-UL may not be the actual energy consumption. Because of the unreliable links, the data transmission may fail, and a new space-time path will be generated. If the path reliability is high, the failure probability of data transmission is low, and then the calculated energy cost is equal to the actual value.Figure 5
Tradeoff between energy cost and path reliability.
(a)
Energy cost(b)
Path reliabilityThe metrics of energy cost and transmission count in EEDT-UL are similar with these in EEDT-RL. Thus, we study the path reliability in EEDT-UL in contrast to epidemic-based and distance-based data transmission. Figures6(a) and 6(b) show the simulation results of path reliability vs. number of nodes and time period, respectively. Here, we set time period as 10 time slots in Figure 6(a), number of nodes as 20 in Figure 6(b), and weight factor as 0.5 for both. From Figure 6, the proposed EEDT-UL has the maximum path reliability compared with the two common algorithms.Figure 6
Path reliability of EEDT-UL vs. number of nodes and time period.
(a)
Path reliability vs. number of nodes(b)
Path reliability vs. time period


## 6.1. Simulations on EEDT-RL

In this simulation, we first increase the number of nodes from 10 to 30 and keep time period at 10 time slots. Figures3(a) and 3(b) show the variation trend of energy cost and transmission count versus number of nodes. Before executing the proposed EEDT-RL and two comparison algorithms, a sequence of static topology graphs should be converted into a space-time graph, as shown in Subsection 3.1. These algorithms are implemented on 1000 various space-time graphs, and in each space-time graph, one source-destination pair is selected randomly. From Figure 3, the proposed EEDT-RL has the minimum energy cost and the minimum transmission count compared with the epidemic-based and distance-based algorithms. Actually, EEDT-RL can select better communication opportunities for data transmission and hold data packet (do not transmission) for saving energy when the communication opportunities is worse. With the increase of number of nodes, the two metrics of energy cost and transmission count are stable relatively in EEDT-RL and distance-based algorithm, while these two metrics are increasing rapidly in epidemic-based algorithm.Figure 3
Performance metrics of EEDT-RL vs. number of nodes.
(a)
Energy cost(b)
Transmission countThe time periodT is varied from 8 to 12 time slots to study the impact of time period on energy cost and transmission count. The curves of energy cost and transmission count vs. time period are reported in Figures 4(a) and 4(b), in which the number of nodes is 20. Similarly, the proposed EEDT-RL generates the most energy-efficient space-time path. From Figure 4(a), the energy cost decreases gradually with the increase of time period in EEDT-RL; that is, a longer time period will induce a more energy-efficient data transmission.Figure 4
Performance metrics of EEDT-RL vs. time period.
(a)
Energy cost(b)
Transmission count


## 6.2. Simulations on EEDT-UL

For the unreliable link model, the reliability probability of a spatial link is assigned a random value from 0.6 to 1 in this simulation. We first investigate the tradeoff between energy cost and path reliability of the proposed EEDT-UL by varying the weight factorλ from 0.1 to 0.9. The time period and number of nodes are set as T=10 time slots and n=20. Figures 5(a) and 5(b) plot the curves of energy cost and path reliability vs. weight factor λ, respectively. The link weight changes from 0.1 to 0.9, reflecting the ever-increasing importance of energy cost in data transmission. From Figure 5, the reduction of energy cost comes at the expense of path reliability. We can see the tradeoff between energy cost and path reliability via the adjustment of weight factor λ. It should be noted that the energy cost of the space-time path generated by EEDT-UL may not be the actual energy consumption. Because of the unreliable links, the data transmission may fail, and a new space-time path will be generated. If the path reliability is high, the failure probability of data transmission is low, and then the calculated energy cost is equal to the actual value.Figure 5
Tradeoff between energy cost and path reliability.
(a)
Energy cost(b)
Path reliabilityThe metrics of energy cost and transmission count in EEDT-UL are similar with these in EEDT-RL. Thus, we study the path reliability in EEDT-UL in contrast to epidemic-based and distance-based data transmission. Figures6(a) and 6(b) show the simulation results of path reliability vs. number of nodes and time period, respectively. Here, we set time period as 10 time slots in Figure 6(a), number of nodes as 20 in Figure 6(b), and weight factor as 0.5 for both. From Figure 6, the proposed EEDT-UL has the maximum path reliability compared with the two common algorithms.Figure 6
Path reliability of EEDT-UL vs. number of nodes and time period.
(a)
Path reliability vs. number of nodes(b)
Path reliability vs. time period


## 7. Conclusions

In this paper, the energy-efficient data transmissions over reliable links and unreliable links in mobility-aware wireless networks are investigated. A sequence of network topologies deduced by mobility prediction, each of which is usually disconnected, was modeled as a virtual space-time graph. Data transmission problems over reliable links and unreliable links on space-time graph were defined, in which a space-time path with the minimum energy cost would be found. Then, EEDT-RL was proposed to find the optimal space-time path under the reliable link model. Under the unreliable link model, we developed a heuristic data transmission method, named EEDT-UL, which could achieve the tradeoff between energy cost and path reliability. The simulation results showed that our proposed algorithms perform well in terms of energy consumption and transmission count compared with some existing algorithms. Specially, we can further improve the energy-efficiency of data transmission by increasing the number of nodes and/or prolonging the time period, due to that these ways could result in more communication opportunities for selection.



---

*Source: 8683854-2022-05-24.xml*