# A Vehicular Service-Oriented Dynamical Routing Searching Algorithm in Software-Defined BusNet

Authors: Lingqiu Zeng; Sheng Cheng; Qingwen Han; Lei Ye
Journal: Mobile Information Systems
 (2020)

---

## Abstract

With the development of the vehicular network, BusNet-based service is of great interest to both bus companies and public users. How to provide service and ensure service quality is considered as key points for the promotion of such kinds of applications. In this paper, a system architecture, which is designed based on multiaccess edge computing (MEC) architecture and software-defined network (SDN), is proposed. Moreover, considering the problem of the dynamicity of the network, a new routing path optimization algorithm, SPSO (serial particle swarm optimization), is proposed, while a dynamic weight matrix is used to improve routing performance. The comprehensive simulation results demonstrate that the proposed method can well adapt to the dynamic change of network topology and improve communication performance significantly.


---

## Body

## 1. Introduction

With recent advances in wireless communication technologies, vehicular ad hoc networks (VANETs) have received much attention in both industries and academia for enabling emerging Intelligent Transportation Systems (ITSs), such as autonomous intersection control [1], cooperative vehicular positioning [2], and advanced information sharing [3].Besides basic safety message [4] that received considerable attention from the public, the abundant services that can improve user experience are gradually becoming a commercial hot spot too.Buses, equipped with powerful communication and storage capability, are considered as a powerful service provider, which could provide commercial messages according to passenger’s request. Hence, some bus companies believe that information service could bring benefits for public transport operators. Some previous research utilized buses as routing relays to improve network connectivity [5, 6]. A few studies considered the bus ad hoc network (BusNet) as the delay/disruption-tolerant network (DTN), and different routing strategies based on the historical driving traces have been proposed [7]. The geocast in BusNet has also been widely investigated [8–10], where the mobility statistics from the historical traces are exploited for designing routing paths. However, none of the above studies have considered the delay-constrained routing in the BusNet.Moreover, both academia and industry believe that a software-defined network (SDN) [11] can conveniently be applied to support the dynamic nature and dense deployment scenarios of future VANET functions and applications while reducing the operation cost [12].However, the only problem is how to guarantee the quality of service (QoS). BusNet can provide information service via a routing path between information source and destination nodes. Therefore, the corresponding QoS problem could be transformed into a routing optimization problem, which includes two key points, routing strategy and optimization algorithm.Due to the dynamic nature of vehicle nodes, VANETs have highly dynamic topology. Researchers are more inclined towards adopting an opportunistic routing strategy [13], which utilizes a set of candidate nodes and discovers the shortest path according to index metric. Literature [14] employed three communication performance parameters—packet loss, delivery delay, and path accessibility—as the index for routing path selection but did not discuss the weight feature of the selected index. Hence, in this paper, we use the index metric of literature [14] and focus on the weight factor optimization.The other left question is the optimization algorithm. Researchers believe that search algorithms, such as genetic algorithm [15], neighborhood search algorithm [16], and particle swarm optimization (PSO) [17], could be used in dynamic routing path selection. In PSO searching progress, each particle’s moving direction is influenced by its inertness, local best-known position, and the group’s best-known position. As the local best-known position is computed according to the historical data of this specific particle in the past few cycles, the group’s best-known position is selected from the whole group historical data in the past few cycles. Based on this searching mechanism, PSO is able to solve the optimization problem lightly by calculating particle position and velocity, which represent the optimization result and iteration process, respectively. Since the different combinations of weights of VANET key factors can be regarded as the position of several particles, we believe that PSO strongly matches the demand of our application and will perform well in routing path discovery progress.To deal with the time efficiency problem of PSO searching, in this paper, we proposed a new algorithm, serial particle swarm optimization (SPSO), to realize routing path optimization in SDN.Given the above problems, the main contributions of this work are outlined as follows:(i)
We propose a software-defined BusNet consisting of 4 layers: user layer, bus layer, roadside layer, and control layer.(ii)
Based on the presented architecture, a data fusion scheme in the SDN framework is deployed.(iii)
Two algorithms are employed to solve the routing selecting problem. Firstly, we use a modified Bellman–Ford algorithm to select the shortest path. Then, an intellectual algorithm called SPSO is applied to adapt to the network dynamicity while selecting the route.(iv)
We conduct a simulation for these two algorithms to enhance the quality of service and discuss the relevant improvement of using the SPSO algorithm to reduce the packet delivery delay and packet loss.The rest of this paper is organized as follows. We review the related work in Section2. Section 3 describes the proposed system architecture. Section 4 formulates the problem of route selecting and presents the calculation of factors we focused on. Routing selecting problem is proposed in Section 5. In Section 6, we propose the SPSO algorithm based on PSO to solve the optimization problem. In Section 7, simulation and evaluation of the results are given. The conclusion and future work are discussed in Section 8.


