A Multi-Hop Moving Zone (MMZ) Clustering Scheme Based on Cellular-V2X

Zahid Khan, Pingzhi Fan

Key Laboratory of Information Coding and Transmission, School of Information Science and Technology,Southwest Jiaotong University, Chengdu 611756, China

Abstract: A clustering scheme based on pure V2V communications has two prominent issues i.e. broadcast storm and network disconnection. The application of the fifth generation(5G) technology to vehicular networks is an optimal choice due to its wide coverage and low latency features. In this paper, a Multihop Moving Zone (MMZ) clustering scheme is proposed by combining IEEE 802.11p with the 3rd Generation Partnership Project (3GPP)5G cellular technology. In MMZ, vehicles are clustered up-to three hops using V2V communications based on IEEE 802.11p aiming to reduce excessive cellular hand-off cost. While the zonal heads (ZHs) i.e. cluster heads (CHs)are selected by cellular-V2X (C-V2X) on the basis of multi-metrics i.e. relative speed, distance and link life time (LLT). The main goal of MMZ is to form stable clusters achieving high packet delivery and low latency. The simulation results using ns3 show that, 5G wide range technology significantly improves the stability of MMZ in term of ZH duration and change rate. The average Data Packet Delivery Ratio (DPDR) and E2E latency are also improved as compared to the existing clustering schemes.

Keywords: clustering, 3GPP 5G, cluster head,stable clusters, reliability and latency

I. INTRODUCTION

The highly dynamic nature of vehicular ad-hoc network (VANET) is vulnerable to many potential challenges i.e. frequent link disconnection, intermittent connectivity and poor communication between vehicles. The current advancement in VANET is expected to significantly improve the safety of transportation system by providing timely and efficcient data dissemination about events such as accidents, road conditions, and trafficc jams beyond the driver’s knowledge. Strict delay,good throughput and packet delivery are the core requirements for safety transportation system. The dedicated short range communication (DSRC) based on IEEE 802.11p is currently a de-facto standard, which does not offer all trafficc use cases due to its limited data rates ranging from 6 to 27 Mb/s at short range communication distance i.e. around 300m. In high vehicle density scenarios, the DSRC will not be able to offer reliable and low latency communications. According to Cisco, in the near future, say 2019, the consumer of Internet trafficc will be around 80-90% video streaming[1]. The allocated DSRC spectrum for IEEE 802.11p is not expected to support highly video streaming.

Vehicle-to-everything (V2X) communications refer to information exchange between a vehicle and various elements of the intelligent transportation system, including other vehicles, pedestrians, Internet gateways, and transport infrastructure (such as traffic lights and signs). V2X technology has a great potential of enabling a variety of novel applications for road safety, passenger infotainment, car manufacturer services, and vehicle trafficc optimization. The current V2X communication is based on one of two main technologies: dedicated short range communications (DSRC) and cellular networks. V2X communication system based on IEEE 802.11p faces many challenges such as, limited mobility support, lack of advanced use cases support (fully automated vehicles), limited coverage range, latency and reliability etc.[2]. The aforementioned issues become a motivation for cellular based V2X.Cellular-V2X (C-V2X) as initially de fined as LTE V2X in 3GPP Release 14 is designed to operate in several modes such as device-to-device, device-to-cell tower, device-to-network.3GPP Release 14 has many future challenges,so 3GPP Release 15 is introduced in March 2017. 3GPP Release 15 (i.e. 5G) speci fication is divided into two phases, Release 15 NSA(Non-standalone) as a priority and Release 15 Full (with standalone) at a later date in 2018.The 5G Automotive Association (5GAA)directs the advantages of C-V2X technology over IEEE 802.11p to connected transportation service all over the world[3].

A pure V2V based clustering scheme (using IEEE 802.11p) has two prominent issues [4]i.e. broadcast storm and network disconnection. The broadcast problem occurs at high vehicle density, where continuously packets dissemination causes packets delay and number of collisions. In literature, a hybrid architecture (LTE + IEEE 802.11p) based clustering scheme called Vehicular Multi-hop algorithm for Stable Clustering (VMaSC) is proposed in [5]. In VMaSC, the communication model was based on 4G LTE and cluster head (CH)i.e (ZH) selection was relying on relative mobility metric w.r.t neighboring vehicles. The relative location and link life time (LLT)[6]was ignored.

