楊　瓊　邢　松　夏瑋瑋　沈連豐

(1東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京　210096)(2加利福尼亞州立大學(xué)信息系統(tǒng)系，美國(guó)洛杉磯　90032)

?

一種基于MAC層時(shí)延上限的VANET自適應(yīng)分簇算法

楊瓊1邢松2夏瑋瑋1沈連豐1

(1東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京210096)
(2加利福尼亞州立大學(xué)信息系統(tǒng)系，美國(guó)洛杉磯90032)

摘要:為提高車輛自組織網(wǎng)絡(luò)(VANET)中媒體接入控制(MAC)協(xié)議在車輛密集情況下的性能，提出了一種基于MAC層時(shí)延上限的自適應(yīng)(MDBA)分簇算法，該算法包括簇頭選舉算法和簇維護(hù)算法．在MAC層消息傳輸?shù)臅r(shí)延上限制約下，簇頭選舉算法通過綜合考慮車輛節(jié)點(diǎn)的速度、加速度、位置和目的地4種因素來(lái)選取簇頭;針對(duì)網(wǎng)絡(luò)拓?fù)涞淖兓鼐S護(hù)算法對(duì)分簇進(jìn)行自適應(yīng)調(diào)整．利用交通流仿真軟件VISSIM創(chuàng)建仿真場(chǎng)景，以考察MDBA分簇算法的性能．仿真結(jié)果表明，與傳統(tǒng)無(wú)線傳感器網(wǎng)絡(luò)和移動(dòng)自組織網(wǎng)絡(luò)中的典型分簇算法相比，MDBA分簇算法中簇頭和簇成員的生存時(shí)間較長(zhǎng)，算法性能更優(yōu)，更加適用于車輛自組織網(wǎng)絡(luò)．

關(guān)鍵詞:車輛自組織網(wǎng)絡(luò);媒體接入控制;分簇算法;簇頭選舉;簇維護(hù)

引用本文:楊瓊，邢松，夏瑋瑋，等．一種基于MAC層時(shí)延上限的VANET自適應(yīng)分簇算法［J］．東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，46(1) : 1 －6．DOI: 10．3969/j．issn．1001－0505．2016．01．001．

目前，將無(wú)線通信技術(shù)應(yīng)用于車輛間通信的研究已經(jīng)受到了產(chǎn)業(yè)界和學(xué)者們?cè)絹?lái)越廣泛的關(guān)注［1］．媒體接入控制(MAC)是車輛自組織網(wǎng)絡(luò)(VANET)的關(guān)鍵技術(shù)之一，它決定了車輛節(jié)點(diǎn)共享無(wú)線信道的方式［2］．在VANET中針對(duì)MAC協(xié)議的研究大致可以分為兩大類:①以IEEE 802．11p標(biāo)準(zhǔn)為代表的基于競(jìng)爭(zhēng)的MAC協(xié)議［3－4］;②以時(shí)分多址接入(TDMA)技術(shù)為代表的非競(jìng)爭(zhēng)MAC協(xié)議［5－6］．研究發(fā)現(xiàn)，這2類MAC協(xié)議應(yīng)用于VANET時(shí)均存在著固有缺陷:在基于競(jìng)爭(zhēng)的MAC協(xié)議中，當(dāng)車輛節(jié)點(diǎn)數(shù)不斷增加時(shí)，車輛節(jié)點(diǎn)接入時(shí)延的增長(zhǎng)是無(wú)限的，因而不能保證對(duì)時(shí)延敏感的安全消息的及時(shí)傳輸;而在非競(jìng)爭(zhēng)MAC協(xié)議中，每個(gè)時(shí)間幀中所劃分的時(shí)隙數(shù)目是有限的，因此該類協(xié)議不能應(yīng)用于車流密集的場(chǎng)景［7－8］．