## 2. Related Work

In VANETs, a lot of effort has been devoted to the designing of routing protocols for the aim of enhancing the QoS. Eiza et al. [18] proposed a SAMQ (Situation Aware Multiconstrained QoS) routing algorithm to compute feasible routes and select the best route subject to multiple QoS constraints. The SA levels and ACS (Ant Colony System) mechanism are utilized at intermediate nodes to respond to the link breakage without interruption, and they not only replace the broken link but also consider the QoS requirements of data transmission. Togou et al. [19] developed a distributed geographic source routing scheme named SCRP (Stable CDS-based Routing Protocol), which built the stable backbones over the road segment by considering vehicles’ speed and spatial distribution and connected them through the dynamically elected bridge nodes at intersections. Nevertheless, their research ignores the constriction of communication bandwidth and the dynamicity of the network.Besides, routing design with buses based on SDN in the city network has also been excavated to solve the problem of the lack of calculation capacity and space sparsity of vehicle distribution. Wang et al. [14] designed a BusNet, using buses as service providers, to forward response packets and introduce SDN into BusNet, believing that the SDN controller is fitted for the role of routing path decision-maker. They employed three communication performance parameters—packet loss, delivery delay, and path accessibility—as the index for routing path selection, but did not discuss the weight feature of the selected index. Although the architecture proved to be a success, the algorithm to find a feasible route did not fit the scenario of high dynamical characteristics. Jiang and Du [20] designed a VANET architecture that integrated buses, RSUs, and TCC (Traffic Control Center) for providing data services. Each vehicle needs to register with a nearby high-tier node (i.e., RSU or bus), which is connected to TCC. The proposed registration technology reduces the number of switches in the routing path by utilizing the updated registration message to locate destination vehicles and selecting the proper registration nodes as relays. This research focused on the bandwidth, yet it failed to take the dynamicity into consideration, which is the core problem of VANET.Furthermore, many research works have studied the application of intellectual algorithm in routing strategies. Shirmarz and Ghaffari [21] propose a greedy flow routing algorithm on SDN to enhance the QoS. They consider a series of network variables including connectivity, bandwidth, delay, jitter, and packet loss of links matrices. After selecting all paths between source and destination nodes, they use the greedy algorithm to try to select the best path in every step. Oh et al. [22] propose the RT-SDN for priority order and adaptive routing that can guarantee the required bandwidth. Zhao et al. [23] propose a joint optimization of flow entry aggregation and routing selection in SDN, but this solution only focuses on delay. Fei et al. [24] work on virtual network function (VNF) to provide flexible services, and they use an efficient online learning method to predict the service chain demand and propose two algorithms for new instance assignment and service chain rerouting. Feng et al. [25] present the design of distributed online solutions that drive flow processing and routing decisions, along with the associated allocation of cloud and network resources. In [26], the authors’ goal is to determine the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. Bagci and Tekalp [27] propose a heuristic group-constrained SP procedure that aims for a fair allocation of resources among a group of requests with the same service level while maximizing the total NSP (Network Service Provider) revenue. All the above studies have done a good job on the route decision; however, the problem is that their solution cannot be applied to a moving model especially when the cars or the users of which own huge mobility.Distinguished from the above studies, our work focuses on the dynamicity of BusNet and addresses the problem of routing selecting, thereby enhancing the quality of service. We propose an architecture that can conveniently compute the attributes of each link and then construct a network graph at the controller. In addition, the architecture can save considerable bandwidth and use buses to solve the space sparsity problem. What is more, based on the graph on the controller, an intellectual algorithm, SPSO, is proposed to handle the problem of dynamicity. As a result, the users are able to get a high-quality service according to the suitable communication route.


## 3. System Architecture

In this section, we shall introduce a basic system architecture that provides BusNet-based service. Meanwhile, a corresponding message dissemination progress should be explained.


### 3.1. System Framework

Here, we employ a BusNet-oriented SDN architecture, which includes four layers—namely, user layer, bus layer, roadside layer, and controller layer—to provide information service, as shown in Figure1.(1)
User layer: the user layer includes social vehicles equipped with LTE-V2X OBUs. Each vehicle could be considered as a user, who has information service requirements.(2)
Bus layer: the buses act as information collectors and service providers. Here, we assume that all buses are equipped with LTE-V2X OBUs and have sufficient storage room to store the collected information.(3)
Roadside layer: it includes a roadside unit (RSU) and the cellular base station (BS) and performs information aggregation and redundant information filtering.(4)
Controller layer: controller acts as a global manager, which executes routing path optimization procedure.Figure 1
Architecture of the software-defined network.