In [7], the authors proposed a novel cluster based routing scheme aim to form stable group of vehicle leading by an optimal cluster head or zonal head (ZH). The ZH selection criterion was contention based on back-off timer (calculated from relative speed or relative distance or link life time (LLT)). Suppose vehicleViandVjhave a very short back-off time gapAssume thatVibroadcasts zonal head announcement (ZHA) to their neighborsNiand lettBtbe the broadcast traverse time to reach allthenVjwill also start broadcasting, which will not only produce broadcast storm, but will also lead to overlapping. The selected metrics in [7] for ZH was good enough to select an appropriate ZH, but the concept of backoff timer leads to overlapping and broadcast storm. To deal with broadcast storm and overlapping problem, we assigned ZH election to the centralized body called eNodeB (discussed in system model) based on multi-metrics (relative speed + relative distance + LLT). Since ZH selection on distributed manner based on IEEE 802.11p, which faces problems such as broadcast storm, network disconnection and back-off timing issues as mentioned in the motivation part [4], [7], that’s why centralized approach is adopted in ZH selection.

The second problem (network disconnection) occurs due to the low traffic density,where the number of nodes may not be able to relay the packets to destination. Multi-hop communication is a good solution to deal with network disconnection problem [5]. MoZo [8]is a good approach to form optimal moving zones i.e. clusters by measuring similarity scores. Apart from some environmental and prediction based specifications issues, MoZo also causes network disconnection problem due to pure V2V communications. Highly fragmented zones will not only increase the number of ZHs, but will also face network disconnection problem due to out of range zones.

In this paper, on the basis of existing state of the art [5], [7], [8], [9], we proposed a novel multi-hop moving zone (MMZ) clustering scheme based on cellular V2X for reliable and low latency communications. The main contributions are given below.

? The proposed MMZ utilizes the benefits of two prominent technologies i.e IEEE 802.11p and 5G LTE. The multi-hop zones are formed using IEEE 802.11p, while the zonal head (ZH) selection and wide range communications are performed using 5G.The zonal members (ZMs) i.e. cluster members (CMs) communicate with ZH via IEEE 802.11p, whereas ZH communicates with other ZH and pedestrians via 5G cellular technology.

? To cope with the back-off timer issue [7],MMZ proposed a new ZH selection algorithm to select an appropriate ZH on the basis of multi-metrics i.e. relative speed,relative distance and link life time (LLT).

? It is shown that the proposed C-V2X MMZ is more stable in term of ZH duration and change rate. The multi-hop connections reduce the number of ZHs, which further reduces the cellular hand-off cost [5]. The proposed clustering scheme also achieved good DPDR and E2E latency due to the wide coverage technology.

The rest of the paper is organized as follows, Section II describes the system model in detail, III explains MMZ clustering algorithm,Section IV deliberates on the experimental study along with discussion and V concludes the paper based on simulation results.

II. SYSTEM MODEL

Consider a multilane road of lengthLcovered by IEEE 802.11p and 5G hybrid architecture[10] as shown in figure 1. The vehicles enter into the highway follow Poisson distribution[11], [12], where speed of each vehicle modeled as Normal distribution [11], [13], [14]. It is assumed that each vehicle is embedded with two types of interfaces i.e. PC5 or LTE D2D interface and Uu. The GPS embedded inside OBU (on-board unit) provides vehicle’s basic information including vehicle’s speed, direction and location.

The vehicles form multi-hop moving zones in each direction of the road. The vehicles lie in the transmission rangeRof ZH become a 1-hop ZMs. All 1-hop ZMs can communicate directly with ZH. On the other hand, the indirect connected vehicles via intermediate hops become multi-hop (M)ZMs which communicate with other ZMs through ZH. In a given zone, all the ZMs use 802.11p to communicate with other cluster members, whereas ZH communicates with ZMs via IEEE 802.11p and with eNodeB via 5G LTE. ZH can communicate with pedestrians (having cellular device)directly or indirectly.

