1
Sharing-oriented Resource Allocation for Multiplatoon's Groupcasting and Unicasting Communication based on the Transmission Reliability Chung-Ming Huang1, and Yen-Hung Wu1, Duy-Tuan Dao2 1
Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan 2 Faculty of Electronics and Telecommunications Engineering, The University of Danang-University of Science and Technology, Vietnam Email: {huangcm, wuyh}@locust.csie.ncku.edu.tw; [email protected] Corresponding author: Duy-Tuan Dao
Abstract— Resource allocation in vehicular platoons is challenging due to high vehicle mobility and limited spectrum resources. To improve spectral efficiency, resource sharing is commonly adopted. In 5G-based platoons, the Platoon Leader Vehicle (PLV) employs groupcasting to disseminate control messages to Platoon Member Vehicles (PMVs). When the groupcasting power is insufficient, a selected PMV acts as a Platoon Relay Vehicle (PRV) to extend the communication range. In addition, PMVs transmit unicast control messages to their following vehicles for emergency coordination. This work proposes a sharing-oriented resource allocation method for both groupcasting and unicasting communication based on transmission reliability. For groupcasting, the proposed Tripartite Matching for Platoon Groupcasting (TMPG) algorithm applies tripartite matching to allocate subchannels shared by a PLV/PRV and corresponding individual entities (IEs), which denote cellular users or non-platooning vehicles. For unicasting, the proposed Resource Sharing for Platoons’ Unicasting (RSPU) algorithm (i) firstly partitions PMVs into clusters by considering intra-cluster interference and then (ii) uses tripartite matching to allocate a subchannel that is shared by a cluster of PMVs and the corresponding IE. Simulation results demonstrate that the proposed methods outperform benchmark schemes in terms of Quality of Service (QoS) satisfaction, allocated subchannels, and spectral efficiency. Keywords— Resource Allocation, Resource Sharing, Platoon Groupcasting, Multi-platoon Communications, Tripartite Matching.
1. Introduction Platooning is a group of vehicles coordinating their speeds and distances while moving together. The effectiveness of communication, i.e., high reliability, within the platoon plays a key role in platooning [1][2][3]. That is, the implementation of platooning depends on the reliable and timely sharing of information among the composed Platoon Vehicles (PVs) of a platoon to make decisions based on the latest data regarding road and traffic conditions [4][5]. For the platooning communication, a lot of previous works (i) use Platoon Leader Vehicle’s (PLV’s) broadcasting to deliver messages to Platoon Member Vehicles (PMVs) that are inside PLV’s broadcasting range and (2) use PMV’s unicasting to forward PLV’s broadcasted messages from one PMV to its adjacent PMV hop by hop for those PMVs that are outside PLV’s broadcasting range. Several resource allocation schemes for platooning have been proposed. For PLVs, (1) broadcasting subchannels are allocated orthogonally to PMVs’ subchannels [4][6]; and (2) broadcasting subchannels can be shared with uplink subchannels of individual entities (IEs)1, such as cellular users or non-platooning vehicles [6][7]. The designated subchannel for the vehicle-to-vehicle (V2V) link between two adjacent intra-platoon PMVs can be shared with (a) other intra-platoon PMVs but not with other platoon PMVs [8], (b) other inter-platoon PMVs but not with other intra-platoon PMVs [8], or (c) both intra and inter-platoon PMVs [4][9][10]. In addition, subchannels allocated for IEs can also be shared with the PMVs [6][11][12].
1. An individual entity (IE) is defined as a mobile object, e.g., a smart phone or a non-platooning vehicle that does not join any platoon.
2 5G NR C-V2X’s platoon groupcast, which is like multicast, is a communication technique for broadcasting messages to a particular group of vehicles. Groupcasting communication aims to provide efficient and reliable communication between the PLV and PMVs to ensure timely exchange of critical messages for a platoon [13][14][15][16][17]. In long platoons, PLV messages may suffer from severe path loss and fading, resulting in poor reception at distant PMVs. To mitigate this issue, a Platoon Relay Vehicle (PRV) is employed to re-groupcast the PLV’s messages to PMVs beyond PLV’s direct coverage, thereby extending the effective groupcasting range [18]. To tackle the relay issue, (i) some relay selection methods were proposed to achieve the minimum transmitted power [19], the minimum latency [6], or the maximum communication range [20]; (ii) some works used relay to do retransmission to reduce the failed communication [20]; (iii) some works studied the performance for different relay situations, e.g., using Road Side Unit (RSU) as the relay [22], [23], and considering link quality in both transmitted directions [24][25]. Most existed studies concentrate only on delivering PLV control messages by allocating spectrum resources for PLV broadcasting/groupcasting and, in some cases, unicast forwarding by PMVs outside the PLV’s coverage. PMVs within the groupcasting range are typically ignored, as they are assumed to directly receive PLV message [4]. However, current approaches do not simultaneously consider resource allocation for groupcast and unicast communications, even though PMVs also require unicast exchanges with neighboring PMVs for safety-critical coordination. Therefore, a practical platooning system should jointly allocate resources for both groupcast PLV’s groupcasting transmissions and unicast PMVs’ unicasting communications. These limitations motivate us to explore a structured resource-sharing method based on the technique of tripartite matching. The criteria that this work adopts for platooning’s resource allocation is the transmission reliability concern. To achieve the goal of reducing the amount of used radio resource, i.e., subchannels, this work considers both transmission reliability of (1) PLVs’ and PRV’s groupcasting for transmitting PLV’s control messages and (2) PMVs’ unicasting for transmitting PMV’s control messages to its adjacent PMV in the proposed resource allocation methods that adopt the principle of resource sharing for platooning. Since platoons can share resources with individual entities (IEs), i.e., cellular phones or non-platooning vehicles that do not join any platoon, the proposed resource allocation method is devised to maximize intra-platoon transmission reliability while meeting IEs' Quality of Service (QoS) requirements. For groupcasting communication of PLVs/PRVs, a tripartite matching problem is formulated to allocate subchannels that maximize platoon’s transmission reliability while considering the QoS constraints of IEs by optimizing the transmitted power of PLVs/PRVs. It is assumed that only one single IE can share the subchannel allocated to a PLV or a PRV. Resource allocation for PMVs’ unicasting communication is formulated as the other tripartite matching problem, for which one subchannel can be shared with multiple PMVs and one IE to improve spectrum utilization. The contributions in this work are summarized as follows. - A new Tripartite Matching for Platoon Groupcasting (TMPG) algorithm that optimizes subchannel allocation for both PLVs/PRVs and IEs is devised. This method concentrates on improving the spectrum efficiency and transmission reliability of message dissemination from PLV and PRV to PMVs. - A Resource Sharing for Platoons’ Unicasting (RSPU) algorithm, which clusters PMVs to manage intra-cluster interference and optimizes resource allocation, is devised to enhance spectrum utilization and transmission reliability. The effectiveness of the proposed
3 method is demonstrated through quantitative results, i.e., the improved Quality of Service (QoS) satisfaction rate, the reduced number of allocated subchannels, and the enhanced spectral efficiency, compared to the other methods. - This work advances the state-of-the-art of platoon communications by addressing both groupcasting and unicasting resource allocation, which are technical challenges in 5G networks. The rest of the paper is organized as follows: Section 2 presents related works. Section 3 presents the system model for a platoonbased network. Section 4 mathematically formulates the transmission reliability problems for both PLVs/PRVs and PMVs. Section 5 presents the proposed algorithms. Section 6 presents the performance analysis and compares it with the other methods. Finally, Section 7 gives a conclusion and future work. 2. Related Work Related work of the proposed method is presented in this Section. 2.1. Relay Selection In [7], the authors introduced a technique to minimize the latency of groupcasting communication within platoons, in which a platoon manager, instead of the PLV, controls platoon’s vehicles.. In the work, the available uplinked subchannels can be utilized by vehicles acting as the platoon manager role to broadcast messages. An algorithm that optimizes joint resource allocation for 5G-V2X systems and coding rates was proposed. Based on the results, the proposed method achieves (i) the optimal performance for intraplatoon groupcast latency comparing with others’ works and (ii) complexity reduction because the method’s operation can converge within three iterations. However, using a PMV as the platoon manager will result in the inability to respond to emergency situations. In [19], the authors improved the dissemination of a platoon leader’s cooperative awareness messages by optimizing relay selection and power control. Using the proposed method, an optimal relay is chosen to enhance channel conditions, while power control ensures link quality. Both centralized and distributed methods were proposed, and the experimental results show that the transmission power can be reduced. However, the communication reliability issue was not clearly addressed. In [23], the authors developed a Markov model for changing transmission links (vehicle-to-RSU and intra-vehicle). The authors studied the effect of various communication approaches, which are (1) C-V2V relaying and (2) RSU relaying. Then, the control and communication systems were designed for platooning, and the effectiveness of the suggested method using different relaying strategies was evaluated. According to the simulation outcomes, the proposed method, which uses the C-V2V relaying technique, can decrease the distance of intra-vehicular than the other methods, including (1) the method without relaying and (2) the method using the RSU relaying technique, while maintaining the stipulated control and communication prerequisites. However, the proposed method that uses the C-V2V relaying technique needs more subchannels than the compared method that uses the RSU relaying technique, which thus could perform poorly in the spectral efficiency. 2.2. Resource Sharing In [11], the authors focused on optimizing spectrum sharing and managing interference in the multi-platoon scenario. The proposed method allocates dedicated resources to PLVs for (i) sending messages to Base station (BS) and (ii) broadcasting messages to their own PMVs. PMVs share spectrum resources with intra/inter-platoon’s PMVs to relay their messages to adjacent PMVs within their own
4 platoons. A Hypergraph-based Resource Allocation and Interference Management (HRAIM) algorithm was proposed to allocate resources to PMVs based on the needed SINR threshold. The proposed method has the better effect in the aspects of spectral efficiency and sum data rate compared with using the conventional graph coloring scheme. However, the authors only considered the resource allocation for PMV unicasting and did not study the resource allocation for PLVs in their study. In [12], the authors introduced a spectrum-sharing method between V2V and nearby V2I vehicles for platoon longitudinal control. The proposed method jointly optimizes spectrum allocation and power control, for which each V2V vehicle selects one V2I vehicle to share a subchannel. The performance result shown that the proposed method can achieve the throughput gains through power optimization. However, the proposed method only considered V2I–V2V pairs and did not address more spectrum-sharing scenarios. In [6], the authors proposed a resource allocation technique for the multi-platoon scenario utilizing the graph-theory-based control scheme, where a platoon has (1) one PLV that broadcasts messages and (2) multiple PMVs that use unicast to forward PLV’s broadcasted messages to PMVs outside PLV’s broadcasting range. A 2-STage Resource Allocation (2-STRA) approach was proposed to enhance spectrum effectiveness. In the 1st stage, a resource allocation algorithm that aims to maximize the broadcasted range of PLVs by employing the minimum transmitted power was devised for PLVs. In the 2 nd stage, a scheme was proposed to cluster PMVs at first. Afterward, a tripartite hypergraph is formulated utilizing the proposed control strategy. Then, the problem of resource allocation for PMVs was resolved using two proposed algorithms, both of which were based on the aforementioned tripartite hypergraph. According to the performance evaluation results, the proposed 2-STRA method outperforms the benchmarks in terms of PLV transmission delay, power control efficiency, and transmission rate. Nevertheless, the proposed method does not use the relay vehicle to re-broadcast PLV’s messages. Thus, it results in the lower spectrum efficiency and the need for more subchannels. In [15], the author concentrated on developing the joint allocation of bandwidth and computation resources within a Platoon Digital Twin Network (PDTN), which considers the mobility of vehicles and real-time data requirements. However, the reliance on advanced neural networks results in high computational complexity, which may not be feasible in all scenarios. The paper [18] employed a deep reinforcement learning (DRL) approach for optimizing resource allocation in the multi-platoon vehicular network. The authors formulated the problem as a multi-objective optimization problem and solved it by dividing it into multiple optimization subproblems. Each subproblem was then resolved using a DRL-based method called Contribution-based DualClip Proximal Policy Optimization (CD-PPO). Simulation results demonstrated that the proposed method outperforms existed methods in terms of both successful communication rate and quality of service. However, DRL algorithms, especially deep learning-based ones, are computationally intensive, which may limit their practical application. In [26], Kim et al. introduced a resource allocation framework with spectrum reuse for platooning, prioritizing intra-platoon communications to ensure reliability while allowing resource sharing among platoons. However, the approach mainly targeted on the single-platoon scenario and did not explicitly address simultaneous groupcasting and unicasting in the multi-platoon scenario. Overall, the groupcasting approach can be used to maximize the effective use of available resources by simultaneously sending the same information to all vehicles in a platoon, which can reduce redundant transmissions and conserve bandwidth; unicasting, which needs specific resource allocation to meet each vehicle’s communication requirement, can ensure that critical messages are delivered
5
Fig. 2. The communication configuration in a platoon. Fig. 1. An example of the platooning configuration.
with the necessary bandwidth and power. That is, applying relay selection and resource sharing in platoon-based vehicular networks is needed to optimize network efficiency and performance, but there are still several challenges to be resolved. 3. The System Model This Section describes the details of the system model for the proposed method. The system model is designed to explicitly capture the interactions among platoon leader/relay vehicles, individual entities, and subchannels, which are essential for enabling a matchingbased resource allocation framework. Notations used in the system model are depicted in Table 1. 3.1 The Network Model The defined network model includes (i) one Base Station (BS), (ii) 𝑀 platoons, in which a platoon’s PVs can consist of one PLV, some PMVs and one optional PRV, and (iii) 𝐶 individual entities. An illustration of the platooning configuration is shown on Fig. 1. Referring to Fig. 2, let there be 𝑉 PVs in platoon 𝑚, where PVs are numbered from 0 to 𝑉 − 1 beginning from the PLV, i.e., 𝑃𝑉 is the PLV, and 𝑃𝑉 to 𝑃𝑉
are PMVs, which is denoted as 𝑃𝑀𝑉 to 𝑃𝑀𝑉
, respectively.
Let 𝑅 be PLV’s groupcasting range, which covers PMVs 1 to 𝑛 , i.e., PMVs 1 to 𝑛 can directly receive the groupcasted messages transmitted from PLV. For the PMVs that are outside PLV’s groupcasting range , 𝑃𝑀𝑉
is selected as the PRV to re-groupcast the
messages it received from PLV to PMVs 𝑃𝑀𝑉
= 𝑉 − 1, it indicates that platoon m’s 𝑃𝐿𝑉
to 𝑃𝑀𝑉
can groupcast its messages to all of its PMVs; however, if 𝑛
. Referring to Fig. 2, if 𝑛
< 𝑉 − 1, it indicates that platoon m’s 𝑃𝐿𝑉 cannot groupcast its messages
to all of its PMVs and thus vehicle 𝑃𝑀𝑉 , which is the farthest PMV in the range of PLV’s groupcasting, can play the PRV role to regroupcast PLV’s messages to PMVs, 𝑃𝑀𝑉 , 𝑖 = 𝑛 + 1, . . , 𝑉 − 1. 3.2
The Communication Model The resource allocation mode that the work adopts is Mode 1 of 5G NR C-V2X. That is, the proposed resource allocation method
is executed in the BS. Let the network bandwidth be composed of K orthogonal subchannels denoted by the set 𝕂 = {1,2, … , 𝐾} and each subchannel 𝑘 contains several resource blocks (RBs). The subchannel’s usage principle adopted in this work is as follows: (i) a PLV or a PRV cannot share its subchannel with any PMV but can share its subchannel with one IE’s uplinked subchannel. (ii) other inter-platoon PMVs can reuse the subchannel utilized by a given PMV and intra-platoon PMVs under some constraints. (iii) No subchannel sharing among IEs. (iv) An IE can share its subchannel with either a PLV/PRV or some PMVs. As a result, the subchannels allocated for platoon 𝑚 are as follows: (1) One for V2I communication between the BS to PLV. The BS assigns an orthogonal spectrum resource specifically for the PLV, which can only be utilized by the PLV. (2) One for the PLV’s groupcast, for which the PLV can share its allocated subchannel with an IE for spectrum efficiency. (3) One for the PRV’s groupcast, for which the PRV also can share its allocated subchannel with an IE for spectrum efficiency.
6 TABLE 1 NOTATIONS USED IN THE SYSTEM MODEL AND PROBLEM FORMULATION. Notation PV PLV PRV PMV 𝑀 𝕄 𝐶 ℂ ℂ ℂ 𝑉 𝑅 𝑛 𝐾 𝕂 𝕂 𝑑, 𝐺 ℎ α 𝛽, ℎ, 𝑋 𝑥 , 𝑌 𝑦 , 𝑧 𝑆𝐼𝑁𝑅 , , σ 𝑆𝐼𝑁𝑅 , 𝐼, 𝐼, 𝐼, 𝑃 𝑅, , 𝑅, 𝑃𝑟 , 𝛾 𝜃 𝑅𝑒𝑙-𝑔 𝑅𝑒𝑙-𝑢 , 𝑟 𝛿 𝕋 𝕋 𝕊 ℝ ℕ 𝕊 𝑈 ℚ
Description Platoon Vehicle. Platoon Leader Vehicle Platoon Relay Vehicle Platoon Member Vehicle Number of platoons. The set of platoons. Number of individual entities. The set of individual entities. The set of individual entities that share subchannels with PLVs/PRVs. The set of individual entities that aren’t shared subchannels with PLVs’ groupcasting or PRVs’ groupcasting. Number of vehicles in platoon 𝑚. PL’s groupcasting range. Number of vehicles in platoon m’s PLV groupcasting range. Number of subchannels. The set of subchannels. The set of subchannels that aren’t used by PLVs’ groupcasting and PRVs’ groupcasting. The intra-platoon spacing between vehicle 𝑖 and vehicle 𝑗 of platoon 𝑚. The power gain constant introduced by transmission equipments. The complex Gaussian random variable representing Rayleigh fading. The path loss exponent. The random variable describing the channel gain’s uncertainty. The statistical average channel gain. The allocation of subchannel 𝑘 to platoon vehicles in the complete network. The allocation of subchannel 𝑘 to platoon 𝑚’s vehicle 𝑗’s unicasting. The allocation of subchannel 𝑘 to PLV’s or PRV’s groupcasting link The allocation of subchannel 𝑘 to platoon 𝑚’s PLV/PRV groupcasting, where 𝑔 = 0 (1) denotes PLV (PRV). The allocation of subchannel 𝑘 to individual entity 𝑐. The SINR from platoon m’s vehicle 𝑖 to vehicle 𝑗 over subchannel 𝑘. The power of the additive white Gaussian noise (AWGN) The SINR from the transmitting individual entity 𝑐 to the BS over subchannel 𝑘. The interference of platoon m’s PLV over subchannel 𝑘. The interference of platoon m’s PRV over subchannel 𝑘. The interference of platoon m’s vehicle 𝑗 over subchannel 𝑘. The maximum threshold of the transmitted power. The obtaining data rate from platoon m’s vehicle 𝑖 to vehicle 𝑗 over subchannel 𝑘. The obtaining data rate from BS to individual entity 𝑐 over subchannel 𝑘. The successful transmission probability from platoon m’s vehicle 𝑖 to vehicle 𝑗 over subchannel 𝑘. the SINR requirement of each PM’s unicasting. The successful transmission probability threshold. The groupcasting transmission reliability of platoon 𝑚’s vehicle 𝑗. The unicasting transmission reliability of platoon 𝑚’s vehicle 𝑗. The selected relay vehicle for platoon 𝑚. the SINR requirement of each individual entity The set of candidate matchings. The set of sorted candidate matchings. The set of resulted matchings. The vector of PRV’s index of each platoon. The set of PMVs that need to do unicasting. The resulted matching of the previous iteration. The number of clusters at the beginning. The set of clusters, where 𝑄 stores the PMVs that belong to the i-th cluster after partition.
At most (𝑉 − 2)2 subchannels are assigned to PMVs in platoon 𝑚. These subchannels can be shared with (i) an IE and (ii) other intra-platoon and/or inter-platoon PMVs, excluding adjacent intra-platoon PMVs, i.e., subchannel used by PMV 𝑃𝑀 cannot be used by PMVs 𝑃𝑀
and 𝑃𝑀
of the same platoon.
3.3. The Channel Model The Rayleigh fading and free space path-loss model are adopted to model the wireless channel. The channel gain ℎ , from transmitting vehicle 𝑖 to receiving vehicle 𝑗 in platoon 𝑚 is calculated as follows: ℎ , = G ∗ 𝑑 ,
α
∗ (ℎ ) = 𝛽 , ∗ ℎ , , where G
designates the power gain constant introduced by the transmission equipment, ℎ ~ 𝐶𝑁(0,1) designates a complex Gaussian random 2. Since the PLV, which is denoted as 𝑃𝑉 , can groupcast the messages to platoon vehicles, the PLV does not need a subchannel to communicate with 𝑃𝑉 . Since each 𝑃𝑉 , 𝑖 = 1. . 𝑉 -2, needs a subchannel to send its messages to its follow-up 𝑃𝑉 , it needs (𝑉 -2) subchannels totally for PMVs.
7 variable indicating Rayleigh fading, 𝑑 , designates the distance from platoon m’s vehicle 𝑖 to platoon m’s vehicle 𝑗, α designates the path loss factor, 𝛽 , is a random variable describing the channel gain’s uncertainty, ℎ , is the statistical average channel gain. In the work for vehicular network, the slow fading components, including path loss and shadowing, which vary slowly over time, are considered, while fast fading is not explicitly modeled. The reason is that the resource allocation operates over time scales much larger than the coherence time of fast fading. Therefore, the impact of fast fading is handled in the physical layer rather than incorporated into the higher-layer resource allocation framework [20]. Matrix 𝑋 = 𝑥 ,
∀ ,
∈ {0,1}
∗
denotes the situation of assigning subchannel 𝑘 to PVs in the network, where 𝑥 , = 1
indicates PMV 𝑗 of platoon 𝑚 using subchannel 𝑘; otherwise, 𝑥 , = 0. Matrix 𝑌 = 𝑦 ,
∀ ,
∈ {0,1}
∗
, where 2 denotes PLV
and PRV, represents the situation of assigning subchannel 𝑘 to PLV’s/PRV’s groupcasting of platoon 𝑚, 𝑦 , = 1 indicates the vehicle of platoon 𝑚 using subchannel 𝑘 for groupcasting, 𝑔 = 0/1 denotes PLV/PRV ; otherwise, 𝑦 , = 0. Matrix 𝑍 = [𝑧 ]∀ ∈ {0,1} ∗ , where 𝐾 denotes the number of subchannels, 𝐶 denotes the number of IEs, 𝑧 = 1 denotes assigning subchannel 𝑘 to IE 𝑐. The SINR that PLV (𝑖 = 0) or PRV (𝑖 = 1) vehicle 𝑖 groupcasts messages to PMV 𝑗 over subchannel 𝑘 is denoted as follows:
𝑆𝐼𝑁𝑅 , , =
𝑃 ∗ℎ,
(1)
𝜎 +𝐼,
where 𝑃 designates the transmitted power of platoon 𝑚’s PLV/PRV, ℎ , designates the power gain from the PLV/PRV i to PMV 𝑗 in platoon 𝑚, σ designates the power of the white Gaussian noise (AWGN), 𝐼 , designates the interference from IE 𝑐, which shares subchannel 𝑘 with the PLV/PRV of platoon 𝑚. 𝐼 , is formulated as follows: 𝐼 , = ∑
𝑧 ∗ 𝑃 ∗ ℎ , , , subject to ∑
𝑧 = 1,
where 𝑧 designates the allocation of subchannel 𝑘 to IE 𝑐, 𝑃 designates the transmitted power of IE 𝑐, ℎ , , designates the channel gain from IE 𝑐 to the PLV/PRV of platoon 𝑚 over subchannel 𝑘. Equation (3𝑎) means that PLV’s/PRV’s groupcasting subchannel can only be shared with one IE. For the intra-platoon communication, the SINR that PMV 𝑗 − 1 (1 ≤ j − 1 ≤ 𝑉 − 2) transmits messages to PMV 𝑗 over subchannel 𝑘 is represented as follows: 𝑆𝐼𝑁𝑅 𝑗 − 1, (ii) ℎ
,
, ,
=
∗ σ
,
, where (i) 𝑃
designates the transmitted power of platoon 𝑚’s PV
,
designates the channel gain of the V2V link from transmitting PMV 𝑗 − 1 to receiving PMV 𝑗 over subchannel 𝑘 in
platoon 𝑚 and (iii) 𝐼 , designates the total co-channel interference from other PMVs or IE over subchannel 𝑘. 𝐼 , is formulated as follows:
𝐼, =
𝑥 , ∗𝑃 ∗ℎ , ,
+
,
𝑥
,
∗𝑃
∗ℎ
, , ,
+
𝑧 ∗𝑃 ∗ℎ , ,
(2)
,
subject to 0≤𝑃
≤𝑃
0≤𝑃 ≤𝑃 𝑥 , ∗𝑥 , ≠ 1, 1 ≤ 𝑖 ≤ 𝑉 − 1
(2𝑎) (2b) (2c)
8 𝑧 =1
(2d)
where (i) the first part of Equation (2) is for intra-platoon: 𝑥 , denotes assigning subchannel 𝑘 to platoon 𝑚’s vehicle 𝑖 , 𝑃
denotes
the transmitted power of platoon 𝑚’s vehicle 𝑖 , ℎ , , represents the channel power gain from platoon 𝑚’s vehicle 𝑖 to platoon 𝑚’s vehicle 𝑗 over subchannel 𝑘; (ii) the second part of Equation (2) is for inter-platoon: 𝑥 𝑚 ’s vehicles 𝑖 , 𝑃
denotes the transmitted power of platoon 𝑚 ’s vehicle 𝑖 , ℎ
, , ,
,
denotes assigning subchannel 𝑘 to platoon
represents the channel power gain from platoon
𝑚 ’s vehicle 𝑖 to platoon 𝑚’s vehicle 𝑗 over subchannel 𝑘; (iii) the third part of Equation (2) is for IE: 𝑧 denotes assigning subchannel 𝑘 to IE 𝑐, 𝑃 denotes the transmitted power of IE 𝑐 over subchannel 𝑘, ℎ , , represents the channel power gain from IE 𝑐 to platoon m’s vehicle 𝑗 over subchannel 𝑘. Equations (2a) and (2b) constrain the transmitted power of PMVs to not exceed the maximum threshold. Equation (2c) ensures that any two adjacent PMVs within the same platoon cannot transmit on the same subchannel. Equation (2d) restricts a PMV’s unicasting subchannel to be shared with only one IE. The SINR from IE 𝑐 to BS using subchannel 𝑘 is formulated as follows: 𝑆𝐼𝑁𝑅 , =
∗ σ
, where (i) 𝑃 is IE 𝑐’s transmitted power, (ii) ℎ denotes the channel power gain from IE 𝑐 to BS and (iii) ,
𝐼 , is the total co-channel interference from a PLV’s groupcasting, a PRV’s groupcasting, or some PMVs’ unicasting that share subchannel 𝑘 with IE 𝑐. 𝐼 , is formulated as follows:
𝐼, =
𝑥 , ∗𝑃 ∗ℎ, , +
𝑦 , ∗𝑃 ∗ℎ , ,
(3)
subject to 0≤𝑃 𝑥 , ∗𝑥 ,
(3𝑎)
≤𝑃 ≤𝑃
(3b)
≠ 1, 1 ≤ 𝑗 ≤ 𝑉 − 1
(3c)
𝑦 , ≤1
𝑥 ,
∧
𝑦 ,
(3d)
≠1
where 𝑥 , denotes the allocation of subchannel 𝑘 to platoon 𝑚’s vehicles, 𝑃
denotes the transmitted power of platoon 𝑚’s vehicle 𝑗,
ℎ , , denotes the channel power gain from platoon 𝑚’s vehicle 𝑗 to IE 𝑐 over subchannel 𝑘, 𝑦 , denotes assigning subchannel 𝑘 to PLV’s or PRV’s groupcasting link of platoon 𝑚, 𝑃 denotes the transmitted power of PLV’s/PRV’s groupcasting over subchannel 𝑘, ℎ , , denotes the (groupcasting) channel gain from platoon m’s PLV (𝑔 = 0) or PRV (𝑔 = 1) vehicle to IE 𝑐 over subchannel 𝑘, Equation (3a) limits the transmitted power to the maximum threshold; (3b) prevents adjacent PMVs from using the same subchannel; (3c) allows an IE to share its subchannel with at most one PLV/PRV groupcasting; and (3d) restricts an IE’s subchannel to either one PLV/PRV groupcasting or multiple PMV unicasting links; ⋁ PMV’s unicasting; ⋁
⋁
⋁
𝑥 , denotes the assignment situation of subchannel 𝑘 for
𝑦 , denotes the assignment situation of subchannel 𝑘 for PLV’s or PRV’s groupcasting.
9 The obtained bit rate of the vehicle 𝑗 of platoon 𝑚 from the transmitting PLV/PRV of platoon 𝑚 over subchannel 𝑘 is derived as follows: 𝑅 , , = 𝑙𝑜𝑔 (1 + 𝑆𝐼𝑁𝑅 , , ). The obtained bit rate of PMV 𝑗 of platoon m from PMV 𝑖 of platoon 𝑚 over subchannel 𝑘 is derived as follows: 𝑅 , , = 𝑙𝑜𝑔 (1 + 𝑆𝐼𝑁𝑅 , , ). The obtained bit rate in the BS from the transmitting IE 𝑐 over subchannel 𝑘 is derived as follows: 𝑅 , = 𝑙𝑜𝑔 (1 + 𝑆𝐼𝑁𝑅 , ). 4. Problem Formulation In this Section, the problems of maximizing transmission reliability for both (i) PLV’s/PRV’s groupcasting and (ii) PMV’s unicasting are formulated. Achieving the wireless link’s transmission reliability can be done by guaranteeing the successful transmission’s probability from vehicle 𝑖 to vehicle 𝑗 of platoon 𝑚, i.e., the corresponding link’s SINR is greater than the pre-defined SINR threshold, which can be expressed as follows: 𝑃𝑟 , = 𝑃𝑟𝑜𝑏 𝑆𝐼𝑁𝑅 , , ≥ 𝛾
≥ 𝜃 , where (i) 𝛾
is the pre-defined SINR threshold and (ii) 𝜃
is the pre-
defined probability threshold. Let 𝑃𝑟 , be the successful transmission probability from vehicle 𝑖 to vehicle 𝑗 in platoon 𝑚. Then, the transmission reliability 𝑅𝑒𝑙𝑔 from PLV/PRV to PMV j in platoon 𝑚 of the single-relay-vehicle’s situation3 is as follows: 𝑅𝑒𝑙-𝑔 =
The transmission reliability 𝑅𝑒𝑙-𝑢
,
vehicle’s situation is as follows: 𝑅𝑒𝑙-𝑢
𝑃𝑟 , , 𝑤ℎ𝑒𝑛 𝑃𝑀𝑉 𝑗 𝑖𝑠 𝑖𝑛 𝑃𝐿𝑉’𝑠 𝑔𝑟𝑜𝑢𝑝𝑐𝑎𝑠𝑡𝑖𝑛𝑔 𝑟𝑎𝑛𝑔𝑒. 𝑃𝑟 , , 𝑤ℎ𝑒𝑛 𝑃𝑀𝑉 𝑗 𝑖𝑠 𝑜𝑛𝑙𝑦 𝑖𝑛 𝑃𝑅𝑉’𝑠 𝑔𝑟𝑜𝑢𝑝𝑐𝑎𝑠𝑡𝑖𝑛𝑔 𝑟𝑎𝑛𝑔𝑒.
(4)
from PMV 𝑗 − 1 to its adjacent PMV 𝑗, 2 ≤ 𝑗 ≤ 𝑉 − 1, in platoon 𝑚 of the single-relay,
= 𝑃𝑟
where 𝑃𝑟
,
,
is the successful transmission probability from PMV 𝑗 − 1 to its
neighboring PMV 𝑗 in platoon 𝑚. The objective is to find the PRV in each platoon that can maximize reliability. For each platoon, the 𝒱
PRV selection problem is modeled as follows: 𝑚𝑎𝑥 ∑
(𝑅𝑒𝑙-𝑔 + 𝑅𝑒𝑙-𝑢
, ), where 𝑟
is the selected relay vehicle for platoon
𝑚, and then it can be transformed as follows: 𝒱
𝑚𝑎𝑥
𝑃𝑟𝑜𝑏 𝑆𝐼𝑁𝑅 , , ≥ 𝛾
+ 𝑃𝑟𝑜𝑏 𝑆𝐼𝑁𝑅
, ,
≥ 𝛾
, 𝑖𝜖{0, 𝑟 }
(5)
Equation (5) can be expanded as the following form: 𝒱
𝑚𝑎𝑥
(𝑃𝑟𝑜𝑏
𝑃 ∗ℎ, ≥ 𝛾 𝜎 +𝐼,
+ 𝑃𝑟𝑜𝑏
𝑃
∗ℎ , ≥ 𝛾 𝜎 +𝐼,
)
(6)
where 𝑖 designates the groupcasting vehicle, which is either a PLV (𝑖 = 0) or a PRV (𝑖 = 𝑟 ), 𝑃 designates the transmitted power of platoon 𝑚’s groupcasting vehicle, ℎ , designates the channel power gain from the groupcasting vehicle to the receiving PMV 𝑗 (1 ≤ 𝑗 ≤ 𝑉 − 1 ) in platoon 𝑚, 𝐼 , designates the interference from the IE, which shares subchannel 𝑘 with the groupcasting vehicle, 𝑃 designates the transmitted power of platoon 𝑚’s vehicle 𝑗 − 1, ℎ
,
designates the channel power gain of unicasting from the
transmitting vehicle 𝑗 − 1 to the receiving vehicle 𝑗 over subchannel 𝑘 in platoon 𝑚, 𝐼 , designates the total co-channel interference from other PMVs or IE over subchannel 𝑘, 𝛾
designates the pre-defined SINR threshold.
3. In this work, the maximum transmitted power of PLV and PRV’s groupcasting is set to be able to cover at least half of platoon vehicles in a platoon with the maximum interference caused by the individual entity because of resource sharing, i.e., the proposed method’s groupcasting can always cover all platoon vehicles in a platoon with at most one PRV..
10
∞
Fig. 3. (a) The graph of Equation (19), which shows that ∫ 𝑒 = 1; (b) the graph of Equation (9), where the gray area represents the probability value of Equation (9).
Then, Equation (6) can be further transformed to the following one: 𝒱
𝑚𝑎𝑥 ∑
(𝑃𝑟𝑜𝑏
∗ , ∗ ,
≥ 𝛾
∗
+ 𝑃𝑟𝑜𝑏
,
, ∗
,
≥ 𝛾
(7)
)
,
subject to (7a) (7b) (7c) (7d)
1≤𝑛 ≤𝑉 −1 1≤𝑟 ≤𝑛 0≤𝑃 ≤𝑃 ≤𝑃 𝑥 , ∗𝑥 , ≠ 1, 1 ≤ 𝑗 ≤ 𝑉 − 1
(7e)
𝑦 , ≤1
𝑥 ,
∧
𝑦 ,
(7f)
≠1
(7g)
𝑧 ≤1
𝑆𝐼𝑁𝑅 , ≥ 𝛿 (7h) 𝑆𝐼𝑁𝑅 , , ≥ 𝛾 (7i) where ℎ denotes the statistical average channel gain, 𝛽 denotes the random variable describing the channel gain’s uncertainty. In Equation (7), constraint (7a) means that the last PMV 𝑛 inside PLV’s groupcasting range of platoon 𝑚 should be one of platoon m’s composed vehicles, (7b) means that platoon 𝑚’s PRV is in the groupcasting range of platoon 𝑚’s PL, (7c) denotes that (i) the transmitted power of groupcasting and unicasting can not surpass the maximum threshold and (ii) groupcasting’s transmitted power is greater than unicasting’s transmitted power, (7d) means that any two adjacent PMVs in the same platoon cannot use the same subchannel, (7e) means that a subchannel 𝑘 can be used by at most one groupcasting vehicle, (7f) means that a subchannel 𝑘 can only be used by either one PL’s or one PR’s groupcasting or some PMs’ unicasting, (7g) means that a subchannel 𝑘 can be used by at most one IE, (7h) is the QoS requirement of each IE, (7i) is the QoS requirement of each PM’s unicasting. The successful transmission probability in Equation (7) can be rewritten as follows: 𝒱
𝑚𝑎𝑥 ∑
(𝑃𝑟𝑜𝑏 𝛽 , ≥
∗(
, )
∗ ,
+ 𝑃𝑟𝑜𝑏 𝛽
,
≥
∗( ∗
, )
)
(8)
,
Since 𝛽 , , which describes the channel gain’s uncertainty, has an exponential distribution with a mean of one, which follows the probability density function 𝑓(𝑥) =
𝑒 , 𝑓𝑜𝑟 𝑥 ≥ 0 . Equation 𝑓(𝑥) is depicted in Fig. 3-(a). 0 , 𝑓𝑜𝑟 𝑥 < 0
According to the Fundamental Theorem of Calculus: ∫ 𝑒 ∫ 𝑒
= (−𝑒
) − (−𝑒
depicted in Fig. 3-(b)):
𝑑𝑥 = (−𝑒
) − (−𝑒
). Thus, the following Equation can be derived:
) = 0 + 1 = 1. Then, Equation (8) can be rewritten as follows, for which the corresponding Figure is
11
Fig. 4 An illustration of the tripartite matching. 𝑃𝑟𝑜𝑏 𝛽 , ≥
∞
∗ σ +𝐼,
𝛾
=
𝑃 ∗ℎ,
∗(σ
, )
𝑒
𝑑𝑥
(9)
∗ , ∗ σ
∗ σ
,
∗ ,
= (−𝑒 ∞ ) − −𝑒
∗(σ
,
∗ ,
=0+𝑒
=𝑒
, )
∗ ,
Therefore, the objective function, which is in Equation (7), for solving the problem of maximizing transmission reliability can be transformed as follows: 𝒱
𝑚𝑎𝑥
(𝑃𝑟𝑜𝑏 𝛽 , ≥
𝛾
∗ (𝜎 + 𝐼 , ) 𝑃 ∗ℎ,
+ 𝑃𝑟𝑜𝑏 𝛽
,
≥
𝛾
∗ (𝜎 + 𝐼 , ) 𝑃
∗ℎ
), 𝑖𝜖{0, 𝑟 }
(10)
,
Refer to Equation (9), Equation (10) is equal to:
𝑚𝑎𝑥 ∑
𝒱
⎛ ⎜𝑒
∗ σ ∗
∗ σ
, ,
, ′
∗
+𝑒
⎞ ⎟ , 𝑖𝜖{0, 𝑟 }
,
subject to
0≤𝑃
≤𝑃
≤𝑃
(11)
⎝ ⎠ where 𝑃 is the transmitted power of vehicle 𝑖, which is either the PLV or PRV, 𝐼 , designates the interference from the IE that shares subchannel 𝑘 with the PLV or PRV, 𝐼 , requirement 𝛾
designates the total co-channel interference over subchannel 𝑘 . Since (1) the SINR
, (2) the power of the AWGN σ , (3) the transmitted power of unicasting 𝑃 and (4) the statistical average channel
gain ℎ in Equation (11) are fixed, Equation (11) is equal to the following one: 𝒱
𝑚𝑖𝑛 ∑
,
𝒱
+∑
𝐼,
, 𝑖𝜖{0, 𝑟 },
(12)
where the first part is for PL’s or PR’s groupcasting and the second part is for PM’s unicasting. 5. The Proposed Method In this Section, two algorithms used in the proposed method to solve the problems formulated in Section IV are presented in detail. 5.1. PLV/PRV’s Subchannel Allocation The first part of Equation (12), i.e., the one for PLV’s groupcasting, is solved as follows. (i) One subchannel is assigned to a platoon for PLV’s groupcasting; (ii) the other one is assigned to a platoon for PRV’s groupcasting optionally, which depends on the existence of the PRV in a platoon. Thus, 𝑚𝑖𝑛 ∑
𝒱
,
= 𝑚𝑖𝑛 ∑
𝒱
∗
,,
, 𝑖𝜖{0, 𝑟 }, where 𝑐 is the IE sharing subchannel 𝑘 with PLV
or PRV 𝑖. Since at most two subchannels are allocated per platoon for PLV and PRV groupcasting, the aforementioned Equation is thus able to be formulated as a tripartite matching problem among subchannels, PLV/PRVs, and IEs, for which an illustrated configuration is depicted in Fig. 4. Refer to Fig. 4, (i) three types of vertices and (ii) the number of each type’s vertex in a tripartite matching graph
12 Algorithm 1 Tripartite Matching for Platoon Groupcasting (TMPG)
Function PLV-IE-CH𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 (ℂ, 𝕂, 𝕄)
● Input: ℂ individual entities, 𝕂 subchannels and 𝕄 platoons. ● Output: resource allocation matching set 𝕊. 1. 𝕋 ← {} // 𝕋 temporarily stores available matching {(𝑐, 𝑘, 𝑚, 𝑔), 𝑥}, where (1) (𝑐, 𝑘, 𝑚, 𝑔) denotes the matching of having IE 𝑐 and platoon PLV (𝑔=0) or PRV (𝑔=1) vehicle of platoon 𝑚 to share subchannel 𝑘 and (2) 𝑥 denotes the upper bound of the transmitted power. 2. 𝕋 ← 𝑃𝐿𝑉-𝐼𝐸-𝐶𝐻𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔(ℂ, 𝕂, 𝕄) 3. 𝕋 ← 𝑆𝑜𝑟𝑡(𝕋, 𝑥) //Sort elements in 𝕋 descendingly based on 𝑥. 4. 𝕊 ← { } 5. 𝕊 ← 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔(𝕋, 0) 6. ℝ ← [𝑅 , 𝑅 , … , 𝑅 ] = [−1, −1, … , −1] //ℝ is used to store the PRV’s index of each platoon. 7. for 𝑚 = 1: 𝑀 do 8. 𝑝 ← {𝑥 | {(𝑐 , 𝑘 , 𝑚, 0), 𝑥 } ∈ 𝕊} 9. 𝑖←1 //𝑖 is used to temporary store the index of the farthest PMV that is in PLV’s groupcasting range. 10. 𝑓 ← 𝑓𝑎𝑙𝑠𝑒 // 𝑓 is used to check whether the farthest PMV in PLV’s groupcasting range is found or not. 11. While 𝑖 ≤ 𝑉 −1 and 𝑓 = 𝑓𝑎𝑙𝑠𝑒 do
1. 2. 3. 4.
𝕋 ← {} foreach 𝑘 in 𝕂 do foreach 𝑐 in ℂ do for 𝑚 = 1: 𝑀 do
5.
𝑆𝐼𝑁𝑅 , = σ
6.
if constraints (h) of Equation (7) is satisfied then
7.
𝑥 ← min(𝑃
12.
𝑆𝐼𝑁𝑅𝑜,𝑖,𝑘′ =
∗
,
,
∗
σ
,
)
, ,
8. 9. 10. 11. 12. 13.
//calculate the upper bound of PLV’s transmitted power. 𝕋 ← 𝕋 + {(𝑐, 𝑘, 𝑚, 0), 𝑥} end if end for end foreach end foreach return 𝕋
Function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 (𝕋, 𝑔) 1. 2. 3. 4. 5.
.
,𝑘′
if 𝑆𝐼𝑁𝑅 , , > 𝛾 then 𝑖 ← 𝑖 +1 else ℝ[𝑚] ← 𝑖 − 1 𝑓 ← 𝑡𝑢𝑟𝑒 end if end while end for 𝕋←{} 𝕋 ← 𝑃𝑅𝑉-𝐼𝐸-𝐶𝐻𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔(ℂ, 𝕂, 𝕄, ℝ) 𝕋 ← 𝑆𝑜𝑟𝑡(𝕋, 𝑥) //Sort elements in 𝕋 descendingly based on 𝑥. 24. 𝕊 ← 𝕊 + 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔(𝕋, 1) 25. return 𝕊;
∗
13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23.
6. 7. 8. 9. 10. 11. 12.
𝕊 ← {} 𝑖𝕋 ← 0 //𝑖𝕋 is used to store the index of 𝕋’s elements. while (𝑖𝕋 < |𝕋|) or (𝕄 ≠ ∅) do if 𝑐 ∈ ℂ 𝑎𝑛𝑑 𝑘 ∈ 𝕂 𝑎𝑛𝑑 𝑚 ∈ 𝕄 in 𝕋[𝑖𝕋 ] then 𝕊 ← 𝕊 + 𝕋[𝑖𝕋 ] //allocate subchannel 𝑘 to entity 𝑐 and PLV (PRV), where input parameter 𝑔 = 0 (1), vehicle of platoon 𝑚. ℂ ← ℂ\𝑐 𝕂 ← 𝕂\𝑘 𝕄←𝕄\𝑚 end if 𝑖𝕋 ← 𝑖𝕋 + 1 end for return 𝕊
Function PRV-IE-CHMatching (ℂ, 𝕂, 𝕄, ℝ) 1. 2. 3. 4. 5.
𝕋 ← {} foreach 𝑘 in 𝕂 do foreach 𝑐 in ℂ do for 𝑚 = 1: 𝑀 do if ℝ[𝑚] ≠ −1 then
6.
𝑆𝐼𝑁𝑅 , =
∗ σ
,
7.
if constraints (h) of Equation (7) is satisfied then
8.
𝑥 ← min(𝑃
∗
,
σ
)
ℝ[ ], ,
9. 10. 11. 12. 13. 14. 15.
//calculate the upper bound of PRV’s transmitted power. 𝕋 ← 𝕋 + {(𝑐, 𝑘, 𝑚, 1), 𝑥} end if end if end for end foreach end foreach return 𝕋
(TMG) configuration are as follows: (1) 𝐶 individual entities, (2) 𝐾 subchannels and (3) 𝑀 platoons, i.e., there are (a) 𝑀 PLVs and (b) at most 𝑀 PRVs. Let groupcasting vehicle 𝑔 share its subchannel with IE 𝑐, the QoS requirement for IE 𝑐 can be formulated as follows: 𝑆𝐼𝑁𝑅 , =
𝑃 ∗ℎ ≥ 𝛿 σ +𝐼 ,
⇒𝐼, ≤
𝑃 ∗ℎ −σ 𝛿
(13)
Accordingly, the maximum transmitted power of the groupcasting vehicle can be calculated as follows:
𝑃𝑐 ∗ ℎ𝑐
𝑃
∗ℎ , ,
2
−σ 𝑃 ∗ℎ 𝑚𝑔 𝛿𝑡ℎ𝑟 ≤ − σ ⇒ 𝑃𝑔 ≤ 𝑚𝑔 𝛿 ℎ 𝑔,𝑐,𝑘
(14)
13
Fig. 5. An example input of the TMPG algorithm.
The objective of the proposed Tripartite Matching for Platoon Groupcasting (TMPG) algorithm, which is called as TMPG hereafter, is to obtain a matching result of the tripartite matching problem. The TMPG algorithm is explained as follows. Line 2 calls function PLV-IE-CH 𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 to find all candidate matchings, which are put in 𝕋 , for PLV groupcasting. Function PLV-IECH𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 derives the corresponding PLV’s transmitted power when the IE’s SINR constraint, i.e., constraint (h) in Equation (7), is satisfied, for which the smaller value of (i) PLV’s derived transmitted power using Equation (14) and (ii) the maximum transmitted power 𝑃
is assigned because the transmitted power cannot be bigger than the maximum power 𝑃
. Line 3 sorts the elements in
set 𝕋, i.e., all candidate matchings for PLV groupcasting, based on PL’s transmitted power, i.e., the value of 𝑥, from high to low, i.e., descendently. Line 5 calls function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 to find all resulted from matchings for PLV groupcasting. Function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 iteratively picks up the candidate matching that has the 𝑖𝕋th highest transmitted power: If entity 𝑐, PLV (PRV) of platoon 𝑚 and subchannel 𝑘 have not been matched, then add the matching to set 𝕊; then remove 𝑐 , 𝑘 and 𝑚 from ℂ, 𝕂 and 𝕄 respectively in Lines 7 to 9 of function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 because they have been allocated. Line 6 of the TMPG algorithm initiates a vector ℝ, where 𝑅 , 𝑖 = 1. . 𝑀, to store the index of the PRV. Line 6 sets initial value of 𝑅 as −1 to denote that PLV’s groupcasting range of platoon 𝑚 can cover all of platoon 𝑚’s PMVs, i.e., platoon 𝑚 does not need to find the PRV. Lines 7 to 20 of the TMPG algorithm find the PRV for each platoon. Line 8 of the TMPG algorithm finds the transmitted power of platoon 𝑚’s PLV. Lines 11 to 19 of the TMPG algorithm find the farthest PMV in PLV’s groupcasting range, for which the perceived PLV’s SINR of the corresponding PMV is still greater than the threshold 𝛾 . Lines 13 to 18 of the TMPG algorithm check whether the 𝑖
PMV’s
SINR constraint is satisfied or not; if the answer is negative, then (i) the PMV whose index is 𝑖−1 is the PRV of platoon 𝑚 and (ii) the checking for the remaining PMVs is stop; otherwise, it continues to check the next PMV. Lines 21 to 25 of the TMPG algorithm add all available candidate matchings that can satisfy the IE’s SINR constraint to set 𝕋. Line 22 of the TMPG algorithm calls function PRVIE-CHMatching to find all candidate matchings for PRV groupcasting. Function PRV-IE-CHMatching derives the corresponding PRV’s transmitted power when the IE’s SINR constraint, i.e., constraint (h) in Equation (7), is satisfied, for which the smaller value of (i) PLV’s derived transmitted power using Equation (14) and (ii) the maximum transmitted power 𝑃 the transmitted power cannot be bigger than the maximum power 𝑃
is assigned (on Line 8) because
. Line 23 of the TMPG algorithm sorts the elements in set 𝕋
based on PRV’s transmitted power, i.e., the value of x, from high to low, i.e., descendently. Line 24 of the TMPG algorithm calls function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 to find all resulted matchings for PRV groupcasting. Function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 iteratively picks up the candidate matching that has the 𝑖𝕋 th highest transmitted power: If entity 𝑐, PRV of platoon 𝑚 and subchannel 𝑘 have not been matched, then add the matching to set 𝕊; then remove 𝑐 , 𝑘 and 𝑚 from ℂ , 𝕂 and 𝕄 respectively in Lines 7 to 9 of function
14
𝒌𝟏
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝒌𝟓
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝑚
28.2
32.1
29.4
42.1
37.5
20.1
30.5
𝑚
23.8
26.6
44.8
30.4
31.4
41.3
28.4
𝑚
25.4
30.5
35.2
25.1
40.2
22.3
25.4
𝑚
23.9
29.6
42.6
33.5
21.1
36.6
35.6
𝑚
23.1
30.6
31.7
30.4
37.2
27.5
14.5
𝑚
23.4
29.8
39.6
27.6
21.6
24.6
38.6
𝒌𝟐
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝒌𝟔
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝑚
27.2
23.1
22.4
32.1
32.7
24.1
20.5
𝑚
26.4
35.6
35.6
31.4
27.1
42.6
22.2
𝑚
27.4
25.5
33.2
35.7
34.3
32.3
24.1
𝑚
28.5
38.6
44.6
28.6
39.6
36.6
27.1
𝑚
28.1
29.9
31.5
31.4
33.3
30.8
21.1
𝑚
26.9
29.5
40.3
26.6
31.4
30.6
27.3
𝒌𝟑
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝒌𝟕
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝑚
30.5
29.4
37.4
44.4
31.4
42.5
25.2
𝑚
27.6
28.4
36.1
38.9
37.5
30.6
24.6
𝑚
38.9
35.1
39.5
24.3
22.5
43.5
24.6
𝑚
28.6
33.6
36.6
22.6
30.6
33.6
25.7
𝑚
41.6
36.6
34.6
39.6
44.2
42.6
35.6
𝑚
27.6
38.5
28.4
42.7
39.9
35.6
44.6
𝒌𝟒
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝒌𝟖
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝑚
39.6
28.6
26.9
22.2
21.6
38.6
31.6
𝑚
35.2
32.1
29.4
30.5
37.5
36.4
25.3
𝑚
26.6
34.3
40.3
42.8
26.9
25.2
43.2
𝑚
23.1
30.5
35.2
25.1
40.2
28.8
25.4
𝑚
34.8
36.1
24.9
40.1
38.8
44.2
37.5
𝑚
30.4
29.7
31.7
27.2
39.9
19.1
25.5
𝒌𝟏
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝒌𝟓
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝑚
32.1
40.2
42.1
37.5
30.5
𝑚
44.8
30.4
31.4
41.3
𝑚
30.5
35.2
40.2
𝑚
42.6
33.5
𝑚
30.6
31.7
30.4
37.2
𝑚
39.6
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
32.1
32.7
35.7
34.3
(a)
𝒌𝟐
𝒄𝟏
𝑚 33.2
𝑚 𝑚
𝒄𝟕
32.3
𝒌𝟔
𝒄𝟏
𝒄𝟑
𝒄𝟒
𝑚
35.6
35.6
31.4
𝑚
38.6
44.6
39.6
36.6
40.3
31.4
30.6
31.5
31.4
33.3
30.8
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
37.4
44.4
31.4
42.5
𝑚
43.5
𝑚
33.6
36.6
38.5
28.4 𝒄𝟑
𝑚
𝒄𝟏
𝑚
30.5
𝑚
38.9
35.1
39.5
𝑚
41.6
36.6
34.6
39.6
44.2
42.6
35.6
𝑚
𝒌𝟒
𝒄𝟏
𝒄𝟐
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
𝒌𝟖
𝒄𝟏
𝒄𝟐
𝑚
39.6
38.6
31.6
𝑚
35.2
32.1
43.2
𝑚
37.5
𝑚
34.3
𝑚 34.8
36.1
40.3
42.8 40.1
38.8
44.2
𝒄𝟕
𝒌𝟕
𝒄𝟏
𝒄𝟐
30.5 30.4
35.6 38.6
𝒄𝟐
𝒌𝟑
𝑚
𝒄𝟐
𝒄𝟔
36.6
𝒄𝟓
𝒄𝟔
𝒄𝟕
42.6
𝒄𝟑
𝒄𝟒
𝒄𝟓
𝒄𝟔
36.1
38.9
37.5
30.6
30.6
33.6
42.7
39.9
35.6
44.6
𝒄𝟒
𝒄𝟓
𝒄𝟔
𝒄𝟕
30.5
37.5
36.4
35.2
40.2
31.7
39.9
𝒄𝟕
(b) Fig. 6 (a) The SINR of each IE in different matchings; (b) the SINR of those matchings that can satisfy IE’s SINR requirement.
𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔 because they have been allocated. Then, the resource allocation results can be decided according to the resulted matching set 𝕊 of the TMPG algorithm, which shows the resource sharing among IEs, subchannels, PLVs and PRVs of all platoons. A simple example of executing the TMPG algorithm is presented in Fig. 5~7. Referring to Fig. 5, let there be seven IEs, eight subchannels and three platoons. The TMPG algorithm can compute the SINR of IE 𝑐 using Equation (6) for every matching (𝑐, 𝑘, 𝑚, 0). Fig. 6-(a) is the SINR of each individual entity 𝑐 , 𝑥 = 1. .7, in different matchings, i.e., each IE 𝑐 , 𝑥 = 1. .7, shares subchannel 𝑘 , 𝑦 = 1. .8, with the PLV of platoon 𝑚 , 𝑧 = 1. .3, that are calculated using Equation (6). Fig. 6-(b) is the results after executing function PLIE-CHMatching, i.e., excluding those matchings that can not satisfy IE’s SINR requirement, which is depicted in constraint (h) of
15
Fig. 7 (a) The resulted set T, in which each element contains a candidate matching and the corresponding PLV’s transmitted power; (b) the resulted set T ,̅ which is the sorted result of T; (c) the resulted set S for PLV’s groupcasting.
Fig. 8 The configuration of PL and PR vehicles.
𝒌𝟑 𝒎𝟏 𝒎𝟑 𝒌𝟒 𝒎𝟏 𝒎𝟑 𝒌𝟔 𝒎𝟏
𝒄𝟏 31.6 32.0 𝒄𝟏 37.5 28.8 𝒄𝟏 32.5
𝒄𝟐 36.3 38.4 𝒄𝟐 37.8 20.1 𝒄𝟐 33.1
𝒄𝟒 38.2 33.4 𝒄𝟒 42.5 38.9 𝒄𝟒 35.0
𝒄𝟔 31.5 39.3 𝒄𝟔 35.1 33.8 𝒄𝟔 34.7
𝒎𝟑
29.7
39.8
40.2
36.3
𝒌𝟕 𝒎𝟏 𝒎𝟑 𝒌𝟖 𝒎𝟏 𝒎𝟑
𝒄𝟏 35.5 30.1 𝒄𝟏 34.7 30.2
𝒄𝟐 29.5 29.4 𝒄𝟐 32.5 39.1 (a)
𝒄𝟒 39.2 33.3 𝒄𝟒 29.1 37.2
𝒄𝟔 40.4 30.3 𝒄𝟔 45 31.8
𝒌𝟑 𝒎𝟏 𝒎𝟑 𝒌𝟒 𝒎𝟏 𝒎𝟑 𝒌𝟔 𝒎𝟏 𝒎𝟑 𝒌𝟕 𝒎𝟏 𝒎𝟑 𝒌𝟖 𝒎𝟏 𝒎𝟑
𝒄𝟏 31.6 32.0 𝒄𝟏 37.5
𝒄𝟐 36.3 38.4 𝒄𝟐 37.8
𝒄𝟏 32.5
𝒄𝟐 33.1 39.8 𝒄𝟐
𝒄𝟏 35.5 30.1 𝒄𝟏 34.7 30.2
𝒄𝟐 32.5 39.1
𝒄𝟒 38.2 33.4 𝒄𝟒 42.5 38.9 𝒄𝟒 35.0 40.2 𝒄𝟒 39.2 33.3 𝒄𝟒 37.2
𝒄𝟔 31.5 39.3 𝒄𝟔 35.1 33.8 𝒄𝟔 34.7 36.3 𝒄𝟔 40.4 30.3 𝒄𝟔 45 31.8
(b)
Fig. 9 (a) SINR of each IE in different matchings; (b) SINR of each IE for candidate matchings with the corresponding PR.
Equation (7). That is, Fig. 6-(b) is the SINR of each IE for candidate matchings with the corresponding PLV of platoon 𝑚 , 𝑦 = 1. .3, using subchannel 𝑘 , 𝑧 = 1. .8. Fig. 7-(a) is the resulted set 𝕋, in which each element contains a candidate matching and the correspond PLV’s transmitted power. Fig. 7-(b) is the resulted set 𝕋, which is the sorted result of 𝕋’s elements based on PL’s transmitted power from high to low, i.e., descendently, after executing Line 3 of the TMPG algorithm. Fig 7-(c) is the resulted set 𝕊, whose elements are selected from set 𝕋 and represents the resulted matching after executing function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝑀𝑎𝑡𝑐ℎ𝑖𝑛𝑔, e.g., platoon 𝑚 ’s PLV shares subchannel 𝑘 with IE 𝑐 . After executing Lines 6 to 20 of the TMPG algorithm, ℝ is equal to [5, -1, 4], which means that (i) the PRV of platoon 1 and 3 is PMV 5 and PMV 4 respectively, and (ii) the transmitted power of platoon 2’s PLV can reach its tail PMV, i.e., PMV 5, and thus no PRV is needed for platoon 2, i.e., 𝑅 = -1. Fig. 8 depicts the configuration of PLVs and PRVs of platoons 1, 2 and 3. After that, Lines 22 to 24 of the TMPG algorithm match PRVs, individual entities and subchannels using the same steps as that for matching PLV, individual entities and subchannels. Since (i) individual entities 3, 5 and 7 can share subchannels with PLVs of platoons 1, 2 and 3, respectively and (ii) subchannels 1, 2
16
𝕋
𝕋
{(𝑐 , 𝑘 , 𝑚 , 1), 29.4} {(𝑐 , 𝑘 , 𝑚 , 1), 28.7} {(𝑐 , 𝑘 , 𝑚 , 1), 31.9} {(𝑐 , 𝑘 , 𝑚 , 1), 33.5} ⋮ {(𝑐 , 𝑘 , 𝑚 , 1), 32.4}
{(𝑐 , 𝑘 , 𝑚 , 1), 37.4} {(𝑐 , 𝑘 , 𝑚 , 1), 37.3} {(𝑐 , 𝑘 , 𝑚 , 1), 37.1} {(𝑐 , 𝑘 , 𝑚 , 1), 36.9} ⋮
(a)
𝕊 {(𝑐 , 𝑘 , 𝑚 , 0), 50.2} {(𝑐 , 𝑘 , 𝑚 , 0), 48.7} {(𝑐 , 𝑘 , 𝑚 , 0), 38.5} {(𝑐 , 𝑘 , 𝑚 , 1), 37.4} {(𝑐 , 𝑘 , 𝑚 , 1), 35.1}
(b)
(c)
Fig. 10 (a) The resulted set T, in which each element contains a candidate matching and the corresponding PRVs transmitted power; (b) the resulted set T ̅, which is the sorted result of T; (c) the resulted set S for PLVs and PRVs groupcasting .
: matching with the PLV
: matching with the PRV
Fig. 11 The example’s resulted TMG. and 5 have been used, only individual entities 1, 2, 4 and 6 can potentially share subchannels 3, 4 and 6~8 with PRVs. Fig. 9-(a) is the SINR of each IE 𝑐 , 𝑥 = 1, 2, 4, 6, in different matchings, i.e., each IE 𝑐 , 𝑥 = 1, 2, 4, 6, shares subchannel 𝑘 , 𝑦 = 3, 4, 6, 7, 8, with PRV of platoon 𝑚 , 𝑧 = 1, 3. Fig. 9-(b) is the results after executing function PR-IE-CHMatching, i.e., excluding those matchings that cannot satisfy IE’s SINR requirement, which is depicted in the constraint (h) of Equation (7). That is, Fig. 9-(b) is the SINR of each IE for candidate matchings with the corresponding PRV of platoon 𝑚 , 𝑦 = 1, 3, using subchannel 𝑘 , 𝑧 = 3, 4, 6, 7, 8. Fig. 10-(a) is the resulted set 𝕋, in which each element contains a candidate matching and the corresponding PRV’s transmitted power. Fig. 10-(b) is the resulted set 𝕋, which is the sorted result of 𝕋’s elements based on PRV’s transmitted power from high to low, i.e., descendingly, after executing Line 23 of the TMPG algorithm. Fig 10-(c) is the resulted set 𝕊, whose elements are selected from set 𝕋 and represents the resulted matching after executing Line 24 of the TMPG algorithm, e.g., platoon 𝑚 ’s PRV shares subchannel 𝑘 with IE 𝑐 . Fig. 11 shows the resulted matching set 𝕊 after executing the TMPG algorithm, which is a TMG. For the complexity of Algorithm 1, it mainly consists of triple-nested loops over 𝐶, 𝐾, and 𝑀, which leads to a linear complexity of 𝑂(𝐶 ∗ 𝐾 ∗ 𝑀) for constructing and traversing the candidate set 𝑇. The dominant operations are the sorting steps applied to 𝑇, whose size is 𝐶 ∗ 𝐾 ∗ 𝑀, resulting in a complexity of 𝑂((𝐶 ∗ 𝐾 ∗ 𝑀) ∗ log (𝐶 ∗ 𝐾 ∗ 𝑀)). In addition, the algorithm includes a traversal over all platoons and their vehicles, which incurs an extra cost of 𝑂(𝑀 ∗ 𝑁), where 𝑁denotes the maximum number of vehicles per platoon. Consequently, the overall time complexity of Algorithm 1 is 𝑂((𝐶 ∗ 𝐾 ∗ 𝑀) ∗ 𝑙𝑜𝑔 (𝐶 ∗ 𝐾 ∗ 𝑀) + M*N). 5.2. PMVs’ Subchannel Allocation The second part of Equation (12), i.e., the one for PMV’s unicasting, is solved as follows. (i) PMVs are partitioned into clusters; (ii) one subchannel is assigned to a cluster for all PMs’ unicasting in that cluster, i.e., all PMVs in a cluster share one subchannel. Since the only thing that affects the result is the total co-channel interference from other PMs’ unicasting because PRV 𝑟
does not share its
17
Fig. 12 An example of the tripartite matching for PMVs. allocated subchannel with any PMV, the effect of PRV 𝑟
𝐼 , , can be transformed to the following one based on Equation (2):
𝑚𝑖𝑛 ∑
𝑚𝑖𝑛
(
𝑥 , ∗𝑃 ∗ℎ , , +
𝑥
,
where ∑ ℎ
, ,
can be ignored. As a result, the second part of Equation (12), i.e.,
,
,
∗𝑃
∗ℎ
, ,
+
(15)
𝑧 ∗𝑃 ∗ℎ , , )
,
𝑥 , ∗ 𝑃 ∗ ℎ , , denotes the interference from the same platoon’s vehicles, ∑
denotes the interference from different platoons’ vehicles, and ∑
,
∑
𝑥
,
∗𝑃
∗
𝑧 ∗ 𝑃 ∗ ℎ , , denotes the interference from IEs.
Since the aforementioned problem aims to share subchannels for PMVs’ unicasting, it can be regarded as a partitioning problem in which those PMVs that share the same subchannel are gathered in a cluster. The partitioning problem aims to partition all PMVs to use the subchannels in 𝕂 , where 𝕂′′ represents the set of subchannels that aren’t used by PLVs’ groupcasting and PRVs’ groupcasting. The subchannel allocation for PMVs now becomes to solve the tripartite matching problem, in which an illustrated configuration of the corresponding tripartite matching is depicted in Fig. 12. Refer to Fig. 12, (i) three types of vertices and (ii) the number of each type’s vertices in the tripartite matching configuration/graph are as follows: (i) 𝐶 IEs, (ii) 𝐾 Subchannels, and (iii) 𝑈 clusters of PMVs. Let |ℂ | denote the number of IEs that share subchannels with PLVs/PRVs, and |ℂ | denote the number of IEs that haven’t been allocated subchannels: |ℂ | = |ℂ| − |ℂ |. Since there is no resource sharing between two different IEs, the number of subchannels needs to satisfy the following constraint: |𝕂 | ≥ |ℂ |. The QoS requirement for IE 𝑐 should be satisfied when entity 𝑐 shares its allocated subchannel 𝑘 with other vehicles. Thus, the following Equation should be satisfied: 𝑆𝐼𝑁𝑅 , =
∗ σ
,
≥ 𝛿
⇒𝐼, ≤
∗
−σ .
The tripartite matching among remaining IEs, subchannels and clusters of PMVs is depicted in the Resource Sharing for Platoons’ Unicasting (𝑅𝑆𝑃𝑈) algorithm, which is called as 𝑅𝑆𝑃𝑈 hereafter. Lines 6 to 17 of the 𝑅𝑆𝑃𝑈 algorithm iteratively produce the tripartite matching results among IEs, subchannels and PMVs’ clusters until subchannels can afford all clusters’ requirements or the number of subchannels used by all clusters is minimized. Line 7 calls function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 to partition |ℕ| PMVs to 𝑈 clusters. Lines 9 to 11 add virtual IEs to set ℂ to make the number of IEs equal the number of clusters. Note that a cluster that shares a subchannel with a virtual IE solely uses the allocated subchannel. Line 12 calls function 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶𝑙𝑎𝑠𝑡𝑒𝑟𝑖𝑛𝑔 to add all available candidate matchings to set 𝕋, for which both (a) IE’s SINR constraint, i.e., constraint (i) in Equation (7) and (b) each PMV’s SINR constraint, i.e., constraint. The corresponding execution is in Lines 5 to 14 of function 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶𝑙𝑎𝑠𝑡𝑒𝑟𝑖𝑛𝑔. Function 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶𝑙𝑎𝑠𝑡𝑒𝑟𝑖𝑛𝑔 derives the corresponding total co-channel interference when (a) the IE’s SINR constraint and (b) each PMV’s SINR constraint in the cluster are
18 Algorithm 2 Resource Sharing for Platoons’ Unicasting (𝑅𝑆𝑃𝑈) ● Input: ℂ individual entities, 𝕂 unassigned subchannels and ℕ PMVs. ● Output: resource allocation matching pair set 𝕊. 1. 𝕊←{} // 𝕊 is used to keep the resulted matching. 2. 𝕊 ←{} // 𝕊 is used to keep the resulted matching of the previous iteration. 3. 𝑓 ← 0 // 𝑓 denotes the trend of the number of clusters: 𝑓 = 0 means the first iteration that decides the trend is either increasing or decreasing; 𝑓 = 1 means that the number is increasing; 𝑓 = −1 means that the number is decreasing. 4. 𝑈 ← |𝕂 | //𝑈 is the number of clusters at the beginning. 5. ℚ ← {𝑄 , 𝑄 … … , 𝑄 } = {∅, ∅, … … , ∅} // ℚ is used to store the partitioned result of each cluster; 𝑄 stores the PMVs that belong to the i-th cluster after partition. 6. while (𝑓 = 0) or (𝑓 = 1 and ℚ ≠ ∅) or (𝑓 = −1 and ℚ = ∅) do 7. ℚ ← 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑜𝑛𝑖𝑛𝑔(𝑈, ℕ) //Use function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑜𝑛𝑖𝑛𝑔 to partition |ℕ| PMVs to 𝑈 clusters. 8. 𝕋←{} // 𝕋 temporarily stores available matching {(𝑐, 𝑘, 𝑢), 𝑥} , where (1) (𝑐, 𝑘, 𝑢) denotes the matching of having IE 𝑐 and cluster 𝑢 to share subchannel 𝑘 and (2) 𝑥 denotes the sum of the co-channel interference of vehicles in a cluster. 9. while |ℂ | < |𝑈| do 10. Add a new virtual IE to set ℂ 11. end while 12. 𝕋 ← 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔(ℂ , 𝕂 , ℚ) 13. 𝕋 ← 𝑆𝑜𝑟𝑡(𝕋, 𝑥) //Sort elements in 𝕋 ascendingly based on 𝑥. 14. 𝕊 ←𝕊 15. 𝕊 ← 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔(𝕋) 16. 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡() 17. end while 18. return 𝕊 Function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑜𝑛𝑖𝑛𝑔(𝑈, ℕ) ● Input: 𝑈 designates the number of target clusters, ℕ designates the set of PMVs; each PMV is denoted as 𝑣 , where m denotes platoon’s index and n denotes the vehicle’s index in platoon 𝑚. ● Output: Partitioned result ℚ 19. ℚ ← {𝑄 , 𝑄 … … , 𝑄 } = {∅, ∅, … … , ∅} // ℚ is used to store the partitioned result of each cluster; 𝑄 stores the PMVs that belong to the i-th cluster after partition. 20. repeat 21. Randomly select a PMV 𝑣 from ℕ. 22. 𝐼 ←∞ //𝐼 is used to record the increased intra-cluster interference. 23. 𝑢 ←0 //𝑢 records the index of the cluster to which vehicle 𝑣 can have the minimum 𝐼 when vehicle 𝑣 belongs. 24. for 𝑖 = 1: 𝑈 do 25. if 𝑣 ∉ 𝑄 or 𝑣 ∉ 𝑄 then 26. Compute the increased interference ⬚
𝑥←
(𝑃
∗ℎ
,
+𝑃 ∗ℎ ,
Function 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔 (ℂ , 𝕂 , ℚ) 1. 𝕋←{} 2. foreach 𝑘 in 𝕂 do 3. foreach 𝑐 in ℂ do 4. for 𝑢 = 1: 𝑈 do 𝑆𝐼𝑁𝑅 , , =
6.
𝑗 ← 𝑡𝑟𝑢𝑒 //𝑗 is used to check whether each PMV’s SINR in the cluster satisfies the SINR constraint or not. 𝑖 ← |𝑄 | − 1 //𝑖 is used to store the index of PMV in cluster 𝑄 . while 𝑗 = 𝑡𝑟𝑢𝑒 and 𝑖 ≥ 0 do
7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.
27. if 𝑥 < 𝐼 then 28. 𝐼 ←𝑥 29. 𝑢 ←𝑖 30. end if 31. end if 32. end for 33. 𝑄 ←𝑄 +𝑣 34. ℕ←ℕ \𝑣 35. until ℕ = ∅;//It means that there is no PMV left to be partitioned. 36. return ℚ
𝑆𝐼𝑁𝑅𝑄𝑢[𝑖𝑄 ]
,
,𝑄𝑢 [𝑖𝑄 ],
=
∗ 𝑄 [𝑖𝑄 ]
𝑄𝑢 [𝑖𝑄]
𝑢
σ
,𝑄𝑢 [𝑖𝑄 ]
𝑄𝑢 [𝑖𝑄],
if Equation 7-(i) is not satisfied then 𝑗 ← 𝑓𝑎𝑙𝑠𝑒 end if 𝑖 ← 𝑖 −1 end while if Equation 7-(h) is satisfied and 𝑗 = 𝑡𝑟𝑢𝑒 then Calculate 𝑥 = ∑⬚∈ 𝐼 , 𝕋 ← 𝕋 + {(𝑐, 𝑘, 𝑢), 𝑥} end if end for end foreach end foreach return 𝕋
Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡(𝑓) 23. switch 𝒇 24. case 0: //Executing the first iteration. 25. if ℚ ≠ ∅ then 26. 𝑓←1 27. Add a new subchannel to 𝕂 28. 𝑈 ← 𝑈+1 29. else 30. 𝑓 ← −1 31. 𝑈 ← 𝑈−1 32. end if 33. case 1: //The number of clusters is increasing. 34. if ℚ ≠ ∅ then 35. Add a new subchannel to 𝕂 36. 𝑈 ← 𝑈+1 37. end if 38. case −𝟏: //The number of clusters is decreasing. 39. if ℚ = ∅ then 40. 𝑈 ← 𝑈−1 41. else 42. 𝕊←𝕊 43. end if 44. end switch Function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔 (𝕋) 1. 2.
)
∈
∗ ,
5.
3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
𝕊={} 𝑖𝕋 = 0 //𝑖𝕋 is used to store the index of 𝕋’s elements. while (𝑖𝕋 < |𝕋|) or (𝑄 ≠ ∅) do if 𝑐 ∈ ℂ 𝑎𝑛𝑑 𝑘 ∈ 𝕂 𝑎𝑛𝑑 𝑄 ∈ ℚ in 𝕋[𝑖𝕋 ] then 𝕊 ← 𝕊 + 𝕋[𝑖𝕋 ] //Allocate subchannel 𝑘 to entity 𝑐 and all PMVs in cluster 𝑄 . ℂ ←ℂ \𝑐 𝕂 ←𝕂 \𝑘 ℚ← ℚ\𝑄 end if 𝑖𝕋 ← 𝑖𝕋 + 1 end while return 𝕊
satisfied. Lines 16 to 17 of function 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝐶𝑙𝑎𝑠𝑡𝑒𝑟𝑖𝑛𝑔 store the candidate matching, for which each element in set 𝕋 contains (i) the tripartite matching and (ii) the increased intra-cluster interference. Line 13 of the 𝑅𝑆𝑃𝑈 algorithm sorts the elements in set 𝕋 based on the total co-channel interference for PMVs in each cluster, i.e., the value of 𝑥, from low to high. Line 14 of the 𝑅𝑆𝑃𝑈 algorithm saves the previous result set 𝕊. Line 15 calls function 𝑅𝑒𝑠𝑢𝑙𝑡𝑒𝑑𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔 to iteratively pick up the candidate matching that has the
19
Fig. 13 (a) An exemplary input of the RSPU algorithm; (b) A example after calling function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 to partition all PMVs.
Fig. 14 (a) The resulted set 𝕋 contains candidate matchings and the corresponding total co-channel interference of all PMVs in the same cluster; (b) the resulted set 𝕋, which is the sorting result of 𝕋; (c) the resulted set 𝕊.
𝑖𝕋 -th lowest total co-channel interference: If entity 𝑐, cluster 𝑄 and subchannel 𝑘 have not been matched, then add the matching to set 𝕊; then remove 𝑐, 𝑘 and 𝑄 from ℂ, 𝕂 and ℚ respectively because they have been allocated. Line 16 of the 𝑅𝑆𝑃𝑈 algorithm calls Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 to consider the result of each iteration and perform actions based on the conditions. Three Cases in Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 based on 𝑓are as follows: (1) 𝑓 = 0 means that the execution is in the first iteration. It decides the number of subchannels needs to be increased or be decreased, i.e., the current number of subchannels cannot afford all PMVs’ requirements of all platoons or the number of clusters is too many. (2) 𝑓 = 1 means that the number of subchannels needs to be increased until it can afford all PMVs’ requirements of all platoons and the number of clusters needs to be increased until its intra-cluster interference is small enough. (3) 𝑓 = -1 means that the number of subchannels can afford all PMVs’ requirements of all platoons and the number of clusters can be decreased to minimize the used resources. In Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡, when 𝑓 = 0, Lines 3 to 6 of the Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 (i) set 𝑓 = 1 , (ii) increase the number of subchannels and, (iii) increase the number of clusters when the initially allocated subchannels cannot afford the required subchannels for all clusters. It implies that there are too many PMVs and thus only a subset of clusters has been allocated subchannels, even if each IE shares its subchannel with a cluster of PMVs. That is, it needs to allocate more subchannels that are dedicated to be used by clusters. When 𝑓 = 0, Lines 7 to 9 of the Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 set 𝑓 = −1 and decrease the number of clusters when the initially allocated subchannels can afford all clusters’ requirement, i.e., it denotes that it may create too many clusters and thus it can try to decrease the number of created clusters. That is, it implies that it does not need to create so many clusters for platoons’ PMVs and thus only some of the IEs need to share their subchannels with these clusters of PMVs, i.e., some IEs solely use the allocated subchannels respectively. When 𝑓 = 1, Lines 12 to 15 of the Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 increase the number of subchannels and the number of clusters because the allocated subchannels still cannot afford all clusters’ required subchannels. When 𝑓 = -1, Lines 17 to 18 of the Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 decrease the number of clusters because it still creates too many clusters. When 𝑓 = -1, Lines 19 to 20 of the Procedure 𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑖𝑛𝑔𝐴𝑑𝑗𝑢𝑠𝑡𝑚𝑒𝑛𝑡 derive the resulted 𝕊 to be equal to 𝕊
when clusters in the current iteration cannot afford all
PMVs. It means that the number of clusters of the previous iteration reaches the minimum and cannot be decreased further. An example of the first iteration of executing the 𝑅𝑆𝑃𝑈 algorithm is depicted in Fig. 13~15. Let there be four IEs, four subchannels
20
Fig. 15 The example’s resulted TMG.
Fig. 16 (a) An example of executing function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔; (b) the partition result of the first four selected PMVs; (c) the increased intra-cluster interference if PMV 𝑣 is added into 𝑄 , 𝑄 , 𝑄 and 𝑄 respectively; (d) the partition result of PMV 𝑣 ; (e) the final partition result after all PMVs have been partitioned.
and seven PMVs, which are shown in Fig. 13-(a). Fig 13-(b) is transformed from Fig. 13-(a) after calling the function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 to partition all PMVs. Fig. 14-(a) is the resulted set 𝕋, in which each element contains a candidate matching and the corresponding total co-channel interference of all PMVs in the same cluster. Fig. 14-(b) is the resulted set 𝕋, which is the sorting result of 𝕋’s elements based on the total co-channel interference of all PMVs in the same cluster. Fig. 14-(c) is the resulted set 𝕊, e.g., the PMVs in cluster 𝑄 share subchannel 𝑘 with IE 𝑐 . Fig. 15 depicts the resulted matching set 𝕊 of executing the 𝑅𝑆𝑃𝑈 algorithm as a TMG. Function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔, which is called in Line 7 of the 𝑅𝑆𝑃𝑈 algorithm, aims to partition all PMVs into |𝕂 | clusters to minimize the intra-cluster interference. Lines 2 to 17 of function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 partition PMVs to the suitable clusters until all PMVs have been partitioned. Lines 6 to 14 of function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 find the cluster, for which the increased intra-cluster interference results from the picked PMV 𝑣
is the minimum, to put PMV 𝑣 . If the adjacent vehicles of PMV 𝑣
cluster, Lines 8 to 12 calculate the increased interference when PMV 𝑣
are not in the 𝑖-th
is put in the 𝑖-th cluster and check whether the resulted
interference becomes smaller or not. A positive result indicates that it has identified a more suitable cluster; otherwise, it needs to try the next cluster. Lines 15 of function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 puts vehicle 𝑣 interference resulted from the addition of 𝑣
to cluster 𝑄
, in which cluster 𝑄
’s increased
is the minimum. Line 16 of function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 removes vehicle 𝑣
from ℕ
because it has been partitioned. An example of executing function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 is depicted in Fig. 16. Let the target of function 𝑃𝑀𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑖𝑛𝑔 be to partition five PMVs to four clusters that are depicted in Fig. 16-(a). Fig. 16-(b) is the partition result of the first four selected PMVs. Fig 16-(c) depicts the increased intra-cluster interference, which is derived using Equation (5), of 𝑄 , 𝑄 , 𝑄 and 𝑄 if PMV 𝑣 is added into 𝑄 , 𝑄 , 𝑄 and 𝑄 respectively, for which 𝑣 can not be added into 𝑄 because the current 𝑄 ’s PMV 𝑣 is the adjacent vehicle of
21
TABLE 2: PARAMETERS AND THEIR ASSOCIATED VALUES ADOPTED IN THE SIMULATION ENVIRONMENT. Parameters
Values
Radius of the BS BS’s antenna height BS’s antenna gain The distance from the BS to road Vehicle’s antenna height Number of road lanes Lane width of the road SINR threshold for the receiver (𝛾 ) QoS requirement of individual entities Number of platoons (𝑀) The maximum platoon size Number of individual entities Vehicle’s maximum transmitted power for groupcasting Vehicle’s maximum transmitted power for unicasting Individual entities’ maximum transmitted power Bandwidth Carrier frequency Fading factor (𝛼) Noise power density (𝜎 ) Size of each data packet (𝜆) Pathloss for individual cellular network users
1km 25m 8 dBi 100 m 1.5 m 2 4m 5 dB 0.5 bps/Hz 5 11 65 17 dBm 30 dBm 10 MHz 2 GHz 3 -114 dBm 300 Bytes 128.1 + 37.6 log (𝑑) [27]
Pathloss for platoon vehicles’ communications
𝐿𝑂𝑆 𝑊𝐼𝑁𝑁𝐸𝑅 + 𝐵1 [27]
30 dBm
Fig. 17 An illustrated configuration of the simulation, where IEs on the road are non-platooning vehicles, which are denoted as white circles, and IEs outside the road are smartphone users, which are denoted as white squares.
𝑣 . Thus, 𝑣 should be added into cluster 𝑄 , which is shown in Fig. 16-(d). Fig. 16-(e) shows the final partitioning result after all PMVs are partitioned into these four clusters. Algorithm 2 performs iterative clustering and adjustment over N PMVs and K ′′ channels. The candidate clustering and sorting processes dominate the computational cost, yielding O(C ′′ ∗ K ′′ ∗ N) and O((C ′′ ∗ K ′′ ∗ N) ∗ log (C′′ ∗ K ′′ ∗ N)), respectively. In the worst-case scenario, the outer while-loop increases the number of channels up to K ′′ = N, such that each cluster contains only one PMV. Therefore, the total time complexity of Algorithm 2 in the worst case is bounded by O(C′′ ∗ N ). 6. Performance Evaluation The performance evaluation of the proposed method is presented in this Section. 6.1 The Simulation Environment To estimate the proposed method’s performance, an urban environment has been modeled, which is depicted in Fig. 17. The urban environment simulates an urban street block covered by a single cell, in which the BS is located in the block’s center. Four roads surround the BS in a perpendicular manner. The simulation parameters and their values are depicted in Table 2. Since there is no paper that has the similar functional scenario as this work, i.e., (i) consider resource allocation for both groupcasting and unicasting and (ii) both groupcasting and unicasting are able to share subchannels with IEs, the benchmark schemes are selected to represent relevant state-of-the-art approaches from two key aspects. For Relay selection, the proposed TMPG algorithm is compared with: (a) a centralized method in [19], which minimizes transmission power at both PLV and PRV, representing an efficient optimization-based baseline. (b) The No Relay method, in which PLV’s groupcasting has the responsibility to transmit PLV’s messages to platoon’s tail vehicle using the corresponding transmitted power. Additionally, the allocated subchannel for PLV’s groupcasting can be shared with one IE, under the condition of the SINR of PLV’s groupcasting being not lower than the SINR’s minimum threshold. Then, methods for relay selection and PMV partitioning are combined together to have the overall performance comparison. The compared PMV partitioning methods with the proposed RSPU algorithm are as follows: (1) The Hypergraph-based Resource Allocation and Interference Management (HRAIM) scheme, which adopts the same principle of subchannel’s sharing among PMVs and IEs as our
22 proposed RSPU algorithm, proposed in [10]. After the HRAIM method partitioning PMVs to clusters based on PMVs’ SINR constraints, a cluster is selected one by one, which is from the one that has the highest intra-cluster interference to the one that has the lowest intracluster interference sequentially, to share with an IE’s allocated subchannel, for which the IE that results in the lowest interference for the cluster’s contained vehicles is picked to share its allocated subchannel with the corresponding cluster. After the cluster’s sharing subchannel with the IE is decided, if there are 𝑛 PMVs in the cluster having the lower SINR than the minimum SINR threshold, which results from sharing the subchannel with the IE, then selecting 𝑘 vehicles from the 𝑛 vehicles to split the other cluster to share with the other IE’s allocated subchannel, for which (i) each one of the remaining vehicles in the original cluster and (ii) each vehicle in the split cluster has the SINR that is higher than the minimum SINR threshold respectively. (2) The random subchannel assignment (RAA) method, which allows an IE’s allocated subchannel to be shared with one or more PMVs, randomly assigns a subchannel to a PMV 𝑥, for which the assigned subchannel may already be allocated to an IE and one or more PMVs, as long as the constraints of the SINR requirements of PMV 𝑥 and those PMVs that originally share the assigned subchannel are satisfied over the assigned subchannel. The adopted performance metrics for comparison are defined as follows: (I) Platoon's transmission latency (ms): This metric represents the average end-to-end transmission time for various scenarios. For groupcasting, it includes two pieces of transmissions: (1) PLV groupcasts messages to (a) the PRV and (b) the PMVs that are between PLV and PRVs and (2) PRV groupcasts messages to the PMVs
that
are
∑
∑
∑
𝑙𝑎𝑡𝑒𝑛𝑐𝑦 ,
between
𝑙𝑎𝑡𝑒𝑛𝑐𝑦 ,
2, and (3) ∑
PRV
and
the
last
PMV.
𝑉 − 2 , where (1) 𝑙𝑎𝑡𝑒𝑛𝑐𝑦 ,
For
unicasting,
the
transmission
latency
is
calculated
as
denotes the transmission latency from PMV 𝑖 to PMV 𝑖 + 1 , (2)
means the sum latency of transmitting a unicasted messages from PMV 𝑗, 𝑗 = 1. . 𝑉 − 2, to 𝑗 + 1, 𝑗 + 2, and 𝑉 − means the sum of these (𝑉 − 2) different unicasting latency. For the overall platoon’s transmission latency, the
transmission latency is calculated by dividing the sum of groupcasting’s transmission latency and unicasting’s transmission latency by 2. (II) QoS’s satisfaction rate of IEs: The QoS’s satisfaction rate of IEs denotes the number of IEs whose SINRs are higher than the minimum threshold divided by the number of IEs who have shared subchannels with PVs. (III) Number of allocated subchannels: It is the number of subchannels allocated for platoons, which are divided into (a) the subchannels allocated for PLVs/PRVs groupcasting and (b) the subchannels allocated for both PLVs/PRVs groupcasting and PMVs’ unicasting. (IV) Spectral efficiency (bps/Hz): It is the bit rate that can be used over a transmission Hz. It is calculated by dividing the transmission bit rate by the allocated subchannels’ amount of transmission bandwidth, which is in the unit of Hz. Two types of evaluated spectral efficiency are (a) the spectral efficiency of PLV’s and PRV’s groupcasting and (b) the spectral efficiency of considering both platoon’s groupcasting and unicasting together. 6.2 The Simulation Results Groupcasting: Let the number of IEs be 65 and the number of platoons be 5 (M = 5); the number of IEs be bigger than the total number of PVs of these 5 platoons because the simulation is assumed to be in the urban scenario; the quantity of subchannels that can be allocated be 65 subchannels (K = 65).
23
(a)
(b)
Fig. 18 (a) The transmission latency of platoon groupcasting; (b) the QoS’s satisfaction rate of individual entities.
(a)
(b)
Fig. 19 (a) The number of allocated subchannels for platoon’s groupcasting; (b) the spectral efficiency of platoon’s groupcasting.
Fig. 18-(a) depicts the transmission latency of PLV’s and PRV’s groupcasting. When the number of PVs is equal to or smaller than 30, in which condition all platoons in the proposed TMPG and the No Relay methods don’t need PRV, (i) the TMPG method remains low transmission latency and (ii) the No Relay method’s latency decreases when the number of platoons’ vehicles is increased. The result is explained as follows. Using the proposed TMPG, PLV uses the transmitted power that can satisfy both the SINR requirements of PLV and the corresponding IE, which shares its allocated subchannel with PLV, and thus it can keep the stable transmission latency. Using the No Relay method, PLV increases its transmitted power to transmit messages to platoon’s tail vehicle when the number of platoon’s vehicles is increased, which leads to the higher SINR. The higher SINR then can increase the transmission rate, which, in turn, results in the lower transmission delay. When the number of PVs is more than 30, the platoon using the proposed TMPG needs to pick a PRV to forward PLV’s messages. As a result, each message needs to be received completely in the PRV at first; then the received message is re-groupcasted by the PRV. Therefore, the proposed TMPG’s transmission latency becomes more than two times higher than the transmission latency on the condition of the number of PVs being equal to or smaller than 30. The Centralized Method always has the higher transmission latency than the other two methods when the number of PVs is smaller than 55 because it needs to pick a PRV no matter how long the platoon is and thus it needs to experience both PLV’s transmission latency and PRV’s transmission latency. Additionally, the Centralized method starts from high latency and then the latency becomes smaller when the number of PVs is increasing. This result is owing to the transmitted power of both PLV’s and PRV’s groupcasting being increased when the total number of vehicles in platoons is increased. The increased power results in the bigger SNR, which, in turn, leads to the better transmission rate
24 and smaller transmission latency. Although the proposed method has the disadvantage of interference from individual entities, Figure 18-(b) shows that the proposed method always can satisfy individual entities’ QoS/SINR’s requirements while the no relay method make some individual entities’ SINRs be lower than the required SINR and thus the QoS’s requirements be not satisfied when the number of platoon vehicles is bigger than 30. Fig. 19-(a) depicts the number of allocated subchannels for PLV’s and PRV’s groupcasting. Referring to Fig. 19-(a) the proposed TMPG does not need to pick a PRV when the number of PVs is equal to or smaller than 30. When the number of PVs is bigger than 30, the proposed TMPG method needs to allocate one more subchannel for PRV’s groupcasting. Thus, the number of allocated subchannels in the condition of the number of PVs being bigger than 30 is twice of the number of allocated subchannels in the condition of the number of PVs being equal to or smaller than 30. The number of subchannels used in the No Relay method is the same as the number of platoons because it uses one subchannel for PLV’s groupcasting for each platoon. On the other hand, since the Centralized method always needs one subchannel for PLV’s groupcasting and one subchannel for PRV’s groupcasting, the number of allocated subchannels of using the Centralized method for one platoon is 2, which is twice of that of using the No Relay method. Fig. 19-(b) depicts the spectral efficiency of those subchannels allocated to PLVs/PRVs. The proposed TMPG method maintains a similar spectral efficiency in conditions of the number of PVs increasing from 15 to 55. The result is owing to the proposed TMPG method achieving stable spectral efficiency, which is explained as follows. Although the proposed TMPG method uses more subchannels when the number of PVs exceeds 30, the proposed TMPG considers all IEs that can share subchannels with PLVs and PRVs to find the suitable transmitted power, which makes PLV and PRV adjust the transmitted power to have the similar SINR, which, in turn, results in the similar transmission rate even if the number of PVs is increased. Thus, the spectral efficiency remains similar. The No Relay method’s spectral efficiency increases when number of PVs increases because the transmitted power of PLVs increases, which, in turn, increases the SINR and thus the transmission rate is increased. Consequently, the spectral efficiency increases. The spectral efficiency of the Centralized method shows a slight increasing when the number of PVs increases because the transmitted power of PLVs and PRVs increases, which, in turn, increases the SINR and thus leads to a higher transmission rate. As a result, the spectral efficiency increases. Overall Performance Comparison Results: For the overall performance evaluation, five methods are compared: (1) the proposed method, i.e., the proposed TMPG algorithm + the proposed RSPU algorithm, which is denoted as “The Proposed method”, (2) the Centralized method + the RAA method, which is denoted as “Cen-RAA”, (3) the Centralized method + the HRAIM method, which is denoted as “Cen-HRAIM”, (4) the No Relay method + the RAA method, which is denoted as “No Relay-RAA” and (5) the No Relay method + the HRAIM method, which is denoted as “No Relay-HRAIM”. Fig. 20-(a) depicts the latency of platoons considering both groupcasting and unicasting. Referring to Fig. 20-(a), the proposed method can have a lower transmission latency than the other jointed methods when the number of PVs is equal to or smaller than 25. The result is owing to the proposed method’s PLV using the highest transmitted power (1) that can satisfy the SINR requirements of PLV groupcasting and (2) whose resulted interference to the IE 𝑐 sharing its allocated subchannel with the PLV is low enough to satisfy the SINR requirement of 𝑐. When the number of PVs equals 30, the proposed method’s latency is slightly higher than the two jointed
25
(a)
(b)
Fig. 20 (a) The overall transmission latency. (b) The overall QoS’s satisfaction rate of individual entities.
methods that adopt the No Relay groupcasting method. The result is owing to the proposed method having the higher PMVs’ unicasting transmission latency than these two jointed methods that adopt the No Relay groupcasting method. When the number of PVs exceeds 35, the transmission latency of the proposed method is gradually becoming higher and is higher than the two methods that adopt the Centralized groupcasting method when the number of PVs is equal to or greater than 45. The reason is as follows. (1) For groupcasting, each message needs to be received completely in the PRV at first; then the received message is re-groupcasted by the PRV. Therefore, the proposed TMPG’s transmission latency of the number of PVs being more than 30 becomes more than two times higher than the transmission latency on the conditions of the number of PVs being smaller than 30. (2) The proposed method has the higher unicasting transmission latency of PMVs than the two jointed methods that adopt the Centralized groupcasting method. Although the proposed method has the disadvantage of interference from IEs, Fig. 20-(b) shows that the proposed method always can satisfy IEs’ QoS/SINR’s requirements while the other joint methods make some IEs’ SINRs be lower than the required SINR and thus the QoS’s requirements be not satisfied when the number of PVs is bigger than 30. Fig. 21-(a) depicts the number of allocated subchannels for PVs. Referring to Fig. 21-(a), the proposed method has the smaller number of allocated subchannels than the other methods when the number of PVs is smaller than 35. The result is owing to the proposed method (1) using the smaller number of subchannels for groupcasting because the proposed method doesn’t always need to use one more subchannel that is for PRV groupcasting, which depends on the existence of the PRV, in each platoon and (2) using the smaller number of subchannels for unicasting because the proposed method decreases the number of subchannels used by platoons’ PMVs to the minimum as long as PMVs’ QoS requirements can be satisfied, which leads to the smallest number of allocated subchannels. In the condition of the number of PVs being bigger than 35, the proposed method has the smaller number of allocated subchannels than the Centralized-RAA method, the No Relay-RAA method and the Centralized-HRAIM method because PMVs’ unicasting of the proposed method uses fewer subchannels. The proposed method has the bigger number of allocated subchannels than the No Relay-HRAIM method because the proposed method uses one subchannel for PRV’s groupcasting in each platoon, i.e., twice of the number of allocated subchannels in the situations of PVs’ number being bigger than 30. Fig. 21-(b) depicts the spectral efficiency of these five methods. Referring to Fig. 21-(b), the proposed method achieves the highest spectral efficiency when the number of PVs is equal to or smaller than 30 because the proposed method has both the highest groupcasting spectral efficiency and highest unicasting spectral efficiency.
26
(a)
(b)
Fig. 21 (a) The number of allocated subchannels for platoons. (b) The overall spectral efficiency of platoons.
In the condition of the number of PVs exceeding 30, the spectral efficiency of the proposed method is gradually smaller than the two jointed methods that adopt the No Relay groupcasting because PLVs’ and PRVs’ transmitted power of the proposed method reach the maximum transmitted power. In the condition of the number of PVs exceeding 50, the spectral efficiency of the proposed method is smaller than that of the Centralized-HRAIM method because the proposed method’s spectral efficiency of groupcasting, which shares subchannels with IEs, has the higher interference, which leads to the lower SINR and higher transmission rate and thus the lower spectral efficiency than the Centralized-HRAIM method. 7. Conclusion This work has proposed the sharing-oriented resource allocation method for multi-platoon communications based on transmission reliability of groupcasting communication and unicasting communication inside platoons. For PLV’s/PRV’s groupcasting communication, a tripartite matching problem that matches (i) an allocated subchannel, (ii) a PLV or a PRV and (iii) an IE is formulated and solved using the proposed TMPG algorithm. The TMPG algorithm maximizes PLV’s/PRV’s transmitted power that can make the SINR of the IE, which shares the subchannel with the PLV/PRV, be higher than the minimum threshold. The TMPG method’s tripartite matching result denotes the resource allocation for PLVs\PRVs. For PMVs’ unicasting communication, the proposed RSPU method firstly partition PMVs into clusters, i.e., those PMVs in a cluster share one subchannel. After that, a tripartite matching problem that matches (i) an allocated subchannel, (ii) a cluster of PMVs and (iii) an IE is formulated and solved using the proposed RSPU algorithm. The RSPU algorithm’s tripartite matching result denotes the resource allocation for PMVs. The performance evaluation results have shown that the proposed method has the better performance on (1) QoS’s satisfaction rate, (2) the number of allocated subchannels for PVs and (3) the spectral efficiency than the compared methods in the urban scenario. Despite its effectiveness, the proposed work has some limitations, particularly its focus on a single-cell scenario without considering the multi-cell scenario. The future work can be twofold: (i) It can extend the proposed method to the scenario of using multiple PRVs, i.e., it can extend the number of PVs in a platoon, (ii) it can extend the resource allocation of multi-platoon communications from the single-cell range to the multi-cell range, where intracell and inter-cell interferences need to be considered, (iii) explore low-complexity or learning-based approaches to enhance scalability and robustness.
27
ACKNOWLEDGMENTS This work was supported by (1) the Ministry Of Science and Technology (MOST), Taiwan (R.O.C.) under the grant number 111-2221E-006-117-MY3 and (2) Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 102.04-2023.40.
REFERENCES Liu, G., Hu, J., Ma, Z., Fan, P., & Yu, F. R. Joint Optimization of Communication Latency and Platoon Control Based on Uplink RSMA for Future V2X Networks. IEEE Transactions on Vehicular Technology 2025; doi: 10.1109/TVT.2025.3560709. [2] Braiteh, F. E., Bassi, F., & Khatoun, R. Platooning in Connected Vehicles: A Review of Current Solutions, Standardization Activities, Cybersecurity, and Research Opportunities. IEEE Transactions on Intelligent Vehicles 2024; 1-23, http://dx.doi.org/ 10.1109/TIV.2024.3447916. [3] Liu, H., Chu, D., Zhong, W., Gao, B., Lu, Y., Han, S., & Lei, W. Compensation control of commercial vehicle platoon considering communication delay and response lag. Computers and Electrical Engineering 2024;, 119, 109623, [4] Yang, Y., Yu, H., Zhao, Y., Chen, M., Du, J., & Ren, Y. A Dynamic Pricing-based Offloading and Resource Allocation Scheme With Data Security for Vehicle Platoon. IEEE Internet of Things Journal 2024; 12(6), 7149-7163, doi: 10.1109/JIOT.2024.3492694. [5] Wang, P., Di, B., Zhang, H., Bian, K., & Song, L. Platoon cooperation in cellular V2X networks for 5G and beyond. IEEE Transactions on Wireless Communications 2019; 18(8), 3919-3932. http://dx.doi.org/ 10.1109/TWC.2019.2919602. [6] Huang, C. M., Lam, D. N., & Dao, D. T. A Hypergraph Matching-Based Subchannel Allocation for Multi-Platoon’s Communications. IEEE Access 2023; 11, 139345-139365., http://dx.doi.org/ 10.1109/ACCESS.2023.3335838. [7] Z. Dong, X. Zhu, Y. Jiang, and H. Zeng, Manager Selection and Resource Allocation for 5G-V2X Platoon Systems with Finite Blocklength, In 2021 IEEE Wireless Communication Network Conference (WCNC), Nanjing, China, 1–6, http://dx.doi.org/10.1109/WCNC49053.2021.9417291. [8] Wang, R., Wu, J., & Yan, J. Resource allocation for D2D-enabled communications in vehicle platooning. IEEE Access 2018; 6, 5052650537.. http://dx.doi.org/ 10.1109/ACCESS.2018.2868839. [9] Zhao, P., Kuang, Z., Guo, Y., & Hou, F. Task offloading and resource allocation in UAV-assisted vehicle platoon system. IEEE Transactions on Vehicular Technology 2025; 74(1), 1584-1596, doi: 10.1109/TVT.2024.3458973. [10] Cui, H., Xu, L., Wei, Q., & Wang, L. Hypergraph based resource allocation and interference management for multi-platoon in vehicular networks. In 2020 IEEE/CIC International Conference on Communications in China (ICCC) 2020; 853-857. IEEE. [11] Cao, L., Roy, S., & Yin, H. Resource allocation in 5G platoon communication: Modeling, analysis and optimization. IEEE Transactions on Vehicular Technology 2022; 72(4), 5035-5048. [12] Han, Q., Liu, C., Yang, H., & Zuo, Z. Longitudinal control-oriented spectrum sharing based on C-V2X for vehicle platoons. IEEE Systems Journal 2022; 17(1), 1125-1136. http://dx.doi.org/10.1109/JSYST.2022.3201816. [13] 3GPP, Study on NR Vehicle-to-Everything (V2X), 2019, TR 38.885 V16.0.0. [14] Silva, E. A., Mozelli, L. A., Neto, A. A., & Souza, F. O. Disturbance and uncertainty compensation control for heterogeneous platoons under network delays. Computers and Electrical Engineering 2025; 123, 110066, 1-16. https://doi.org/10.1016/j.compeleceng.2024.109623. [15] Wang, L., Liang, H., Mao, G., Zhao, D., Liu, Q., Yao, Y., & Zhang, H. Resource allocation for dynamic platoon digital twin networks: A multiagent deep reinforcement learning method. IEEE Transactions on Vehicular Technology 2024; http://dx.doi.org/ 10.1109/TVT.2024.3414447. [16] Fu, X., Yuan, Q., Luo, G., Cheng, N., Li, Y., Wang, J., & Liao, J. HierNet: A Hierarchical Resource Allocation Method for Vehicle Platooning Networks. IEEE Internet of Things Journal 2024; 11(24), 39579-39592. doi: 10.1109/JIOT.2024.3444044 [17] Zhu, S., Meng, K., Wang, R., & Li, D. Coordinated Computing Resource Allocation With Efficiency Maximization in Heterogeneous Platoon Edge Network. IEEE Transactions on Intelligent Transportation Systems 2024; 25(11),15809-15826, doi: 10.1109/TITS.2024.3435760 [18] Xu, Y., Zhu, K., Xu, H., & Ji, J. Deep reinforcement learning for multi-objective resource allocation in multi-platoon cooperative vehicular networks. IEEE Transactions on Wireless Communications 2023; 22(9), 6185-6198. http://dx.doi.org/ 10.1109/TWC.2023.3240425. [19] Wen, Q., & Hu, B. J. Joint optimal relay selection and power control for reliable broadcast communication in platoon. In 2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall) 2020; 1-6. IEEE. http://dx.doi.org/ 10.1109/VTC2020-Fall49728.2020.9348438. [20] Hong, C., Shan, H., Song, M., Zhuang, W., Xiang, Z., & Wu, Y. . A joint design of platoon communication and control based on LTE-V2V. IEEE Transactions on Vehicular Technology, 2020; 69(12), 15893–15907. https://doi.org/10.1109/TVT.2020.3037239 [21] Kim, J., Han, Y., & Kim, I. Efficient groupcast schemes for vehicle platooning in V2V network. IEEE Access 2019; 7, 171333-171345.. [22] Gonçalves, T. R., Varma, V. S., & Elayoubi, S. E. Relay-assisted platooning in wireless networks: A joint communication and control approach. IEEE Transactions on Vehicular Technology 2023; 72(6), 7810-7826. http://dx.doi.org/ 10.1109/TVT.2023.3239801. [23] Goli-Bidgoli, S., & Movahhedinia, N. Towards ensuring reliability of vehicular ad hoc networks using a relay selection techniques and D2D communications in 5G networks. Wireless Personal Communications 2020; 114(3), 2755-2767. https://doi.org/10.1007/s11277-020-07501-0 [24] Chai, G., Wu, W., Yang, Q., & Yu, F. R. Data-driven resource allocation and group formation for platoon in V2X networks with CSI uncertainty. IEEE Transactions on Communications 2023; 71(12), 7117-7132. doi: 10.1109/TCOMM.2023.3311455. [25] T. Fehrenbach, L. O. O. Abrego, C. Hellge, T. Schierl, J. Ott, 3GPP NR V2X Mode 2d: analysis of distributed scheduling for groupcast using ns3 5G LENA simulator, arXiv preprint arXiv:2508.09708, 2025. [26] T.-W. Kim, S. Lee, D.-H. Lee, K.-J. Park, Priority-driven resource allocation with reuse for platooning in 5G vehicular network, Sustainability 17 (4) (2025) 1747, https://doi.org/10.3390/su17041747. [27] 3GPP, Evolved universal terrestrial radio Access (E-UTRA); Physical layer procedures, 2021, TS 36.213 V16.4.0. [1]