傳統(tǒng)的分簇方法［9］在VANET中并不適用，究其原因在于:①無(wú)線傳感器網(wǎng)絡(luò)(WSN)中能量問題是節(jié)點(diǎn)分簇時(shí)首要考慮的因素，而VANET中車輛節(jié)點(diǎn)并無(wú)能量限制;②VANET中車輛節(jié)點(diǎn)均處于快速移動(dòng)的狀態(tài)，而傳統(tǒng)的分簇方法并不能根據(jù)網(wǎng)絡(luò)拓?fù)渥兓瘉?lái)快速自適應(yīng)調(diào)整分簇;③傳統(tǒng)分簇方法主要從能量和路由的角度來(lái)考慮發(fā)射功率，而在VANET中簇的大小受消息的MAC層時(shí)延上限制約，以時(shí)分多址接入機(jī)制為例，簇的大小是由每個(gè)時(shí)間幀中所劃分的時(shí)隙數(shù)決定的，時(shí)間幀的長(zhǎng)短受消息時(shí)延上限的制約．為此，本文提出了一種基于MAC層時(shí)延上限的自適應(yīng)(MDBA)分簇算法．在2類傳統(tǒng)的MAC協(xié)議中融合節(jié)點(diǎn)自適應(yīng)分簇機(jī)制，有效克服了各自的固有缺陷，從而提高了VANET中媒體接入機(jī)制性能．

1　算法結(jié)構(gòu)

本文以典型的雙向六車道高速公路為研究場(chǎng)景．雙向行駛的車輛被公路中央的隔離帶分隔，故只考慮一側(cè)單向行駛的三車道場(chǎng)景．假設(shè)行駛在道路上的所有車輛都配有定位設(shè)備(如GPS)以及記錄車輛行駛狀態(tài)的傳感器．定位設(shè)備能夠獲取車輛當(dāng)前的位置，車輛傳感器能夠記錄車輛行駛過程中的狀態(tài)(包括速度、加速度、方向等)．通過定位設(shè)備和傳感器采集的信息將匯聚至車載單元(OBU)，利用無(wú)線通信設(shè)備發(fā)送給周圍其他車輛，同時(shí)也能接收其他車輛發(fā)來(lái)的行駛狀態(tài)信息．為解決VANET中現(xiàn)有MAC協(xié)議在車流量較大時(shí)的固有缺陷，擬對(duì)VANET中的車輛節(jié)點(diǎn)進(jìn)行自適應(yīng)分簇．每個(gè)簇由1個(gè)簇頭(CH)和若干個(gè)簇成員(CM)共同組成，所有簇成員都在簇頭的通信范圍之內(nèi)．

在基于分簇機(jī)制的VANET中，采用有限狀態(tài)機(jī)［10］對(duì)車輛節(jié)點(diǎn)所處狀態(tài)之間的轉(zhuǎn)換關(guān)系進(jìn)行描述．車輛節(jié)點(diǎn)存在4種狀態(tài):孤立節(jié)點(diǎn)狀態(tài)、簇頭狀態(tài)、簇成員狀態(tài)和偽孤立節(jié)點(diǎn)狀態(tài)(見圖1)．

1)孤立節(jié)點(diǎn)狀態(tài):網(wǎng)絡(luò)初始化之后，車輛節(jié)點(diǎn)處于孤立節(jié)點(diǎn)狀態(tài);當(dāng)車輛經(jīng)過分簇成為簇成員之后，某簇成員在一段時(shí)間內(nèi)離開簇頭的通信范圍，則該車輛節(jié)點(diǎn)又重新回到孤立節(jié)點(diǎn)狀態(tài)．

2)簇頭狀態(tài):孤立節(jié)點(diǎn)狀態(tài)下車輛節(jié)點(diǎn)通過簇頭選舉算法可能選舉為簇頭;當(dāng)車輛密度增大，簇內(nèi)成員增多到影響安全消息及時(shí)收發(fā)時(shí)，原有的簇將會(huì)進(jìn)行簇分裂以減少簇內(nèi)成員，在簇分裂過程中將再次利用簇頭選舉算法重新選舉出簇頭．