### 3.2. Message Dissemination Progress

The whole service providing process includes two steps of message dissemination progress; one is service information collection, while the other is service request/response.


#### 3.2.1. Service Information Collection

Sequence diagram of service information collection is shown in Figure2.Figure 2
Sequence diagram of service information collection.As service subscribers, cars are not involved in this procedure. Bus node generates the Neighborhood Message (NMSG) packet, which includes state information of the bus and its neighboring bus, such as Bus ID, cruising velocity, heading, and GPS position, and broadcasts NMSGs periodically. Meanwhile, the bus node collects service information, such as discount posters, shopping mall opening, 24-hour store position, etc. RSU/BS collects NMSGs, filters redundant information, and generates a message packet NMSG_AggreTag, which is uploaded to the controller. Note that, here, RSU/BS can be geographically organized in several service areas, while each one is governed by an SDN controller. According to NMSG_AggreTag, the SDN controller generates a service map, which includes network status and GPS information of bus nodes.


#### 3.2.2. Service Request/Response

Sequence diagram of request/response is shown in Figure3.Figure 3
Sequence diagram of request/response.If a vehicle user has a service requirement, it should send a request packet to the controller. According to the request packet, the controller searches for an information source and will employ a routing path optimization algorithm to select the most suitable routes from the bus route set. Then the controller generates a Link Tag message and sends it to bus nodes. The source bus node sends service information to the target bus node, which provides service to the vehicle user. At last, the vehicle user node should feed back corresponding performance features, such as service delay and packet loss ratio, to the controller.


#### 3.2.3. Data Filtering

To improve the efficiency of BusNet service, a data filtering process, whose pseudocode is shown in Algorithm 1, is done by RSUs/BSs. Corresponding variables and functions definitions are given in Table1.Algorithm 1: Data filtering.
input: thisMessage, lastMessagesoutput: messages(1)
newMsgFlag ⟵ true(2)
Fori = 0 ⟶ lastMessages.size ()-1 do(3)
if lastMessages [i].srcId = thisMessage.srcId then(4)
newMsgFlag ⟵ false(5)
if allSame (lastMessages [i], thisMessage) then(6)
throwMessage (thisMessage)(7)
else(8)
updateMessage (thisMessage)(9)
newMsgFlag ⟵ true(10)
end if(11)
end if(12)
end for(13)
if newMsgFlag = true then(14)
addMessage (thisMessage)(15)
end if(16)
return lastMessagesTable 1
Explanation of variables and functions in data filtering.
Variable/functionExplanationthis MessageMessage of current searching period.last MessagesMessages of last searching period.new Msg FlagA flag message expresses that current message is sent by a new bus node.all Samep1,p2Content of packetp1 is the same as that of packet p2.throw MessagepDiscard current message.update MessagepUpdate messagep in database.add MessagepAdd messagep to database.


## 3.1. System Framework

Here, we employ a BusNet-oriented SDN architecture, which includes four layers—namely, user layer, bus layer, roadside layer, and controller layer—to provide information service, as shown in Figure1.(1)
User layer: the user layer includes social vehicles equipped with LTE-V2X OBUs. Each vehicle could be considered as a user, who has information service requirements.(2)
Bus layer: the buses act as information collectors and service providers. Here, we assume that all buses are equipped with LTE-V2X OBUs and have sufficient storage room to store the collected information.(3)
Roadside layer: it includes a roadside unit (RSU) and the cellular base station (BS) and performs information aggregation and redundant information filtering.(4)
Controller layer: controller acts as a global manager, which executes routing path optimization procedure.Figure 1
Architecture of the software-defined network.


## 3.2. Message Dissemination Progress

The whole service providing process includes two steps of message dissemination progress; one is service information collection, while the other is service request/response.


### 3.2.1. Service Information Collection

Sequence diagram of service information collection is shown in Figure2.Figure 2
Sequence diagram of service information collection.As service subscribers, cars are not involved in this procedure. Bus node generates the Neighborhood Message (NMSG) packet, which includes state information of the bus and its neighboring bus, such as Bus ID, cruising velocity, heading, and GPS position, and broadcasts NMSGs periodically. Meanwhile, the bus node collects service information, such as discount posters, shopping mall opening, 24-hour store position, etc. RSU/BS collects NMSGs, filters redundant information, and generates a message packet NMSG_AggreTag, which is uploaded to the controller. Note that, here, RSU/BS can be geographically organized in several service areas, while each one is governed by an SDN controller. According to NMSG_AggreTag, the SDN controller generates a service map, which includes network status and GPS information of bus nodes.


### 3.2.2. Service Request/Response

