of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
112 JOURNAL OF NETWORKS, VOL. 6, NO. 1, JANUARY 2011 A Novel Position-based Multi-hop Broadcast Protocol for Vehicular Ad Hoc Networks Xuewen Wu College of Computer and Information, Hohai University, Nanjing, China Email: Shiming Song College of Computer and Information, Hohai University, Nanjing, China Email: Huibin Wang College of Computer and Information, Hohai University, Nanjing, China Email: Abstract—Vehicular Ad Hoc Networks (VANETs
Document Share
Document Tags
Document Transcript
  A Novel Position-based Multi-hop BroadcastProtocol for Vehicular Ad Hoc Networks   Xuewen Wu College of Computer and Information, Hohai University, Nanjing, ChinaEmail: Shiming Song College of Computer and Information, Hohai University, Nanjing, ChinaEmail: Huibin Wang College of Computer and Information, Hohai University, Nanjing, ChinaEmail:  Abstract —Vehicular Ad Hoc Networks (VANETs) areconsidered as a promising scheme to actively guarantee  vehicle safety, and broadcast is a key technology forwarning message dissemination in VANETs. This paperproposes a novel Position-based Multi-hop Broadcast(PMB) protocol for VANETs in view of some shortcomingsof existing broadcast protocols for VANETs, such asignoring the differences of transmission range amongdifferent nodes (vehicles), and disseminating warningmessages only with the help of nodes in the one-way lane,PMB calculates waiting time to select the rebroadcast nodesbased on additional coverage area of adjacent nodesconsidering the transmission ranges of nodes together withthe inter-vehicle spacing, to guarantee less nodes used torebroadcast warning packets. Besides, it guarantees thereliability of warning message dissemination by adoptingthe alternative answering mechanism named implicit ACKand explicit ACK adaptively and rebroadcast packets basedon nodes in the two-way lane. The simulation results showthat PMB outperforms existing broadcast protocols forwarning message dissemination in VANETs in terms of suppression of broadcast redundancy, real-timeperformance and reliability even if all nodes have differenttransmission ranges.  Index Terms — Broadcast Protocol, Position-based Scheme,Transmission Range, Vehicular Ad Hoc Networks,Warning Message Dissemination I.   I NTRODUCTION  Vehicular Ad Hoc Networks (VANETs) dedicated toWireless vehicle communications are considered as anoff-shoot of Mobile Ad hoc Networks (MANETs) [1].VANETs have two kinds of communication methods , namely Inter-Vehicle Communications (IVC) andRoadside-to-Vehicle Communications (RVC). IVCprovide direct exchange of information between nodes(vehicles), and are mainly used to achieve warningmessage dissemination for vehicle collision accident,cooperative driving and real-time traffic informationdissemination. RVC can access other networks (e.g.Internet) for more information sharing via the pre-existingroadside infrastructure resulting in providing comfortabletravel for passengers. Unlike other traditional passivesafety protection technology such as the use of air bags,seat belts, automatic braking system and brake lamps,VANETs can provide active vehicle collision warning viaIVC to make drivers have enough reaction time forbraking in advance to eliminate safety hazards, and as aresult VANETs can significantly prevent or reduce trafficaccidents, IVC are considered as the most effectivecommunication methods for vehicle collision warning onbehalf of VANET safety applications.Broadcast is the most widely used technology forwarning message dissemination in vehicle collisionavoidance applications. Whether VANETs can effectivelyavoid or reduce vehicle collision directly depends on theability to quickly and reliably broadcast warning packetsto the rear vehicles for proactive warning, therefore, thedesign of broadcast protocols supporting VANET safetyapplications is crucial for warning message dissemination.   However, Compared to MANETs, VANETs have someunique features, such as node mobility restricted by theroad, fast-changing network topology due to high-speedmoving of nodes [2], as a result directly applyingtraditional broadcast protocols for Ad Hoc networks toVANETs would make protocol performances degraded orcannot even work correctly. Designing efficient broadcastprotocols specifically for VANETs is very essential.II.   R ELATED W ORK  Researchers have been proposed various broadcastprotocols for message dissemination as yet. The existingbroadcast protocols were classified into categories asfollow: Flooding-based scheme : A source node broadcasts apacket and all of its neighbors will rebroadcast the packetas soon as they receive it. This scheme is relativelysimple and not subject to network topology, especiallysuitable for the scenarios of high-speed mobile nodeswhere the network topology changes frequently.However, because each node in the rear of the source 112JOURNAL OF NETWORKS, VOL. 6, NO. 1, JANUARY 2011© 2011 ACADEMY PUBLISHER doi:10.4304/jnw.6.1.112-120  node will rebroadcast packets, as the network nodedensity increases, it will bring well-known broadcaststorms problem [3]. NB [4] and OZF [5] are typical of flooding-based broadcast protocols. I-BIA protocol [6]makes improvements to NB, it reduces redundant packetrebroadcasting by means of the implicit ACK mechanism,but its rebroadcast nodes are randomly selected, if two-hop adjacent rebroadcast nodes are close to eachother, real-time message dissemination will not beguaranteed. Probability-based scheme: Compared with theflooding-based scheme, probability-based scheme enablesrebroadcast nodes to broadcast received packets withprobability p, where p is usually calculated by currentreceiving nodes based on the ratio of the distance fromthem to the previous-hop rebroadcast node and theirtransmission range. In such scheme, the receiving nodefarthest away from the previous-hop rebroadcast nodewithin one-hop range is most likely to become arebroadcast node. Typical representatives of such schemeinclude Wp-PB [5], FDPD [7], p-IVG [8], NPPB [9] etc.,they are essentially of no difference, but differ from eachother only in some details, such as the calculation of probability p. However, probability-based mechanismshave an inherent shortcoming that it is still possible fornodes with the litter and the greater probability torebroadcast packets simultaneously, resulting in highredundancy of packet broadcasting. Counter-based   scheme: it implies that the moreduplicated packets a node receives in RandomAssessment Delay (RAD) which is randomly chosenbetween 0 and a maximum delay value, the less chancesthe node has to become a rebroadcast node, but thecounter threshold of this scheme is usually fixed andcannot be dynamically adjusted to adapt to changes of node density. DBCG [9] is a typical example of thisscheme, where RAD is inversely proportional tointer-node distance. Distance-based scheme: nodes always obtain theposition information of vehicle with the help of GPSdevice, and they make decisions for packetrebroadcasting based on inter-node distance. Within aRAD, if a node receives packets from at least one node ina place to which the distance is less than distancethreshold from the previous hop node, it will give uprebroadcasting packets after a random waiting time[11][12]. Similarly to Counter-based scheme, it is verydifficult to determinate the distance threshold, and cannotbe dynamically adjusted to adapt to changes of local nodedensity. Neighbor knowledge scheme: It needs nodes tomaintain and update the neighbor node information withthe help of periodic broadcasting of “Hello” packets(which include neighbor node information and itself).Nodes determine whether to broadcast packets based onthese neighbor knowledge maintained by themselves.Flooding with Self Pruning [13], Dominant Pruning [13],AHBP [14], CDS-Based Broadcast [15], LENWB [16],INK [17] and GPCR [18] are typical examples of thisscheme. Such scheme has better performance in the staticor other networks with slow-changing network topologies,but it is not suitable for VANETs whose topologies arefast changing. Because nodes in VANETs need toexchange neighbor information more frequently, morepacket collisions are brought out deteriorating thenetwork performance.   Cluster-based scheme:   the nodes in one network aredivided into several clusters and each cluster has one head node.Only cluster heads will broadcast packets to their neighborswithin cluster, and gateway nodes are responsible forinter-cluster packet broadcasting, while other number nodesonly need to receive packets [18]. Wei Lou et al. [19] proposedtwo cluster-based backbone infrastructures respectively basedon Source-Independent and Source-Dependent ConnectedDominating Sets (SI-CDS and SD-CDS) for broadcasting.These backbones infrastructures only require few cluster headsand gateway nodes to rebroadcast packets reducing broadcastredundancy. Fan P [20] proposed a cluster-based broadcastingscheme that provides an efficient and stable hierarchicalnetwork backbone , and make cluster heads and some selectedgateway nodes rebroadcast packets to reduce the redundantretransmissions. it decreases the overhead required to maintainnetwork topology due to high mobility based on Lowest-IDalgorithm by incorporating moving direction information andleadership duration. But the cluster-based scheme can lead toreduced performance level if there are increasing controlmessage exchanges between the nodes for the formation andmaintenance of cluster. Position-based scheme : Similarly to distance-basedscheme, it does not need to rely on the network topologyinformation, and especially suitable for VANETs whosetopologies are fast-changing . This scheme is based onadditional coverage of two-hop adjacent nodes, withinone-hop range; the neighbor node farthest from theprevious-hop broadcast node has the largest additionalcoverage, and will become a rebroadcast node. Therebroadcast node for each hop is selected determinatelyand uniquely, differing from other broadcast schemessuch as flooding-based, probability-based, andcounter-based distance-based schemes which may causemultiple nodes broadcasting at the same time, therefore,the position-based scheme has lower broadcastredundancy relatively. At present, most of VANETbroadcast protocols are usually position-based protocols,e.g. S1-PB [5], PAB [21], ODAM [22], SNB [23], EDB[24] and RBRS [25] etc..All the schemes above assume that all nodes in anetwork have the same transmission range, but it is notalways true in the real world. Different vendors ordifferent types of vehicles may be equipped with wirelesscommunication devices with different transmissionranges, and different transmission ranges will lead to theunidirectional link, thereby resulting in a lot of unnecessary packet retransmissions. Besides, variousexisting broadcast protocols simply use rebroadcast nodesin one-way lane to rebroadcast packets, while packetrebroadcasting based on two-way lane can overcome theproblem of connectivity gaps which always appear in thesparse traffic scenarios [15]. In view of theseshortcomings, in this paper, we propose a novelPosition-based Multi-hop Broadcast (PMB)   protocol derivingfrom the position-based scheme considering the fact thatnodes in a network have different transmission ranges forVANETs. The simulation results show that even in thecase of different transmission ranges for different nodes,PMB can significantly bring lower broadcast redundancyso as to improve broadcast efficiency, and guaranteesbetter real-time performance and reliability of warningmessage dissemination.The rest of the paper is organized as follow: in section JOURNAL OF NETWORKS, VOL. 6, NO. 1, JANUARY 2011113© 2011 ACADEMY PUBLISHER   III the proposed protocol called PMB is described indetail. In section IV we evaluate the performance of PMBtogether with other protocols using Network simulatorVersion 2 (NS2). Finally, we conclude in section V.III.   P ROPOSED P ROTOCOL  In designing PMB, we make the following assumptions:(1) Each node is aware of its geographical position bymeans of GPS device; (2) All nodes have the samereceiving sensitivity, but they have different transmissionpower, therefore, there will have different transmissionranges; (3) Nodes are equipped with omni-directionalantennas.PMB uses timer-based method to select rebroadcastnodes and its waiting time is inversely proportional toAdditional Coverage Area (ACA). A node with thelargest ACA has the shortest waiting time, so it willbecome a rebroadcast node in the competition with othernodes, and other nodes will stop timer to give up packetrebroadcasting when they receive a duplicated packetfrom the rebroadcast node, therefore fewer nodes areselected as rebroadcast nodes to be responsible for packetbroadcasting of the rear warning zone, thereby reducingbroadcast redundancy and end-to-end delay. In addition,according to the relationship between the transmissionrange of current receiving node and the distance from thecurrent receiving node to the previous rebroadcast node,PMB adopts the implicit and the explicit ACK answeringmechanisms adaptively, and rebroadcasts packets with thehelp of nodes in two-way lane so as to guarantee thereliability of warning message dissemination. In messagedissemination, PMB also restricts both the coverage of message dissemination and the remaining valid times of nodes reasonably to bring high efficiency of messagedissemination.  A.   Selection of the Rebroadcast Node Suppose node  j denotes the current receiving node in alane, and node i denotes the previous-hop broadcast node.The ACA of node  j is denoted as  ACA ij , and it is definedby the expression  ACA ij   = S  j - S i ∩  j , where S  j is the signalcoverage area of node  j , and S i ∩  j   is the overlappingcoverage area of node i and  j . Considering thetransmission range of node is usually far greater than thewidth of lane, as for the signal coverage area, only thecovered part over the lane is considered, and the ACA isillustrated in Fig. 1. ij ACA   Figure 1 The ACA of node  j Thus, (1) will be simplified as follows: ( ) ijjijjroadiijroad   ACASSRWRdW  ∩ = − = ⋅ − − ⋅   ( ) road  W d  R R iji j ⋅+−= (1)Where  R i and  R  j denote the transmission ranges of node i and  j respectively, d  ij denotes the d istance between node  i and  j , and W  road    denotes the width of the two-way lane.The preset waiting time of rebroadcast node is defined asfollows:   1 max ijdeferrand max  ACATTT  ACA α  ⎛ ⎞= ⋅ − ⋅ +⎜ ⎟⎜ ⎟⎝ ⎠ (2)Where T  max is the (assumed) maximum waiting timedefined by PMB (for PMB, T  max =100ms), and  ACA max isthe upper limit of ACA achieved only when node  j hasthe largest transmission range at the edge of coveragearea of node i . In order to make the node that would mostlikely become a rebroadcast node further reduce thewaiting time, multiplier factor α    is used and defined asfollows: 11 exp ijmax  ACA ACA α λ  ⎛ ⎞⎛ ⎞= − − ⋅ −⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠ (3)Where   λ  >0 ( λ    is a constant), and evolutions show thebest performance of PMB occurs when λ  =15. In addition,in order to prevent nodes with the same ACArebroadcasting packets simultaneously to bring morepacket collisions, a random short delay T  rand  , which israndomly chosen from the uniform distribution over theinterval [- C   /2, C   /2], is added to T  deffer  , where C  is thenumber of lanes. Noting the equation  ACA max =  R max ⋅  W  road  ,the following expression is inferred from (1) and (2): maxmax 1  jiijdeferrand   RRd TTT  R α  − +⎛ ⎞= ⋅ − ⋅ +⎜ ⎟⎝ ⎠ (4) Where we have max 1exp1  jiij  RRd  R α λ  ⎛ ⎞− +⎛ ⎞= − − ⋅ −⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠ (5)From (4), we can conclude that for all neighbor nodesof node i within one-hop, a neighbor node with largertransmission range and farther from node i is more likelyto become a rebroadcast node, thereby usually resulting inonly one neighbor node selected as a rebroadcast nodewithin one-hop to be responsible for packetrebroadcasting. Therefore, in other words, the least hopsare required to broadcast packets throughout the rearwarning area, thereby reducing the delay of messagedissemination.  B.    Reliability of the Proposed Protocol As for satety applications of VANETs, it is asimportant as the real-time performance to guarantee thereliability of warning message dissemination. In the paper,the following two answering mechanisms forbroadcasting are used, for convenience, we assume CRNis the current rebroadcast node selected in competition,PRN is the previous rebroadcast node, the transmissionranges of PRN and CRN are denoted by  R  p and  R c  respectively, and d  is the distance between PRN andCRN.1)   The implicit ACK and the explicit ACK: When thefront node detects the emergency such as vehicle collisionaccident, it will immediately generate and broadcastwarning messages to its rear zone per 1 second. Eachnode in the rear of the emergency source node adds itsown position and velocity vector information to thepacket header before rebroadcasting. In packetbroadcasting, packets permanently contain some 114JOURNAL OF NETWORKS, VOL. 6, NO. 1, JANUARY 2011 © 2011 ACADEMY PUBLISHER   important information, namely the indentifier, position,and velocity vector of emergency source node, they canuniquely identify where the current emergency occurs,When CRN receives a broadcast packet from PRN, it willdetermine whether PRN is in its own transmission rangebased on the position information of PRN in the packetheader, and determine whether PRN is moving in thesame direction as itself based on the angle between thevelocity vector of PRN and that of itself.If PRN is in the transmission range of CRN as shownin Fig. 2 (where d  ≤   R c ), PRN and CRN can communicatewith each other, the implicit ACK mechanism is adaptedby PMB at the moment, that is, CRN retransmits the justreceived packet to PRN. As for PRN, successful receptionof packet indicates that the packet from PRN has alreadybeen received and rebroadcasted by some rear nodes, andPRN will stop the rebroadcast timer so as not torebroadcast this packet. Otherwise, CRN cannotcommunicate with the PRN directly as shown in Fig. 3(where d  >  R c ). Even if CRN rebroadcasts ACK packet,PRN cannot be informed, so ACK packet has to beretransmitted to PRN with the help of the intermediatenodes between CRN and PRN. This process is theso-called explicit ACK mechanism. Figure 2 Implicit ACK mechanismFigure 3. Explicit ACK mechanism If  d  >  R c, CRN will add the ACK transmission flag intopacket header before packet rebroadcasting. The momentthat the intermediate node receives the warning messagepacket from CRN, its will immediately stop its waitingtimer, and consequently determine whether to transmitACK packet to PRN according to the ACK transmissionflag in packet header. If desired, and PRN is within thescope of its radiation, the intermediate node will wait fora period of time randomly chosen from a limited timeinterval to compete with other intermediate nodes fortransmitting the ACK packet, the implementation processis described in detail as follows:Firstly, the (assumed) maximum waiting time T   Ack_max  for ACK packet transmission is equally divided into  N  TimeSlice slots, and the length of each slot is defined as theexpression  L TimeSlice = T   Ack_max  /   N  TimeSlice , consequently, the idx -th slot time will be randomly chosen from a uniformdistribution over the interval [0,  N  TimeSlice -1], and then anoffset denoted by T  offset  within the interval [0,  L TimeSilce ]will be randomly determined from a uniform distribution.Finally, we have the waiting time T   Ack  calculated asfollows: T   Ack  = idx ⋅  L TimeSlice + T  offset  (6)After the two random choices, the waiting time of theintermediate node that competes for ACK packettransmission is greatly discretized, thereby preventingmultiple nodes transmitting ACK packets at the sametime effectively. The intermediate node with the shortestwaiting time will be chosen to generate and transmit ACKpacket to PRN immediately. ACK packet includes theidentifier of emergency source node and the sequencenumber of the warning packet which uniquely identify thewarning message. In addition, two identifiers of PRN andCRN are also included in ACK packet, where the identifier of PRN is used for ACK packet transmission asa destination address. PRN will stop rebroadcast timer assoon as receiving this explicit ACK packet, and give uppacket broadcasting.2)   Packet rebroadcasting based on the two-way lane: When the distance between PRN and its rear nodes isgreater than the transmission range of PRN, packetdelivery will be interrupted, which is well-knownconnectivity gap problem [26] as illustrated in Fig. 4(a).PRN will rebroadcast packets until at least one rearvehicle node drives into its scope of radiation or thepacket is expired. If packet broadcasting is realized onlybased on the vehicle nodes in one-way lane, the speeddifference between vehicles is too little to eliminate theconnectivity gaps in a short time, while PMB uses thetwo-way lane mode as shown in Fig. 4(b), it can eliminatethe connectivity gaps rapidly with the help of packetrebroadcasting of intermediate nodes located in theopposite lane, resulting in successful packet reception forthe rear nodes.  R  p PRNPRN  R  p CRNCRN (a) Emergence of connectivity gap (b) Elimination of connectivity gap Figure 4 Connectivity gap problem in the lane In PMB, if the intermediate nodes find that theremaining valid times of the just received packets are stillgreater than the one-hop propagation delay, they willresume packet rebroadcasting to disseminate warningmessages to the rear zone, thus guaranteeing thereliability and real-time performance of the messagedissemination. Even in the dense traffic scenarios of VANETs, a rear vehicle node in the same lane is morelikely to become a CRN due to long distance from PRN,and the intermediate node located in the opposite lanebetween PRN and CRN will give up packet broadcastingas soon as it receives the duplicated packet from CRN, soit will not bring too much packet collisions. C.    Restrictions of Message Dissemination Noting that the emergency warning process by meansof warning messages has the inherent properties of regionand time in the real world, PMB considers the restrictions JOURNAL OF NETWORKS, VOL. 6, NO. 1, JANUARY 2011115© 2011 ACADEMY PUBLISHER 
Similar documents
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!