3)簇成員狀態(tài):在簇頭選舉算法中未被選舉為簇頭的孤立節(jié)點(diǎn)將會(huì)以簇成員的狀態(tài)加入簇;當(dāng)暫時(shí)離開簇頭通信范圍的簇成員又重新回到簇頭通信范圍之內(nèi)時(shí)，將會(huì)重新成為簇成員;當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，經(jīng)過簇分裂或者簇融合，原先的簇頭也可能轉(zhuǎn)換為簇成員．

4)偽孤立節(jié)點(diǎn)狀態(tài):為了避免頻繁地進(jìn)行簇維護(hù)，該狀態(tài)是簇成員狀態(tài)和孤立節(jié)點(diǎn)狀態(tài)之間的過渡狀態(tài)．當(dāng)簇成員離開簇頭通信范圍時(shí)，并不立即拋棄原簇成員的身份，如果只是暫時(shí)離開簇頭的通信范圍，則該節(jié)點(diǎn)成為偽孤立節(jié)點(diǎn)．

根據(jù)圖1中車輛節(jié)點(diǎn)4種狀態(tài)之間的轉(zhuǎn)換關(guān)系，將自適應(yīng)分簇算法分為簇頭選舉算法和簇維護(hù)算法2部分．其中，簇維護(hù)算法又包括簇成員的離開與加入、簇融合以及簇分裂．

圖1　分簇算法結(jié)構(gòu)

2　簇頭選舉算法

所提簇頭選舉算法基于消息傳輸?shù)腗AC層時(shí)延上限，綜合考慮了車輛節(jié)點(diǎn)的速度、加速度、位置及目的地等因素．MDBA分簇算法中的簇頭選舉算法步驟如下:

①初始化．當(dāng)車輛節(jié)點(diǎn)i進(jìn)入某高速路段時(shí)，該車輛節(jié)點(diǎn)開啟所有與VANET相關(guān)的設(shè)備(如GPS、傳感器、OBU等)，并輸入此次行駛的目的地信息Di，GPS開始獲得車輛節(jié)點(diǎn)i的位置信息Pi．

②車輛節(jié)點(diǎn)廣播Hello消息，定義傳輸半徑為R．Hello消息中包含車輛的狀態(tài)信息，包括車輛節(jié)點(diǎn)識(shí)別碼、車輛節(jié)點(diǎn)的位置信息Pi、車速vi和加速度ai，所有車輛節(jié)點(diǎn)的傳輸半徑相同，令初始化時(shí)的傳輸半徑為RInit．每個(gè)車輛節(jié)點(diǎn)在收到鄰居車輛節(jié)點(diǎn)的Hello消息后，將鄰居車輛節(jié)點(diǎn)的狀態(tài)信息加入自己的Hello消息中并再次廣播，于是每個(gè)車輛節(jié)點(diǎn)將會(huì)獲得2跳范圍內(nèi)車輛節(jié)點(diǎn)的狀態(tài)信息．沒有鄰居車輛節(jié)點(diǎn)的車輛節(jié)點(diǎn)直接成為簇頭．

③計(jì)算車輛的局部密度β以及此密度下一跳范圍內(nèi)的車輛節(jié)點(diǎn)數(shù)目None-hop=2Rβ．

④判斷None-hop是否能滿足消息傳輸?shù)腗AC層時(shí)延上限TD．如果不滿足時(shí)延上限，則調(diào)整發(fā)射功率以改變車輛節(jié)點(diǎn)的傳輸半徑R，轉(zhuǎn)至步驟②．

⑤根據(jù)加權(quán)函數(shù)F(·)計(jì)算簇頭指數(shù)．簇頭指數(shù)最小的車輛節(jié)點(diǎn)當(dāng)選為簇頭．車輛節(jié)點(diǎn)i的簇頭指數(shù)Q(i)體現(xiàn)了該車輛節(jié)點(diǎn)成為簇頭的合適程度，該指數(shù)越小則越適合被選舉為簇頭．如果出現(xiàn)2個(gè)車輛節(jié)點(diǎn)的簇頭指數(shù)相同，則車速越接近平均車速的車輛節(jié)點(diǎn)當(dāng)選為簇頭，未當(dāng)選的車輛節(jié)點(diǎn)成為簇成員．