Sequence diagram of request/response is shown in Figure3.Figure 3
Sequence diagram of request/response.If a vehicle user has a service requirement, it should send a request packet to the controller. According to the request packet, the controller searches for an information source and will employ a routing path optimization algorithm to select the most suitable routes from the bus route set. Then the controller generates a Link Tag message and sends it to bus nodes. The source bus node sends service information to the target bus node, which provides service to the vehicle user. At last, the vehicle user node should feed back corresponding performance features, such as service delay and packet loss ratio, to the controller.


### 3.2.3. Data Filtering

To improve the efficiency of BusNet service, a data filtering process, whose pseudocode is shown in Algorithm 1, is done by RSUs/BSs. Corresponding variables and functions definitions are given in Table1.Algorithm 1: Data filtering.
input: thisMessage, lastMessagesoutput: messages(1)
newMsgFlag ⟵ true(2)
Fori = 0 ⟶ lastMessages.size ()-1 do(3)
if lastMessages [i].srcId = thisMessage.srcId then(4)
newMsgFlag ⟵ false(5)
if allSame (lastMessages [i], thisMessage) then(6)
throwMessage (thisMessage)(7)
else(8)
updateMessage (thisMessage)(9)
newMsgFlag ⟵ true(10)
end if(11)
end if(12)
end for(13)
if newMsgFlag = true then(14)
addMessage (thisMessage)(15)
end if(16)
return lastMessagesTable 1
Explanation of variables and functions in data filtering.
Variable/functionExplanationthis MessageMessage of current searching period.last MessagesMessages of last searching period.new Msg FlagA flag message expresses that current message is sent by a new bus node.all Samep1,p2Content of packetp1 is the same as that of packet p2.throw MessagepDiscard current message.update MessagepUpdate messagep in database.add MessagepAdd messagep to database.


## 3.2.1. Service Information Collection

Sequence diagram of service information collection is shown in Figure2.Figure 2
Sequence diagram of service information collection.As service subscribers, cars are not involved in this procedure. Bus node generates the Neighborhood Message (NMSG) packet, which includes state information of the bus and its neighboring bus, such as Bus ID, cruising velocity, heading, and GPS position, and broadcasts NMSGs periodically. Meanwhile, the bus node collects service information, such as discount posters, shopping mall opening, 24-hour store position, etc. RSU/BS collects NMSGs, filters redundant information, and generates a message packet NMSG_AggreTag, which is uploaded to the controller. Note that, here, RSU/BS can be geographically organized in several service areas, while each one is governed by an SDN controller. According to NMSG_AggreTag, the SDN controller generates a service map, which includes network status and GPS information of bus nodes.


## 3.2.2. Service Request/Response

Sequence diagram of request/response is shown in Figure3.Figure 3
Sequence diagram of request/response.If a vehicle user has a service requirement, it should send a request packet to the controller. According to the request packet, the controller searches for an information source and will employ a routing path optimization algorithm to select the most suitable routes from the bus route set. Then the controller generates a Link Tag message and sends it to bus nodes. The source bus node sends service information to the target bus node, which provides service to the vehicle user. At last, the vehicle user node should feed back corresponding performance features, such as service delay and packet loss ratio, to the controller.


## 3.2.3. Data Filtering

To improve the efficiency of BusNet service, a data filtering process, whose pseudocode is shown in Algorithm 1, is done by RSUs/BSs. Corresponding variables and functions definitions are given in Table1.Algorithm 1: Data filtering.
input: thisMessage, lastMessagesoutput: messages(1)
newMsgFlag ⟵ true(2)
Fori = 0 ⟶ lastMessages.size ()-1 do(3)
if lastMessages [i].srcId = thisMessage.srcId then(4)
newMsgFlag ⟵ false(5)
if allSame (lastMessages [i], thisMessage) then(6)
throwMessage (thisMessage)(7)
else(8)
updateMessage (thisMessage)(9)
newMsgFlag ⟵ true(10)
end if(11)
end if(12)
end for(13)
if newMsgFlag = true then(14)
addMessage (thisMessage)(15)
end if(16)
return lastMessagesTable 1
Explanation of variables and functions in data filtering.
Variable/functionExplanationthis MessageMessage of current searching period.last MessagesMessages of last searching period.new Msg FlagA flag message expresses that current message is sent by a new bus node.all Samep1,p2Content of packetp1 is the same as that of packet p2.throw MessagepDiscard current message.update MessagepUpdate messagep in database.add MessagepAdd messagep to database.


## 4. Problem Formulation