The 5G LTE infrastructure aims to disseminate the packets to the vehicles inside a geographical region. The structure of 5G LTE is depicted in figure 2.

Fig. 1. System model

Fig. 2. 5G functional structure

In LTE, each cell is managed by an eNodeB and evolved packet core (EPC). Furthermore EPC consists of server gateway (SGW) and packet data network gateway (PGW). SGW uses for routing and forwarding packets to eNodeBs and pedestrians, whereas PGW is responsible for QoS control, authentication and setting the transfer paths of vehicles data packets. EPC has global information of all eNodeBs and pedestrians in a given safety transportation region. eNodeBs form moving zones based on multi-metrics i.e. relative speed Δv, relative distance ΔDand link life time (LLT). When ZH sends a packet to eNodeB, the packet is sent to the EPC over wired network. The EPC disseminates the received packet to all eNodeBs within the geographical region, and finally eNodeB multi-casts the packet to all the ZHs.

III. PROPOSED MULTI-HOP MOVING ZONE (MMZ) CLUSTERING SCHEME

The main features of MMZ are given below.

1) It selects stable and consistent ZH by the use of multi-metrics composed on three factors such as relative speed Δv, relative distance ΔDand link life time LLT.

2) The proposed clustering algorithm is reactive in nature, the multi-hop nodes are connecting with ZMs directly instead of excessive messages to ZH.

3) The multi-hop property reduces the number of clusters, which further decreases the cost of hand-overs signi ficantly with eNodeBs.

4) The wide coverage cellular technology solves the problem of zone disconnection which reduces the communication latency.

3.1 Vehicle states

The followings are different states of vehicle in the proposed clustering algorithm.

1) Undecided Vehicle (UV): The state of vehicle before classification of nodes into zones.

2) 1-hop Neighbors: Set of neighbors directly accessible to ZH or ZM.

3) Multi-hop Neighbors: Set of neighbors accessible to ZH through intermediate vehicles.

4) Zonal Head (ZH) or Cluster Head (CH):The leader of the zone. The responsible node among zone’s members, whose aims to communicate with ZMs and pedestrians via IEEE 802.11p and eNodeB respectively.

5) Zonal Member (ZM) or Cluster Member:The vehicles directly attached to ZH.

6) Multi-hop Zonal Member (MZM): The vehicles attached to ZH via other ZMs.

3.2 Bootstrap

Bootstrapping refers to the initial loading of necessary information. All the vehicles disseminate beacons messages to 1-hop neighbors aim to estimate their neighbors set (NS).Beacon message includes vehicle’s ID, position (x,y), speedv, directionDir, and laneID. Once all the vehicles got theirNS, they unicast to the regional base station named as eNodeB.NSinformation repository is given in table 1 below.

The direction of vehicles in table 1 is represented by flag value, where 1 is for same direction and -1 for opposite direction.

3.3 Zonal head (ZH) selection

As mentioned in the literature, many authors used different criteria to select appropriate cluster head. Most of the existing schemes cause either computational overhead or communicational overhead. Here in this work,a new combo metric (CM) is introduced to select a stable and consistent zonal head.The CM is composed on three sub metrics such as average relative speedvavgaverage relative distanceDavgand average link life time (LLTavg) [6]. The CM for each vehicle is calculated by the centralized point named as eNodeB. The vehicle having the smallest CM value will be elected as ZH.

LLT de fines the robustness and duration of the two vehicles link. The mathematical de finition of LLT [15] is given as below

In Eq(1),Rrepresents the transmission range of each vehicle. In the given de finition ofLLT, all the vehicles are considered to travel in straight line. TheLLTijrepresents the link duration between vehicleViandVj,wherecleVicalculates the averageLLTavg, average relative speed Δvavgand average relative distance ΔDavgas below

whereNiis the number of vehicles inNS. The proposed CM for ZH selection is given as

Table I. Neighbor set(NS) information.