加權(quán)函數(shù)F(·)需綜合考慮車速vi、加速度ai、位置Pi以及目的地Di對(duì)分簇穩(wěn)定性的影響．在一組分簇中，適合擔(dān)任簇頭的車輛節(jié)點(diǎn)的車速和加速度應(yīng)最接近于該分簇中所有車輛的平均值，簇頭應(yīng)位于該分簇的中心位置;為避免因簇頭離開行駛路段而造成的分簇不穩(wěn)定，離目的地較遠(yuǎn)的車輛節(jié)點(diǎn)適合擔(dān)任簇頭．基于此來(lái)設(shè)計(jì)加權(quán)函數(shù)，定義Fi(i)為根據(jù)車輛節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)計(jì)算出的車輛節(jié)點(diǎn)i的加權(quán)函數(shù)，其表達(dá)式為

式中，fv，fa，fp，fd分別為歸一化的速度因子、加速度因子、位置因子和目的地因子; w1，w2，w3，w4分別為其對(duì)應(yīng)的權(quán)重，w1，w2，w3，w4＞0，且w1+ w2+ w3+ w4=1．

歸一化速度因子fv可表示為

歸一化加速度因子fa可表示為

車輛節(jié)點(diǎn)獲取的位置信息Pi一般采用經(jīng)度緯度二維坐標(biāo)來(lái)描述，由于只考慮單向行駛的車道，且車輛被限制在規(guī)則的車道上行駛，故可以將車輛節(jié)點(diǎn)的位置信息簡(jiǎn)化為一維坐標(biāo)pi．

歸一化位置因子fp可表示為

歸一化的目的地因子fd可表示為

式中，di為車輛節(jié)點(diǎn)i到駛離高速路段出口的距離．

根據(jù)式(2)～(8)，可將加權(quán)函數(shù)表示為

車輛節(jié)點(diǎn)i的簇頭指數(shù)Q(i)為

3　簇維護(hù)算法

3．1簇成員的加入與離開

在分簇的VANET中，最常見的拓?fù)浣Y(jié)構(gòu)改變是簇成員的加入與離開．如圖2所示，當(dāng)孤立車輛節(jié)點(diǎn)CHB駛?cè)氪谹的范圍(即簇頭CHA的通信范圍)時(shí)，將會(huì)收到簇頭CHA的消息．車輛節(jié)點(diǎn)CHB知道自己進(jìn)入簇A后，首先向簇頭CHA發(fā)送請(qǐng)求加入簇A的消息．簇頭CHA收到請(qǐng)求消息后，根據(jù)MAC層時(shí)延上限TD判斷是否允許加入新成員，若不允許則直接發(fā)送消息拒絕車輛節(jié)點(diǎn)CHB加入，若允許則進(jìn)入等待期．等待期時(shí)長(zhǎng)為Tw，經(jīng)過Tw時(shí)間后，若車輛節(jié)點(diǎn)CHB仍在簇頭CHA的通信范圍內(nèi)，則正式允許CHB加入簇A，成為簇成員CMA6．當(dāng)簇成員CMA6駛離簇A，簇頭CHA和CMA6均離開對(duì)方的通信范圍時(shí)，簇成員CMA6就成為偽孤立節(jié)點(diǎn)，若在等待期Tw期間CMA6又回到簇頭的通信范圍內(nèi)，則CMA6從偽孤立節(jié)點(diǎn)狀態(tài)恢復(fù)為簇成員;若經(jīng)過等待期Tw后，CMA6仍離開簇頭的通信范圍，則CMA6離開簇A，從偽孤立節(jié)點(diǎn)轉(zhuǎn)變?yōu)楣铝⒐?jié)點(diǎn)CHB．

圖2　簇成員加入與離開示意圖