This section is to abstract the problem in reality into mathematical problems. We will give the problem statement and explain the selected index in detail.The following assumptions are made:(1)
BusNet fully covers the object area, which is divided into several nonoverlapping service areas(2)
Each service area is covered by RSUs/BSs placed in fixed locations(3)
Each service area can be controlled by one or several SDN controllers(4)
User nodes and bus nodes broadcast message periodically via LTE-V2X OBU(5)
The SDN controller could be implemented as 1-to-N associated with vehicle node via RSUs/BSs relayBusNet is abstracted as a directed graphGB,E, where B and E are the sets of bus nodes and edges. We assume that there are n paths between information source bus node and service subscriber bus node; then, the set of all candidate routing paths can be denoted by P=p1,p2,…,pn. As mentioned earlier, in this paper, we employ three communication performance factors—packet loss, delivery delay, and path accessibility—as the index for routing path selection. Assuming that a routing path includes m edges, we defined routing path comprehensive training evaluation index as follows:(1)Cpi=∑k=1mCpik,where Cpi is the comprehensive training evaluation index of routing path i and k represents the kth pair of bus nodes of this path. Cpik is the cost of every pair of bus nodes and is defined as follows:(2)Cpik=wp×Plossik+wd×delayik+wa×accik,where Plossik, delayik, and accik are packet loss, delivery delay, and path accessibility of routing path i for kth bus nodes pair. wp, wd, and wa are corresponding weight factors of all the above three factors, and the combination of which implies different focus on network attributes.Then those three factors can be denoted as(3)pLossik=2×g1−NRikNSik−1,delayik=2×g∑j=1NRdelayikjNRik−1,accik=2×1−gLik,where(4)LE2=xBs−xBe−vBssinθBs−vBesinθBe2+yBs−yBe−vBscosθBs−vBecosθBe2,gz=11+e−z.For one edge with two bus nodes,NS is the sent packet number, and NR is the received packet number. Delayj is the dissemination delay of a specific packet, and L is the length of this edge after one second. Bs and Be are the start and end bus nodes of this edge, and xBs, yBs, vBs, and θBs represent the horizontal location, vertical location, velocity, and moving direction of Bs, respectively. Then, the set of routing path comprehensive training evaluations’ index is denoted by Cp=Cp1,Cp2,…,Cpn, and routing selecting problem is formulated as follows:(5)minpi∈pCpi.On the other hand, after selecting a route through training evaluations, we need to use another index called generalization evaluation to evaluate the performance of this specific path in real communication.We define generalization evaluation as follows:(6)Gpi=lossi+delayi2,here, Gpi represents the generalization evaluation, and lossi and delayi represent the statistical result of communication loss and delay, respectively.Then, the optimization algorithm could find an appropriate combination of weight factors, which can help to select an appropriate path with a minimalGpi.


## 5. Routing Selecting Problem Solution through Modified Bellman–Ford Algorithm

In this section, we propose a modified Bellman–Ford algorithm to select the path with minimal training evaluation. Given a precise request, we can construct the routing graph with specific start bus nodes and destination nodes.When receiving a request, the controller can construct a routing graph, and, after analyzing the request, it will recognize the request bus nodeBe and the resource holder bus node Bs. To find the shortest route, the controller has to compute the length of each edge, Cpk. Recall that the nodes pair of this edge has three parameters: delay, packet loss, and path accessibility. Then, the length of an edge can be calculated via formula (1) after choosing a specific combination of weight of these three factors.The steps of the modified Bellman–Ford algorithm are described as follows:(1)
Initialize: find the ids and e of the resource holder node and resource subscriber node (s,e∈1,m). Set Di=−1, where Di represents the distance of Bs and Bi. Calculate each Cpk∈Cp according to formula (1) and the weight matrix of those three factors including packet loss, delivery delay, and path accessibility of routing path, but notice that the following constraints need to be satisfied: (a) Delayk is smaller than TD (threshold of delay); (b) Plossk is smaller than TP (threshold of packet delivery loss); (c) acck is smaller than TA (threshold of path accessibility).(2)
Optimize: traverse each edge, and setDi+1=minDi+1,Di+Cpi.(3)
Repeat step 2N−1 times, where N is the number of bus nodes.(4)
After finding the candidate path, check if the total delay of this route is smaller than the request live time. This should guarantee that the selected path is valid for the specific request.


## 6. Optimization Problem Solution Based on SPSO Algorithm

### 6.1. SPSO Algorithm