where ΔLLTmaxis given as the same time as the simulation timeT, ΔDmaxis considered the same as that ofR, Δvmaxis same as that of maximum allowed speed on highway. Theαandβrepresent the relative importance of location and mobility respectively. Here relative speed is considered relatively more important than location. The value ofαandβwill be small, if the vehicles are relatively similar w.r.t mobility and location.

In the proposed ZH selection combo metric(CM), weights of relative distance and speed are added, whereαandβrepresent the relative importance of both factors supporting by reference [16]. The said factors (relative distance and speed) are independent, but both of them are further depended on transmission rangesR[17]. In order to consider the impact of transmission rangeR, we added LLT to get more accurate and consistent ZH. In a real scenario, two vehicles may be strongly connected w.r.t relative distance and speed,but their weak radio signals will affect the communication session signi ficantly, which is the main motivation for the summation of LLT with weighted relative distance and speed.

The centralized point measures the CM for all vehicles belong toNSand elects the ZH with minimum value among allNSvehicles.Finally, the selected ZH is multi-casted to all theNSvehicles and pedestrians on the road.The complete pseudo code of ZH selection is given in Algorithm I, which calculates the CM for all 1-hop neighbors step by step and selects the ZH with minimum value.

3.4 Multi-hop topology construction

It has already been discussed that short range communication causes broadcast storm [18]and network disconnection [19]. On the other hand, large number of clusters also causes high hand-off cost over base station [5], [20],[21]. In order to cope with these problems,multi-hop based clusters will not only extend the coverage area, but will also reduce the number of ZHs. The complete procedure of multi-hop construction is given in Algorithm 2.

Algorithm 2 iteratively selects ZMs and checks its availability in the directly connected neighbors directory, in case of unavailability the hop count of ZM incremented by 1 and put that node in the multihop zonal member(MZM) category. Upon the reception of periodic hello messages, vehicles keep update MZMs information.

3.5 Zone formation

The zone formation function is done by the centralized point by passing theNSand (M)ZMs as an inputs. Any vehicle is randomly selected and its status is checked, if the selected vehicle belongs toNSi, it becomes ZM of the ZHi. If the selected vehicle is multi-hop neighbor, it will be put in the zone of its directly connected neighbor. Each zone has certain restrictions on both number of ZMs and length of multi-hop members. A new vehicle will be nominated as a candidate for ZM, ifMAXNUMBERof zonal members andMAXhopsare within the given threshold. The complete step by step procedure is given in Algorithm 3.

3.6 MMZ maintenance

In the proposed MMZ scheme, ZHs updates depend on cluster members (i.e. ZMs) updates in case of topological change. Once a ZM left the zone due to a direction change or some other reasons, then leaving the zone condition will be activated to update the zone (i.e.cluster). In case of leaving a zone, the ZM is responsible in ideal case to inform all the NS members through beacon messages.

In some special cases, where a vehicle may not be able to disseminate the leaving message to neighbors, then a counter will be set to 180 seconds. After the expiration of counter, all the nodes will flush out that ZM information and will inform the centralize point to reform the zone structure and then will check the status of current responsible ZH. If the leaving of speci fic ZM changes the value of CM signi ficantly, then ZH update will be activated.

The same rules are also carried in ZM joining process. The joining of new member will also be disseminated to the zonal members and will further direct to the central point to check the possibility of ZH update.

IV. SIMULATION RESULTS AND DISCUSSIONS

The goal of the simulation is to evaluate the worth of the proposed C-V2X based clustering scheme. The simulations are performed in the Network Simulator ns3 (Release 3.26) [22]with the help of LENA (LTE-EPC NetsimulA-tor) projects code [23]. The ns3 is an emerging discrete event based network simulator aims to replace ns2. A highway with 3 lane grid having 10Km moving boundary is selected for mobile vehicles and pedestrians. The initial position of eNodeB is set to (0, 0) coordinates.Table 2 and 3 show the simulation parameters of VANET and 5G networks respectively. The maximum number of hops within a cluster is set to two based on references [5], [24], [25],since more number of hops reduce the stability due to excessive hello messages dissemination. The values ofαandβare kept 0.6 and 0.4 in combo metric (CM) for relative location and speed respectively.