3．2簇分裂

簇分裂可以分為2類情況:①原先的分簇經(jīng)過分叉路段時(shí)，一部分車輛節(jié)點(diǎn)按原路線行駛，而另一部分車輛節(jié)點(diǎn)駛?cè)肓硗庖粭l路線，此時(shí)原先的分簇自然就被分裂為2個(gè)新的分簇;②車輛密度增大到原先的分簇不能容納更多簇成員時(shí)，需要將原先的簇分裂為多個(gè)較小的新簇，以滿足MAC層消息傳輸?shù)臅r(shí)延上限．由道路分叉造成的簇分裂情況較簡(jiǎn)單，原先的簇頭保持不變，繼續(xù)擔(dān)任簇頭，而在分叉路段的其他車輛節(jié)點(diǎn)將通過MDBA分簇算法中的簇頭選舉算法重新選出簇頭，形成分簇．下面著重分析車輛密度增加造成簇分裂的情況．當(dāng)高速公路某路段上車流量逐漸增多、車輛密度逐漸增大時(shí)，簇成員的數(shù)量也會(huì)趨于飽和．在MDBA分簇算法中，消息傳輸?shù)腗AC層時(shí)延上限為約束簇成員數(shù)量的因素．根據(jù)MAC層時(shí)延上限TD確定簇成員數(shù)量的上限值NC，當(dāng)簇A中的簇成員數(shù)量達(dá)到此上限值，且不斷有新的車輛節(jié)點(diǎn)請(qǐng)求加入簇A時(shí)，原來(lái)的分簇已不適用于當(dāng)前場(chǎng)景．此時(shí)，簇A的簇頭CHA將根據(jù)當(dāng)前的車輛密度β重新選擇車輛節(jié)點(diǎn)的消息傳輸半徑R，使新的消息傳輸半徑R'滿足2βR'＜NC．簇頭CHA在原先的傳輸半徑R內(nèi)廣播簇分裂消息以及新的傳輸半徑R'，收到簇頭CHA廣播消息的簇成員以及申請(qǐng)加入簇A的車輛節(jié)點(diǎn)將傳輸半徑設(shè)為R'，再通過MDBA分簇算法中的簇頭選舉算法重新選舉簇頭，從而使原先的簇A分裂為多個(gè)較小的新簇．

3．3簇融合

當(dāng)2個(gè)簇的簇頭移動(dòng)到彼此的通信范圍之內(nèi)時(shí)，需要利用簇融合算法對(duì)當(dāng)前的分簇進(jìn)行調(diào)整．在高速公路上，該情景通常發(fā)生在有車流匯入的路口．如圖3所示，當(dāng)2組分簇的簇頭處于彼此通信范圍內(nèi)時(shí)，簇A的簇頭CHA和簇B的簇頭CHB處于對(duì)方的通信范圍內(nèi)，車輛節(jié)點(diǎn)將自適應(yīng)地調(diào)整分簇，2組分簇將會(huì)融合．

圖3　簇融合示意圖

雙方簇頭首先交換各自簇成員的數(shù)量，由簇成員較多的一組簇接納簇成員較少的另一組簇;若簇成員數(shù)量相同，則由行駛方向上靠前的簇接納另一組簇．如圖3所示，由于簇A的簇成員少于簇B，則由簇B接納處于簇頭CHB通信范圍內(nèi)的簇A的所有成員．簇頭CHA將處于簇頭CHB通信范圍內(nèi)的原簇A成員的數(shù)量通知簇頭CHB，簇頭CHB收到申請(qǐng)加入的新成員數(shù)目后，根據(jù)MAC層時(shí)延上限TD判斷是否能夠容納所有新成員．若不能容納則告知簇頭CHA，然后簇頭CHA和CHB均廣播簇分裂消息告知其簇成員需要進(jìn)行簇分裂，使用3．2節(jié)中描述的簇分裂算法來(lái)調(diào)整分簇．若簇頭CHB可以容納申請(qǐng)加入的新成員，則簇頭CHB發(fā)送消息告知簇頭CHA后，簇頭CHA廣播告通知其簇成員解散簇A，簇頭CHA不再擔(dān)任簇頭，簇成員需申請(qǐng)加入簇B;簇A的簇頭CHA以及簇成員CMA1，CMA2將向簇頭CHB申請(qǐng)加入簇B，成為簇B的簇成員，而不在簇B通信范圍內(nèi)的原簇A的簇成員將采用簇頭選舉算法重新選舉出簇頭，形成新簇．由于孤立節(jié)點(diǎn)在沒有鄰居節(jié)點(diǎn)的情況下直接成為簇頭，故單個(gè)車輛節(jié)點(diǎn)加入已有簇的情況可以視為簇融合中最簡(jiǎn)單的一種情形．

