The present invention is in " car networking community dynamic evolution method " filed in the inventors such as Cheng Jiujun on March 1st, 2019 (applicationPeople: Tongji University, number of patent application 201910155584 is 2)) the further research and development of earlier application patent document, it should beFirst patent document can be considered as a part of description of the invention.
Specific embodiment
Specific implementation process of the invention is as shown in figure 5, include following 6 aspects:
1. relevant nature defines
2. informational table of nodes initialization and update
3. community's head node screens
4. the message of ordinary node to head node forwards
5. the message of head node to ordinary node forwards
6. access routing algorithm in community
①
Relevant nature definition
For the node in car networking community, the access scheme that the present invention uses will assign different roles for it, be respectivelyCommunity's head node, community's gateway node and community's ordinary node, are defined as follows:
Define 1 community's cephalomere point set (CHSet): community CiHead node (CH) be the community in the biggish node of community's centripetal forceSet, if in community CiMeeting mathematic(al) representation there are node u is (1):
Wherein, η be head node selective factor B, general η take (0.75,1] in one value, community CiIn meet the section of above-mentioned conditionPoint u is added into CiCHSet in.Node in CHSet is existing community CiThe interior preferable node of communication quality, in communityThe node of CHSet is generally selected as relay node.
It defines 2 community's ordinary nodes (CM): all can be described as community's ordinary node in addition to head node in a community.
Generally, due to car networking is the network of high dynamic variation, the role of each node can with itself movement withTopology and signal intelligence variation and change, ordinary node, head node role may according to the demand of network-in-dialing andIt exchanges.
It defines 3 node connected probabilities (Node Connectivity Probability, NCP) and refers to that car networking interior joint is connected toCredibility.
If node u is adjacent with node v and in respective range for wireless communication, their direct connected probability (Direct NodeConnectivity Probability, DNCP) be mathematic(al) representation (2):
Wherein, dist (u, v) indicates that the distance between node u and v, TR indicate the maximum communication radius of node.When between nodeDistance when being greater than node maximum communication radius, the connected probability between node is 0；Otherwise, the connected probability meeting between nodeIncrease with the reduction of distance between node.
It, i.e., can be by other node configuration node communication paths, if this path between node u and v if two node indirect communicationsIt is expressed as NodePathi={ e1,e2,…,en, wherein e1=u, en=v, n > 2, n indicate the quantity of node on the access, thenNode u and v are in NodePathiOn node connected probability (Path Node Connectivity Probability, PNCP)It is:
That is direct the tired of node connected probability of u and v communication path multiplies.Since there may be a plurality of node access between u and vDiameter, between definition node u and v indirect inode connected probability (Indirect Node Connectivity Probability,INCP) be connected probability on all node communication paths maximum value:
INCP (u, v)=max (PNCP (NodePathi)) (4)
To sum up, the node connected probability between definition node of the present invention is the maximum value in DNCP and INCP:
NCP (u, v)=max (DNCP (u, v), INCP (u, v)) (5)
②
Informational table of nodes initialization and update
In the Web communication layer of car networking, there is an informational table of nodes on each node, the field which includes includes sectionPoint self ID, current time, speed, acceleration, position longitude and latitude, community's ownership, node role, affiliated community's head node IDAnd ID of gateway node etc..It is specific as shown in table 1.
In table 1, node ID is the unique identification of the node in car networking, if for RSU be to be determined by the type of node itself,Timestamp represents current time, and the nodes such as speed, acceleration and longitude and latitude essential information can be obtained by sensor.For sectionPoint community ownership, calculating process are as follows: initial time, each node need the node broadcasts into its radio signal propagationNeighbor node probe messages (Neighbor node detection message, NNDM), the node for receiving NNDM needs to replyConfirmation message may determine that node and neighbor node with the presence or absence of side, thus come apparent neighbor information and net by this processNetwork topological structure.Hereafter, using car networking community dynamic evolution method, (this part invention see (inventors such as Cheng Jiujun in" car networking community dynamic evolution method " (applicant: Tongji University, number of patent application filed on March 1st, 20192019101555842)), come determine node community belong to.It not only include the essential information of node itself, also in NNDM messageNode adjacency table (Node Adjacency List, NAL) including community where the node, NAL is a two-dimensional array.IfCommunity CiNode number is m, its NAL are as follows:
Wherein, neip,qCommunity C is indicated when=0iIn node vpWith vqBetween side is not present, it is on the contrary then indicate vpWith vqIt is directConnected probability.In community's merger process based on node similarity and the evolutionary process based on increment, exchanged between nodeNAL, so that each node both knows about the node adjacency information of itself affiliated community.
After the community structure at current time determines, community's adjacency list of each community (Community Adjacency List,CAL), i.e. the adjoining community information of community can be obtained the broadcast mode of node adjacency table and obtained by similar.
③
The screening of community's head node
After the community structure at current time determines, community's adjacency list of each community (Community Adjacency List,CAL), i.e. the adjoining community information of community can be obtained the broadcast mode of node adjacency table and obtained by similar.Community's head nodeScreening can refer to and define 1 content and realize that for specific steps as shown in algorithm 1, specific flow chart is as shown in Figure 1.
By the step in algorithm 1, the head node of community will be screened out, and the content of CHSet is stored in eachIn the informational table of nodes of node, the foundation for subsequent access routing provides information support.
④
The message of ordinary node to head node forwards
Communicated between community's interior nodes biggish for car networking, if destination node in the direct communications range of source node, rootCommunication is directly established according to the information in adjacency list.If destination node is not in the direct communications range of source node, in order to realize societyThe overall order of intra-area communication is with access, it is specified that ordinary node must first select the forwarding of a certain head node into CHSet to disappearBreath.In above-mentioned selection course, each ordinary node in community has one group of forwarding behavior probability vector table.Such as node viForwarding behavior probability vector table it is as shown in table 2:
In table 2, every a line indicates ordinary node viForwarding behavior probability vector.Forward probability P FrIt is meant that for oneA forwarding event, i.e. viNeed the v to same communitypWhen sending information, select head node for vchsAnd next-hop node is vnextq'sProbability.
⑤
The message of head node to ordinary node forwards
After ordinary node forwards the message on head node, head node needs a plurality of routing to ordinary node safeguarded from itIt is middle to select optimal one.It is similar with the selection course in " message of ordinary node to head node forwards ", on community's head nodeAlso there is one group of forwarding behavior vector table.Such as head node vchrCommunity in forwarding behavior probability vector table it is as shown in table 3.
Similarly, in table 3, every a line indicates head node vchsForwarding behavior probability vector.PFrIndicate vchsTo same communityNode vpWhen sending information, next-hop node vnextqProbability.
The network under high dynamic change condition in order to guarantee car networking network topology is access, and forwarding behavior above-mentioned is generalForwarding probability P F in rate vector can be with the progress of communication and dynamic changes, and the process of change will commonly be tied by being deployed in communityThe feedback mechanism of learning automaton (LA) determines on point or community's head node.
⑥
Access routing algorithm in community
In order to quantify environment to the feedback of LA, the present invention is by NCP, residue energy of node ratio (Rest Energy Rate, RER)And the main indicator that data delay (Delay) is inputted as LA.Here, the definition of RER and Delay such as formula (7) and (8) instituteShow.
Node R ER indicates that node can continue the traffic load of carrying and the ratio of maximum communication load:
Wherein, EA indicates the load of node maximum communication, and EU indicates the traffic load that node has occupied.
Time delay on this node caused by Delay on node is indicated because of data processing:
Wherein, TreceiveIndicate node viReceive timestamp when data packet, TACKIndicate node viForward data packet whenBetween stab.
Relative distance of the NCP mainly between node is related, and RER is that node can continue to forward the guarantee of data, and Delay is then nodeBetween communication delay historical information description.In summary three aspect factor defines a new scale chance and forwards evaluation factors(Opportunity to Forward Evaluation,OFE)
OFE=f (NCP, RER, Delay) (9)
That is OFE is the function of NCP, RER and Delay.
For ordinary node viTo community head node vchrAnd next-hop is vnextqForwarding behavior, have:
η、It is the adjustment factor of NCP, RER and Delay respectively with ψ.
For community head node vchsTo destination node vpAnd next-hop node is vnextqForwarding behavior, have:
Similarly, η ',It is also the adjustment factor of NCP, RER and Delay respectively with ψ '.
It is deployed in the forwarding behavior vector that LA is forwarded in the community on car networking community node u (ordinary node or community's head node)Number is set as r, and LA forwarding probability is initialized as:
That is each forwarding behavior probability on t=0 moment LA is identical.In following instant, LA cannot be immediately obtained current timeNCP, RER and Delay value, and these data of previous moment are obtainable.Therefore, i-th of forwarding row is selected in t momentFor OFEiEvaluation factors OFE is forwarded with the mean chance on the LAavgCompare, if OFEi≥OFEavg, then LA makes this behaviorExcitation movement:
If OFEi≤OFEavg, then LA makes punishment movement to this behavior:
Wherein, λ is excitation parameters, and λ ' is punishment parameter.
In conclusion interior nodes LA forwarding behavior probability in community adjusts specific steps as shown in algorithm 2, specific flow chart such as Fig. 2It is shown.
On the basis of interior nodes LA forwards behavior probability adjustment algorithm 2 in community, access method for routing in community will be obtained, in detailFor thin step as shown in algorithm 3, specific flow chart is as shown in Figure 3.It is directly logical if destination node is in the communication range of source nodeLetter, otherwise, message transmission will be undergone from source node to community's head node again to two stages of destination node.In addition, in order to anti-The case where endless loop or information drop-out are only fallen into message transmission is, it is specified that the maximum hop count value of forwarding of above-mentioned two stage isHOPmaxIf jumping figure value K is more than HOPmax, source node or head node will forward again.
For car networking community, the LA disposed on ordinary node be by adjusting forwarding behavior probability vector in forwarding probability,To find that connected probability is larger, remaining load is more and the lesser head node of delay and towards under the path of the head node oneIt jumps；The LA disposed on head node is to lead to target section by adjusting the forwarding probability in forwarding behavior probability vector to findThe suitable path of point.These LA can be exchanged with each other data and competition in a network.Shown in specific such as Fig. 4 (a) and (b).
In Fig. 4, (a) indicates what the CHSet of car networking community was made of vehicle node, and (b) indicates car networking communityCHSet not only has vehicle node, and there are also RSU to serve as head node.Due to the communication capacity of the more general vehicular communication equipment of RSU nodeIt is much bigger, it is screened through head node in algorithm 1, if containing RSU node in car networking community, RSU node serves as community's cephalomereThe probability of point or gateway node is very big, and experimentation through the invention demonstrates above content.
Innovative point
Innovative point: being based on car networking community dynamic evolution method, (" vehicle filed in the inventors such as Cheng Jiujun on March 1st, 2019Connected community's dynamic evolution method " (applicant: Tongji University, number of patent application 2019101555842)), it is automatic using studyCorresponding excitation function and penalty is arranged by the information exchange and competition being deployed between community's node in machine technology, adaptiveThe forwarding probability that different routings should be adjusted reaches Nash Equilibrium state, realizes that car networking community is connected to and stablizes.
In car networking vehicle node fast move with car networking network topology high dynamic change, car networking easily occurs data aggregation andPhenomena such as delay, to largely give car networking network-in-dialing and stabilized zone next huge challenge.Therefore, it analyzes and understandsIt is a urgent problem in the current sensible Journal of Sex Research of car networking network that car networking community, which is connected to and stablizes,.The present invention will learnIt practises automaton theory and is applied to car networking community, information exchange and competition between the learning automaton by being deployed in community's node,The forwarding probability of different routings is adaptively adjusted, to achieve the purpose that optimize network communication on the whole, promotes car networking netNetwork is access.
Specification subordinate list
Table 1
Table 2
Table 3