Three types of experiments are performed here, first the stability of the proposed MMZ is compared with the previously VANET clustering algorithms such as VMaSC [5], Triple Cluster based Routing Protocol (TCRP) [16],and multi-hop clustering algorithms NHoP[26]. Second the impact of ZH’s members(Constraint on the maximum number of ZMs that a speci fic ZH can admit) or simply zonal/cluster sizes are analyzed over number of ZHs,third latency and Data Packet Delivery Ratio(DPDR) are also examined and compared with the existing proposed hybrid architectures as mentioned above.

The said protocols are also cluster based schemes, where cluster formation and ZHs(i.e. CHs) are selected on different criteria.VMaSC is hybrid architecture like proposed MMZ, but the core differences are cluster formation, ZH selection and the cellular technology (4G). Besides, VMaSC used multihop based clustering approach, where relative mobility is used as a ZH selection criterion.

Similarly, TCRP is also a clustering scheme, where clusters are formed by modified K-means. In TCRP, the authors used Floyd Warshall algorithm for ZH i.e. CH selection based on relative distance and speed variance. In this paper, TCRP is extended to LTE-TCRP and then compared with MMZ.

Lastly, MMZ is compared with a multi-hop NHoP scheme. The main purpose of NHoP protocol is to form consistent clusters. The authors used a new mobility metric to represent relative mobility between vehicles in multihop distance.

MMZ is different from all of the above protocols because of the new ZH selection criteriaand cellular technology (3GPP 5G).

Table II. ns3 Simulation Parameters for V2X.

Table III. ns3 Simulation Parameters for 5G LTE.

4.1 Stability analysis w.r.t diあerent speed

In order to evaluate the stability of MMZ clustering scheme, two prominent performance metrics such as cluster head change rate and cluster head duration are considered. The main objective of the proposed MMZ clustering scheme is to reduce the ZH change rate and to increase the duration of ZH.

1) ZH Change Rate: ZH rate is de fined as the number of re-selections of ZHs per unit time.

During the simulation timeT, if the total number of ZH isNZH, then ZH change rate can be calculated as below

Whereviis the selected ZH fromNZH. On the basis of results, it is concluded that proposed C-V2X (i.e 5G) based MMZ clustering scheme is more stable in the context of ZH variation rate as depicted in figure 3.

The changing rate of ZH in the proposed MMZ is lower than TCRP, VMaSC and NHoP in all cases due to the adaptation of wide coverage 5G technology. The expanded coverage enhanced the LLT’s of ongoing vehicles,which eliminates the ir-relevant variation of selected ZH. The multi-metric criterion of MMZ’s ZH election selects a consistent and centralized node, which prolongs the duration and reduces the re-selection rate. Due to the technology advancement and better ZH’s selection metric, MMZ defeat VMaSC in term of ZH change rate. NHoP and TCRP use periodic clustering maintenance, which causes unnecessary CH change in the network. Similarly increasing the number of hops allowed in the clusters decreases the ZH change rate and,thus, increases the stability of MMZ. The high variation in speed does not affect the leadership of selected ZH to compel it on changing its status as depicted in figure 3.

2) ZH’s Duration: refers to the time when a ZH changes its status to an ordinary ZM.ZH’s duration is also an important metric,which can be calculated as below

In figure 4, the average ZH duration is shown in all different speeds. The life time of MMZ’s ZH is higher than existing VMaSC,TCRP and NHoP due to the advance 5G technology and multi-metric ZH selection feature.The expanded transmission boundaries and centralized position of ZH are leading to high duration of leadership.

Apart from the stability analysis, the impact of multi-hop structure over number of ZHs is also analyzed. Furthermore, two other metrics such as DPDR and E2E latency are also selected to evaluate the signi ficance of the proposed cluster scheme.

4.2 Multi-hop topological structure impacts on number of ZHs