4　仿真及結(jié)果分析

4．1仿真場(chǎng)景

為了獲取更加貼近實(shí)際交通情況的車輛行駛數(shù)據(jù)來(lái)驗(yàn)證MDBA分簇算法，采用了交通仿真軟件VISSIM來(lái)創(chuàng)建仿真場(chǎng)景．本文設(shè)定的仿真場(chǎng)景為高速公路上一側(cè)單向行駛的三車道場(chǎng)景．為了模擬典型的分叉路段車流匯入與分流，場(chǎng)景中設(shè)置了2段支路，主路段上的車輛將在分叉口分流一部分車輛進(jìn)入支路2，而另一段支路1上的車輛將會(huì)在分叉口匯入主路段．VISSIM的具體仿真參數(shù)設(shè)置如下:

1)路段設(shè)置．主路段中，車道數(shù)為3，車道寬度為3．5 m，主車道長(zhǎng)度為10 000．445 m．支路1中，車道數(shù)為2，車道寬度為3．5 m，車道長(zhǎng)度為1 003．682 m．支路2中，車道數(shù)為2，車道寬度為3．5 m，車道長(zhǎng)度為855．258 m．所有路段的類型均設(shè)置為高速公路“Freeway”．

2)基礎(chǔ)數(shù)據(jù)設(shè)置．選擇小汽車“Car”、貨車“HGV”以及大客車“Bus”，設(shè)置小汽車、貨車、大客車的期望速度范圍分別為80～120，60～100，70 ～110 km /h，其相對(duì)流量(即相應(yīng)車輛類型在輸入交通流中所占百分?jǐn)?shù))分別為80%，10%，10%．

3)車輛輸入設(shè)置．為比較不同車輛密度情況下的分簇算法性能，為主路段和支路1分別設(shè)置不同的交通流量，主路段低、中、高的車流量Vmain分別為1 000，5 000，8 000 veh/h，支路1路段低、中、高的車流量Vbranch分別為1 000，3 000，5 000 veh/h．在某一時(shí)間間隔內(nèi)，車輛進(jìn)入路段的規(guī)律服從泊松分布．定義車流量V = { Vmain，Vbranch}，仿真中設(shè)置的車流量分別為V1= { 1 000，1 000} veh/h，V2= { 1 000，3 000} veh/h，V3= { 5 000，3 000} veh/h，V4= { 5 000，5 000} veh/h，V5= { 8 000，3 000} veh/h，V6= { 8 000，5 000} veh/h．

4．2仿真結(jié)果