Particle swarm optimization (PSO) is a parallel population-based computation technique, which was motivated by the organism’s behavior such as schooling of fish and flocking of birds. In general, the PSO based route searching method gets optimal weights of the routing path matrix through multiple iterations and could be used to generate a quasi-static route. However, in BusNet, current routing selection is not exactly the same as the former times. That said, the selected routing path is nonpersistent, and it is changing with the network communication status or with time. Then, for a new service request, a lot of time has to be wasted to finish another round of training. As a result, PSO’s iteration optimization method could not be used directly in BusNet.However, the optimal routing path between the source bus node and destination bus node is relatively stable. Then, in this paper, a serial PSO algorithm (SPSO), which finds an optimal routing path according to recent searching results, incorporating the training process into every service request, is proposed. To be clearer, failing to use the past training result, PSO does several rounds of training for one request to find the best combination of weights. On the contrary, SPSO, taking advantage of the former training result, does training only once for each request. We can say that the request-response process is exactly our training process. A set of particles, each of which is denoted by a variable combination of weights, is used for training to avoid trapping in a local optimum.Here, we assume that each routing path searching process is triggered by a request message sent by a user node. A particle vector is defined as(7)V=V1,V2,…,Vk,Vi=Wpi,Wdi,Wai,where k is the particle’s number. Vi is the position of the ith particle, representing the weight matrix, our optimization targets. The moving trend of particles is denoted as(8)Δαit=0.3×Δαit−1+0.3×pBest−Vit−1+0.3×gBest−Vit−1,where Δαi is the moving direction of particle i, and t is the time moment of current searching progress, while t−1 is that of last searching progress. pBesti is the best position of particle i during last N searching progress. gBest is the best position of all particles during last N searching progress. The position updating process is expressed as(9)Vit=Vit−1+Δαit.The process of implementing the SPSO is described in Algorithm 2, while corresponding variables and functions definitions are explained in Table2.Algorithm 2: SPSO.
input: request, velocity, positionoutput: path(1)
if velocity = = null || position = = null then(2)
initializeParticle ()(3)
end if(4)
p [i] ⟵ getPresentParticle ()(5)
path ⟵ getMinTrainingEvaluationPath (request,p [i])(6)
[Gpi loss delay] ⟵ getGeneralizationEvaluation (path)(7)
update_pBest (Gpi)(8)
update_gBest (Gpi)(9)
fori = 0 ⟶ k − 1 do(10)
velocity [i] ⟵ updateVelocity (p [i])(11)
position [i] ⟵ updatePosition (p [i])(12)
end for(13)
return pathTable 2
Explanation of variables and functions in SPSO algorithm.
Variable/functionExplanationrequestRequest message includes the node id of request node and request content.velocityParticle’s velocity set.positionParticle’s position set, which corresponds to weight matrix.pathGenerated routing path of specific request.initialize ParticleParticle initialization.get Present ParticleGet particle of current request.get Min Training Evaluation Pathrequest,piSelect the path with minimal training evaluation based on this request and current weights of index.get Generalization EvaluationGet routing path generalization evaluations index.update_pBestGpiUpdatepBest according to current evaluation results.update_gBestGpiUpdategBest according to current evaluation results.update VelocitypiUpdate particle velocity according to (5).update PositionpiUpdate particle position according to (6).


### 6.2. Algorithm Complexity Analysis

The number of particles,K, will affect the update process of each particle, and the number of bus nodes and edges, N and E, will affect the shortest path algorithm complexity. Generally, the most time-consuming part should be the iterating process of the optimization algorithm. Nevertheless, the SPSO algorithm puts iteration into every request, which guarantees that the particles will update only once while the algorithm runs. In other words, the complexity of the iterative process is OK. As a result, the most time-consuming task is the shortest path algorithm, and the complexity is ONE. Then, the complexity of the SPSO algorithm is ONE+K. Considering that the number of particles is usually far less than the number of bus nodes, we can regard the complexity as ONE.


## 6.1. SPSO Algorithm