In general, the number of zones/clusters i.e.the number of ZHs decrease with multihop V2V communications, but the practical number of zones or ZHs also depends on the number of supported ZH’s members (i.e. zonal/cluster size) as shown in figure 5. The line graph shows that in 1-hop communication,the size of cluster/zone has an inverse relation with number of ZHs i.e. by increasing zonal size, number of clusters will decrease. But in multi-hop case, the situation is not so simple.We can say that in moderate zonal size (CH’s members = 5), the multi-hop feature reduces the number of ZHs and improves the performance. But in case of large zonal size (more ZMs attached to ZH) in multi-hop case, there will be higher contention around the ZHs,which will lead to packet loss and may also cause of link breakage. Hence it is concluded that in big zones (where ZH admits more ZMs), the performance degrades in multi-hop case due higher number of clustering and control messages, which will lead to zonal splitting and will increase the number of ZHs.

Fig. 3. Zonal head variation w.r.t different speeds(number of hops = 3).

Fig. 4. Zonal head duration w.r.t different speeds (number of hops = 3).

4.3 Latency and DPDR analysis w.r.t diあ erent speed

The second part analyzes the latency and DPDR of the proposed scheme with existing hybrid architectures as mentioned above.

Due to the enhanced clustering maintenance scheme, the proposed MMZ performs very well in the context of latency and DPDR.

1) E2E Latency: refers to the time taken by a data packet to reach from a source vehicle to destination vehicle.

Fig. 5. Impact of ZH’s members on number of ZHs.

Fig. 6. E2E latency analysis (video packet size = 1400 bytes), ZH’s members = 5,Maxhops=2 .

The E2E latency of proposed MMZ and other existing clustering schemes are shown in figure 6. It is shown that the latency is quite low as compare to the existing approaches.The advancement in technology from 4G to 5G improves the communication quality,which not only reduces the E2E latency, but also improves the average data packet delivery. The VMSaC schemes defeated by the proposed MMZ due to efficcient ZH selection and advance 5G technology. The rest of the two schemes TCRP and NHoP are improved with hybrid architectures, but not too much as compare to the advance MMZ clustering strategy.

In-fact, multi-hop structure increases the overhead due MAC contentions in V2V communications. Here, we used 2-hop structure with moderate number of ZH’s members support. In the given setup, MMZ ensured optimal number of zones, where all the performance metrics will signi ficantly improve. In the context of E2E delay, MMZ is compared with other multi-hop schemes except TCRP that’s why the same impact will be observed in all selected protocols, hence our results are fair in the given setup. Regarding TCRP (Non multihop scheme), where three clusters are formed,therefore in congested vehicular scenario; the performance will be worst and will lead to packet loss and link breakage.

2) Data Packet Delivery Ratio (DPDR): The DPDR metric refers to the ratio of the number of vehicles successfully receiving data packets to the total number of vehicles within the target geographical area for the dissemination of the data packet.

Figure 7 shows the DPDR of different clustering schemes at different speeds. The DPDR of proposed MMZ is above all the existing schemes in all cases. The reasons for the superior DPDR performance of MMZ over the other hybrid architectures, namely, VMaSC,TCRP and NHoP, are better clustering stability, minimal clustering overhead, and minimal overlap among clusters.

On the basis of results, it is concluded that 3GPP 5G based V2X is a good addition to VANET technology. Apart from the technology renovation, the proposed ZH selection criteria and multi-hop approach significantly improve the performance of MMZ clustering protocol.

V. CONCLUSION

In this paper, the proposed C-V2X MMZ uses an architecture that integrates 5G cellular technology with DSRC based VANET networks.The new clustering scheme based on C-V2X achieves good DPDR, low latency and better stability. 5G’s wide range communication and multi-metric ZH selection criteria enabled MMZ clustering scheme more stable in term of ZH duration and variation rate. C-V2X MMZ achieves much lower delay and high DPDR due to better clustering stability, minimal clustering overhead, and minimal overlap among clusters. The multi-hop feature not only overcome the high handoff cost, but also copes with the network disconnection problem.

Fig. 7. Average Data Packet Delivery Ratio (DPDR) analysis (video packet size =1400 bytes).

ACKNOWLEDGMENT

This work was supported by the NSFC key project under Grant No.61731017 and the 111 project under Grant No.111-2-14.