通過VISSIM中一段高速公路的交通流仿真，可以獲得每輛車在整個(gè)仿真過程中的行駛數(shù)據(jù)，包括車輛識(shí)別碼、車輛在路段中的位置、車速、加速度和目的地，將這些統(tǒng)計(jì)數(shù)據(jù)直接用于MDBA分簇算法中．設(shè)置初始化傳輸半徑RInit=0．5 km，MAC層傳輸延時(shí)要求TD＜50 ms，簇成員數(shù)量上限NC=40，等待期Tw=200 ms．權(quán)重w1，w2，w3，w4的取值是通過比較不同設(shè)置下簇頭平均生存時(shí)間來(lái)決定的．不同的權(quán)重值導(dǎo)致仿真結(jié)果中簇頭CH平均生存時(shí)間也各不相同．車流量設(shè)置為V3時(shí)權(quán)重選擇對(duì)簇頭平均生存時(shí)間的影響結(jié)果見1．由表可知，當(dāng)(w1，w2，w3，w4)設(shè)置為(0．4，0．4，0．1，0．1)時(shí)，可以獲得最大的簇頭CH平均生存時(shí)間，因此選擇(0．4，0．4，0．1，0．1)作為MDBA分簇算法的權(quán)重參數(shù)．選擇簇頭CH平均生存時(shí)間和簇成員CM平均生存時(shí)間作為評(píng)價(jià)分簇算法優(yōu)劣的標(biāo)準(zhǔn)．這2項(xiàng)評(píng)價(jià)標(biāo)準(zhǔn)直接反應(yīng)了簇的穩(wěn)定性，在相同的仿真條件下，簇頭和簇成員的生存時(shí)間越長(zhǎng)說(shuō)明分簇越穩(wěn)定，簇維護(hù)的代價(jià)越小，分簇算法越優(yōu)．

表1　權(quán)重選擇對(duì)簇頭平均生存時(shí)間的影響

不同車流量條件下CH平均生存時(shí)間和CM平均生存時(shí)間比較見圖4．由圖可知，利用MDBA分簇算法得到的CH平均生存時(shí)間和CM平均生存時(shí)間均高于Lowest-ID分簇算法［9］和MOBIC分簇算法［11］，即MDBA分簇算法性能最優(yōu)，MOBIC算法次之，Lowest-ID算法的性能最差．在Lowest-ID算法中，節(jié)點(diǎn)廣播Hello消息后，ID號(hào)最小的節(jié)點(diǎn)直接當(dāng)選為簇頭; MOBIC算法針對(duì)節(jié)點(diǎn)的移動(dòng)性，使用相對(duì)移動(dòng)量作為簇頭選舉的標(biāo)準(zhǔn);而MDBA算法則通過綜合考慮車輛節(jié)點(diǎn)的速度、加速度、位置和目的地4種因素來(lái)選舉簇頭．由此可見，性能最優(yōu)的MDBA算法更適用于以車輛為節(jié)點(diǎn)的車輛自組織網(wǎng)絡(luò)VANET．

圖4　不同車流量條件下CH和CM平均生存時(shí)間比較

5　結(jié)語(yǔ)

針對(duì)VANET中MAC層協(xié)議在車輛密集情況下性能變差的問題，利用VANET的特點(diǎn)對(duì)車輛節(jié)點(diǎn)進(jìn)行分簇，提出了一種MDBA分簇算法．該算法在MAC層消息傳輸?shù)臅r(shí)延上限限制下，綜合考慮了車速、加速度、位置和目的地4種因素，并能根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓赃m應(yīng)地進(jìn)行簇維護(hù)．仿真結(jié)果表明，MDBA分簇算法的性能優(yōu)于無(wú)線傳感器網(wǎng)絡(luò)和移動(dòng)自組織網(wǎng)絡(luò)中的傳統(tǒng)算法，大幅度提高了CH平均生存時(shí)間和CM平均生存時(shí)間，更適用于車輛自組織網(wǎng)絡(luò)．下一步研究著重于將MDBA分簇算法與MAC層協(xié)議相融合，設(shè)計(jì)出基于分簇算法的MAC協(xié)議．

參考文獻(xiàn)(References)

［1］Boban M，Vinhoza T T V，F(xiàn)erreira M，et al．Impact of vehicles as obstacles in vehicular ad hoc networks［J］．IEEE Journal on Selected Areas in Communications，2011，29(1) : 15－28．DOI: 10．1109/JSAC．2011．110103．

［2］Booysen M J，Zeadally S，van Rooyen G J．Survey of media access control protocols for vehicular ad hoc networks［J］．IET Communications，2011，5(11) : 1619 －1631．