Particle swarm optimization (PSO) is a parallel population-based computation technique, which was motivated by the organism’s behavior such as schooling of fish and flocking of birds. In general, the PSO based route searching method gets optimal weights of the routing path matrix through multiple iterations and could be used to generate a quasi-static route. However, in BusNet, current routing selection is not exactly the same as the former times. That said, the selected routing path is nonpersistent, and it is changing with the network communication status or with time. Then, for a new service request, a lot of time has to be wasted to finish another round of training. As a result, PSO’s iteration optimization method could not be used directly in BusNet.However, the optimal routing path between the source bus node and destination bus node is relatively stable. Then, in this paper, a serial PSO algorithm (SPSO), which finds an optimal routing path according to recent searching results, incorporating the training process into every service request, is proposed. To be clearer, failing to use the past training result, PSO does several rounds of training for one request to find the best combination of weights. On the contrary, SPSO, taking advantage of the former training result, does training only once for each request. We can say that the request-response process is exactly our training process. A set of particles, each of which is denoted by a variable combination of weights, is used for training to avoid trapping in a local optimum.Here, we assume that each routing path searching process is triggered by a request message sent by a user node. A particle vector is defined as(7)V=V1,V2,…,Vk,Vi=Wpi,Wdi,Wai,where k is the particle’s number. Vi is the position of the ith particle, representing the weight matrix, our optimization targets. The moving trend of particles is denoted as(8)Δαit=0.3×Δαit−1+0.3×pBest−Vit−1+0.3×gBest−Vit−1,where Δαi is the moving direction of particle i, and t is the time moment of current searching progress, while t−1 is that of last searching progress. pBesti is the best position of particle i during last N searching progress. gBest is the best position of all particles during last N searching progress. The position updating process is expressed as(9)Vit=Vit−1+Δαit.The process of implementing the SPSO is described in Algorithm 2, while corresponding variables and functions definitions are explained in Table2.Algorithm 2: SPSO.
input: request, velocity, positionoutput: path(1)
if velocity = = null || position = = null then(2)
initializeParticle ()(3)
end if(4)
p [i] ⟵ getPresentParticle ()(5)
path ⟵ getMinTrainingEvaluationPath (request,p [i])(6)
[Gpi loss delay] ⟵ getGeneralizationEvaluation (path)(7)
update_pBest (Gpi)(8)
update_gBest (Gpi)(9)
fori = 0 ⟶ k − 1 do(10)
velocity [i] ⟵ updateVelocity (p [i])(11)
position [i] ⟵ updatePosition (p [i])(12)
end for(13)
return pathTable 2
Explanation of variables and functions in SPSO algorithm.
Variable/functionExplanationrequestRequest message includes the node id of request node and request content.velocityParticle’s velocity set.positionParticle’s position set, which corresponds to weight matrix.pathGenerated routing path of specific request.initialize ParticleParticle initialization.get Present ParticleGet particle of current request.get Min Training Evaluation Pathrequest,piSelect the path with minimal training evaluation based on this request and current weights of index.get Generalization EvaluationGet routing path generalization evaluations index.update_pBestGpiUpdatepBest according to current evaluation results.update_gBestGpiUpdategBest according to current evaluation results.update VelocitypiUpdate particle velocity according to (5).update PositionpiUpdate particle position according to (6).


## 6.2. Algorithm Complexity Analysis

The number of particles,K, will affect the update process of each particle, and the number of bus nodes and edges, N and E, will affect the shortest path algorithm complexity. Generally, the most time-consuming part should be the iterating process of the optimization algorithm. Nevertheless, the SPSO algorithm puts iteration into every request, which guarantees that the particles will update only once while the algorithm runs. In other words, the complexity of the iterative process is OK. As a result, the most time-consuming task is the shortest path algorithm, and the complexity is ONE. Then, the complexity of the SPSO algorithm is ONE+K. Considering that the number of particles is usually far less than the number of bus nodes, we can regard the complexity as ONE.


## 7. Simulation Results Analysis

All simulations are done based on the NS3 platform, a professional communication simulation platform. The performance of the proposed SPSO algorithm is evaluated by delivery delay and packet loss:(1)
Delivery delay: average time interval at which a service message is sent from the source bus node to the user node(2)
Packet loss: number of packets received incorrectly from source bus node to the total number of data packets


### 7.1. Simulation Setup

Here, we define a simulation scenario, whose area is10km2, and assume that bus nodes are distributed uniformly in the objective area. Note that, here, RSU and BS play the same role in BusNet; hence, our simulation scenario includes only RSU, and then we assume the following:(1)
RSUs communicate with vehicle nodes (including bus node and user node) via LTE-V2X(2)
RSUs communicate with the SDN controller via EthernetDetail parameters are listed in Table3.Table 3
Parameters.
Variable/FunctionExplanationBus number60, 120, 240Bus direction0–360∘RSU number3, 6, 12Controller number1Cars number300, 400, 600V2V communication range200mService area10km2Bus distributionUniform distributionVelocity of buses5–10m/sRequest packets lifetime3sSimulation time80sScheduling period1sParticle number10Relaynodes number[3, 15]


### 7.2. Simulation Results