［3］Yao Y，Rao L，Liu X．Performance and reliability analysis of IEEE 802．11p safety communication in a highway environment［J］．IEEE Transactions on Vehicular Technology，2013，62(9) : 4198－4212．DOI: 10．1109/TVT．2013．2284594．

［4］Miao L，Djouani K，Wyk B J V，et al．Performance evaluation of IEEE 802．11p MAC protocol in VANETs safety applications［C］/ /2013 IEEE Wireless Communications and Networking Conference．Shanghai，China，2013: 1663－1668．

［5］Rezazade L，Aghdasi H S，Ghorashi S A，et al．A novel STDMA MAC protocol for vehicular ad-hoc networks［C］/ /2011 IEEE International Symposium on Computer Networks and Distributed Systems．Tehran，Iran，2011: 148－151．

［6］Omar H A，Zhuang W H，Li L．VeMAC: A TDMA-based MAC protocol for reliable broadcast in VANETs ［J］．IEEE Transactions on Mobile Computing，2013，12(9) : 1724－1735．

［7］Sjoberg K，Uhlemann E，Strom E G．Delay and interference comparison of CSMA and self-organizing TDMA when used in VANETs［C］/ /The 7th IEEE International Wireless Communications and Mobile Computing Conference．Istanbul，Turkey，2011: 1488－1493．

［8］Stanica R，Chaput E，Beylot A L．Comparison of CSMA and TDMA for a heartbeat VANET application ［C］/ /2010 IEEE International Conference on Communications．Cape Town，South Africa，2010: 1－5．

［9］Zheng J，Jamalipour A．Wireless sensor networks: A networking perspective［M］．New Jersey: John Wiley ＆Sons，2009: 181－182．

［10］Su H，Zhang X，Chen H H．WSN12-6: Cluster-based DSRC architecture for QoS provisioning over vehicle ad hoc networks［C］/ /2006 IEEE Global Telecommunications Conference．San Francisco，CA，USA，2006: 1－5．

［11］Basu P，Khan N，Little T D C．A mobility based metric for clustering in mobile ad hoc networks［C］/ /International Conference on Distributed Computing Systems Workshop．Phoenix，AZ，USA，2001: 413－418．

MAC upper band delay based adaptive clustering algorithm for VANET

Yang Qiong1Xing Song2Xia Weiwei1Shen Lianfeng1
(1National Mobile Communications Research Laboratory，Southeast University，Nanjing 210096，China)
(2Department of Information Systems，California State University，Los Angeles 90032，USA)

Abstract:To improve the performance of media access control (MAC) protocols in vehicular ad hoc network (VANET) in the case of large vehicle density，a MAC upper band delay based adaptive (MDBA) clustering algorithm is proposed．The MDBA clustering algorithm includes the cluster head election algorithm and the cluster maintenance algorithm．Under the restriction of MAC upper bound delay，the speed，acceleration，position，and destination are comprehensively considered to select the cluster head in the cluster head election algorithm．In the cluster maintenance algorithm，clusters are adaptively adjusted according to the changes of network topology．Then，the traffic simulation software VISSIM is used to create simulation scenario to evaluate the performance of the MDBA clustering algorithm．The simulation results show that compared with the classic clustering algorithm in wireless sensor network and that in mobile ad hoc network，cluster head and cluster members in the MDBA clustering algorithm have longer life cycle，indicating that the MDBA clustering algorithm has better performance，thus it is more suitable for VANET．

Key words:vehicular ad hoc network; media access control; clustering algorithm; cluster head election;cluster maintenance

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61171081，61201175，61471164)、國(guó)家科技重大專項(xiàng)資助項(xiàng)目(2012ZX03004005)．

收稿日期:2015-06-07．

作者簡(jiǎn)介:楊瓊(1984—)，女，博士生;沈連豐(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，lfshen@ seu．edu．cn．

DOI:10．3969/j．issn．1001－0505．2016．01．001

中圖分類號(hào):TN923

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001－0505(2016) 01-0001-06