Simulation results are shown in Figures4 and 5.Figure 4
Delivery delay.Figure 5
Packet loss.As shown in Figures4 and 5, both delivery delay and packet loss increase with the increase of bus node number. Compared with literature’s routing algorithm RDH, which simply sets the weight of three factors as equal, the proposed SPSO algorithm can reduce both factors significantly. The reason is that SPSO owns the ability to judge the combination of the weights and then adapt them to the current network status. Specially, we can notice that the more the number of bus nodes is, the more obvious the performance improvement will be. That is because as the requests get more frequent, the controller is more likely to learn more about the status in the current communication environment and can modify the combination of the weights timely, thereby performing better. To be much clearer, SPSO is a serial algorithm which means that it can only handle the requests one by one, and that is why we put 10 particles here. When the requests pour in, each particle can iterate several times in a short time. As a result, the combinations of weights are more likely to catch up with the change of network status.The optimization progress of the case with 240 bus nodes is shown in Figures6 and 7.Figure 6
Delivery delay.Figure 7
Packet loss.As mentioned earlier, the SPSO algorithm fulfills routing path optimization based on recent searching results. The result is coming from the requests from all the cars or users. Since the algorithm focuses on the global network status, it is useless to follow a specific user and analyze it. According to Figures6 and 7, we can derive two implications:(1)
When the number of searching times is less than 30, both delivery delay and packet loss curve of SPSO coincide with that of the routing algorithm in [14]. That said, the sample size of recent search records is not enough to support the optimization process and the weights factors remain the same as the initial values.(2)
When the number of searching times is large than 30, the delivery delay and packet loss values of SPOS are obviously lower than that of the routing algorithm in [14]. That being said, the positions of the particles, also named the combinations of weights, are dynamically and persistently changed with network status.Hence, we believe that the proposed SPSO algorithm will converge fast and find optimal weight factors, thus improving user experience.


## 7.1. Simulation Setup

Here, we define a simulation scenario, whose area is10km2, and assume that bus nodes are distributed uniformly in the objective area. Note that, here, RSU and BS play the same role in BusNet; hence, our simulation scenario includes only RSU, and then we assume the following:(1)
RSUs communicate with vehicle nodes (including bus node and user node) via LTE-V2X(2)
RSUs communicate with the SDN controller via EthernetDetail parameters are listed in Table3.Table 3
Parameters.
Variable/FunctionExplanationBus number60, 120, 240Bus direction0–360∘RSU number3, 6, 12Controller number1Cars number300, 400, 600V2V communication range200mService area10km2Bus distributionUniform distributionVelocity of buses5–10m/sRequest packets lifetime3sSimulation time80sScheduling period1sParticle number10Relaynodes number[3, 15]


## 7.2. Simulation Results

Simulation results are shown in Figures4 and 5.Figure 4
Delivery delay.Figure 5
Packet loss.As shown in Figures4 and 5, both delivery delay and packet loss increase with the increase of bus node number. Compared with literature’s routing algorithm RDH, which simply sets the weight of three factors as equal, the proposed SPSO algorithm can reduce both factors significantly. The reason is that SPSO owns the ability to judge the combination of the weights and then adapt them to the current network status. Specially, we can notice that the more the number of bus nodes is, the more obvious the performance improvement will be. That is because as the requests get more frequent, the controller is more likely to learn more about the status in the current communication environment and can modify the combination of the weights timely, thereby performing better. To be much clearer, SPSO is a serial algorithm which means that it can only handle the requests one by one, and that is why we put 10 particles here. When the requests pour in, each particle can iterate several times in a short time. As a result, the combinations of weights are more likely to catch up with the change of network status.The optimization progress of the case with 240 bus nodes is shown in Figures6 and 7.Figure 6
Delivery delay.Figure 7
Packet loss.As mentioned earlier, the SPSO algorithm fulfills routing path optimization based on recent searching results. The result is coming from the requests from all the cars or users. Since the algorithm focuses on the global network status, it is useless to follow a specific user and analyze it. According to Figures6 and 7, we can derive two implications:(1)
When the number of searching times is less than 30, both delivery delay and packet loss curve of SPSO coincide with that of the routing algorithm in [14]. That said, the sample size of recent search records is not enough to support the optimization process and the weights factors remain the same as the initial values.(2)
When the number of searching times is large than 30, the delivery delay and packet loss values of SPOS are obviously lower than that of the routing algorithm in [14]. That being said, the positions of the particles, also named the combinations of weights, are dynamically and persistently changed with network status.Hence, we believe that the proposed SPSO algorithm will converge fast and find optimal weight factors, thus improving user experience.


## 8. Conclusion and Future Work

There is no doubt that routing efficiency is an important topic for most of the wireless networks. As mentioned in Section3, the particularity of BusNet brings a great challenge to realize routing optimization. Most of mesh network-oriented routing algorithms cannot be applied to BusNet due to its dynamic feature. In this paper, we define a routing path evaluation factor, which employs a weight matric to adapt to the dynamic change of the network. On the other hand, to meet the service demand and solve the information dissemination problems, such as poor timeliness and low success rate, we propose a serial PSO algorithm, which finds optimal routing path according to recent searching results. Simulation results show that the proposed method could enhance system performance and communication efficiency.However, this paper just considers the case with only one SDN controller. Hence, in future work, we shall work on multiple-controller case. Moreover, in this paper, the user vehicle number is set as a fixed value implying that no car leaves or enters. In future work, we shall discuss the impact of the changing of the number of user vehicles.



---

*Source: 8856130-2020-09-22.xml*