專利名稱：一種基于車流密度的物聯(lián)網(wǎng)單播數(shù)據(jù)傳輸方法
技術(shù)領(lǐng)域：
本發(fā)明屬于物聯(lián)網(wǎng)通信領(lǐng)域，涉及一種基于車流密度的物聯(lián)網(wǎng)單播數(shù)據(jù)傳輸方法，用于從運動的車輛向固定目標節(jié)點投遞數(shù)據(jù)。本發(fā)明中，目標節(jié)點與信宿節(jié)點、信宿，三個術(shù)語具有相同的含義。在該技術(shù)中提出了一種基于車流密度的物聯(lián)網(wǎng)端到端投遞代價的計算方法，以及相應(yīng)基于代價的路由選擇算法。應(yīng)用該技術(shù)能夠以有限開銷有效提高物聯(lián)網(wǎng)中數(shù)據(jù)多跳轉(zhuǎn)發(fā)的成功率、并縮短端到端投遞延時。
背景技術(shù)：
本發(fā)明涉及的物聯(lián)網(wǎng)特指由多個具有車載短距離無線通信設(shè)備的車輛自組織形成的移動自組網(wǎng)。在物聯(lián)網(wǎng)中，節(jié)點移動速度快，拓撲變化頻繁，同時車輛運動受城市道路約束，這些特點使物聯(lián)網(wǎng)顯著區(qū)別于一般的移動無線自組網(wǎng)絡(luò)。物聯(lián)網(wǎng)中的數(shù)據(jù)傳輸可以通過無線方式多跳傳輸，也可以通過車輛攜帶方式，也可以“多跳方式”、“車輛攜帶”兩種方式交替進行。目前由車輛組成的物聯(lián)網(wǎng)路由算法，可以分作三類:基于地理位置的路由，基于洪泛的路由和基于交通流信息的路由。在基于地理位置的路由中，數(shù)據(jù)包一直由持有車輛發(fā)送給鄰居車輛中最接近目標位置的車輛。在這種路由方式下，道路拓撲中的局部極點，或稀疏車輛都會導(dǎo)致數(shù)據(jù)轉(zhuǎn)發(fā)過程中出現(xiàn)沒有可用鏈路的情況，數(shù)據(jù)包投遞延時因此增加，甚至是因超時而丟棄。在基于洪泛的路由中，數(shù)據(jù)包以直接擴散方式進行轉(zhuǎn)發(fā)，數(shù)據(jù)包的攜帶車輛會將數(shù)據(jù)拷貝復(fù)制 給鄰居車輛中任意尚未持有該拷貝的車輛?；诤榉旱穆酚赡苋〉幂^高的投遞成功率與較小的投遞延時，但是由于網(wǎng)絡(luò)開銷大，通常不適用于繁忙網(wǎng)絡(luò)?；诮煌餍畔⒌穆酚墒墙陙砦锫?lián)網(wǎng)路由領(lǐng)域的研究熱點，該類路由通?；诮煌髁啃畔⒐浪銛?shù)據(jù)包沿路徑多跳轉(zhuǎn)發(fā)的代價，從而選擇具有較小轉(zhuǎn)發(fā)代價的路徑進行數(shù)據(jù)轉(zhuǎn)發(fā)?，F(xiàn)有的基于交通流信息的路由算法中，大多要求精確的實時交通流信息用于計算道路轉(zhuǎn)發(fā)的代價，在高度動態(tài)的路面交通環(huán)境中難以取得理想效果，且一般有較高的計算復(fù)雜度。

發(fā)明內(nèi)容
為克服上述方案缺陷與不足，本發(fā)明涉及一種輕量級的物聯(lián)網(wǎng)單播數(shù)據(jù)傳輸方法，通過量化路段車流密度，估算路段傳輸代價以及沿不同路徑轉(zhuǎn)發(fā)數(shù)據(jù)包的端到端傳輸代價，以作為數(shù)據(jù)包轉(zhuǎn)發(fā)時確定下一跳節(jié)點的選擇依據(jù)。本發(fā)明涉及的技術(shù)使用雙向車流轉(zhuǎn)發(fā)數(shù)據(jù)，使路段上具備短距離無線通信能力的車輛可參與該路段上任意方向的數(shù)據(jù)發(fā)送。與僅依賴單向車流的數(shù)據(jù)轉(zhuǎn)發(fā)機制相比較而言，車輛間有更充分的通信機會，從而提高數(shù)據(jù)投遞成功率，以及縮短數(shù)據(jù)投遞延時。此外，本發(fā)明假設(shè)車輛能通過某種定位技術(shù)(如裝配GPS接收設(shè)備)獲取其當前位置，并能通過電子地圖獲取城市中的道路實時車流密度情況或最近的歷史統(tǒng)計數(shù)據(jù)信息。每個節(jié)點具有全向通信天線，所有節(jié)點的通信半徑記做R。一般來說，R的取值范圍50米至200米。一種基于車流密度的物聯(lián)網(wǎng)單播數(shù)據(jù)傳輸方法，根據(jù)每個路段上雙向車流密度及其路段長度信息計算該路段的代價，并結(jié)合信源S位置、信宿t位置和地圖構(gòu)造擴展圖；由該擴展圖得到網(wǎng)絡(luò)中各節(jié)點間的最短路徑；單播數(shù)據(jù)包根據(jù)所計算的路徑逐路段、逐跳端到端轉(zhuǎn)發(fā)。所述的傳輸方法，沿最短路徑轉(zhuǎn)發(fā)數(shù)據(jù)包時，包括數(shù)據(jù)包的路段轉(zhuǎn)發(fā)階段和路口轉(zhuǎn)發(fā)階段，路段轉(zhuǎn)發(fā)中優(yōu)先將數(shù)據(jù)包轉(zhuǎn)發(fā)給最短路徑中最接近下一跳路口的車輛；路口轉(zhuǎn)發(fā)中優(yōu)先將到所有鄰居路口路徑代價最小、且當前路口有車輛向該鄰居路口行使的路口作為數(shù)據(jù)包轉(zhuǎn)發(fā)的下一跳路口，一個路口距信宿的投遞代價為該路口到信宿的最小投遞代價。在本發(fā)明中，由于僅使用路段平均車流密度進行路徑和鏈路代價估計，并在計算過程中進行了量化處理，因此對交通流信息的精度及實時性要求較低，減少了路由開銷。另一方面，由于車輛在路口處僅需要將數(shù)據(jù)發(fā)往相對最優(yōu)(相對最小的端到端路徑代價)的鄰居路口，因此本發(fā)明的量化機制在大部分情況下足夠保證車輛進行正確轉(zhuǎn)發(fā)決策。


圖1是數(shù)據(jù)包傳輸轉(zhuǎn)發(fā)實施例。
具體實施例方式I)路段代價計算方法:將城市路網(wǎng)拓撲建模成無向加權(quán)圖G(V，E)，每個路口作為一個頂點，V(G)表示路口的集合，E (G)表示路段的集合，則當路口 X與路口 y為相鄰路口時，有(x，y) e E(G)。令rxy代表路段(X，y)上的車流密度值，Lxy代表路段(X，y)的長度，Numxy代表路段(x，y)的雙向車輛總數(shù)(包括路段(x，y)上，從路口 X到路口 y和從路口 y到路口 X兩個方向上的所有車輛)，有rxy=Numxy/Lxy。假設(shè)車輛密度按照從疏到密劃分為N個等級，對應(yīng)密度區(qū)間集合為{[O, rj, (r1； r2],…，(rN_2, Tn^1 ], (^1, °o ) }，(Kr1Cr2〈…，00，其中
= - ，將道路上的車輛密度信息量化后并編號，記做 <，當rxy e
時，<=1;當
rxy e (Γι, r2]時，.￠=2;…;當rxye Ov1,⑴)時，< =N。在道路密度信息量化以后，定義
網(wǎng)絡(luò)中的每個路段(X，y)的路段代價權(quán)值如下:
—1 Twxy— ~r2)基于信源和信宿的擴展圖生成方法:給定信源s位置和信宿t位置和基于流量的拓撲圖G，構(gòu)造新的擴展圖G’，具體方法如下:.V (G，) =V (G)，E (G，)=E (G)； 如果s處于圖G中某路段(x，y)之中，則在s所在位置加一個新的虛擬路口 0，HG’ )=V(G，) + {0}，E(G，)=E(G’ ) + {(x, O), (O, y)}-{(x, y)}，其中 “ + ” 代表集合的合并運算，代表集合的減運算，rx() = r0y = rxy ;否則，如果信源s正處于原圖G中的某一路口，這時，則直接將該路口記做為O ; 如果t處于圖G中某路段(i，j)之中，則在t所在位置加一個新的虛擬路口 D，V(G，)=V(G，) + {D}，E(G’ )=E(G’ ) + {(i,D), (D，j)} - {(i，j)}，令 riD = rDJ = r^.;否則，如果信宿t正處于原圖G中的某一路口，則直接將該路口記做為D ； 構(gòu)造擴展圖完畢G’。3)結(jié)合擴展圖的最短路徑計算方法:根據(jù)道路拓撲圖G’和G’中每一個路段的代價，則可根據(jù)Dijkstra最短路算法計算從圖中任意路口 i到目標路口 D的最短路徑及其路徑代價CiD，i將隨數(shù)據(jù)包的逐路段轉(zhuǎn)發(fā)而變。4)結(jié)合上述路徑計算方法的數(shù)據(jù)包轉(zhuǎn)發(fā)方法:數(shù)據(jù)轉(zhuǎn)發(fā)過程包括兩階段:路段轉(zhuǎn)發(fā)階段和路口轉(zhuǎn)發(fā)階段。 在路段轉(zhuǎn)發(fā)中，對于每個持有數(shù)據(jù)包的車輛來說，如果鄰居節(jié)點中存在更接近下一跳路口的車輛，則將數(shù)據(jù)包轉(zhuǎn)發(fā)給該車輛，如果存在多個這樣的鄰居，則轉(zhuǎn)發(fā)給最靠近下一跳路口的車輛，如果不存在這樣的鄰居，該車輛則自己攜帶該數(shù)據(jù)包，直至到達下一跳路口，或直到遇到比自己更靠近下一跳路口的車輛，如果行進過程中遇到數(shù)據(jù)包的信宿，則直接將數(shù)據(jù)包轉(zhuǎn)交給信宿，路段上的中間轉(zhuǎn)發(fā)節(jié)點不允許改變數(shù)據(jù)包的下一跳路口方向。 在路口轉(zhuǎn)發(fā)中，當持有數(shù)據(jù)包m的車輛V位于路口 X時，X e V(G’)，會首先確定X的鄰居路口集N(X)，然后根據(jù)量化后的車流密度擴展圖G’計算每個鄰居路口 y到信宿t所在路口的最小投遞代價Cyt，其中y e N(X)，隨后根據(jù)計算得到每個鄰居路口的Cyt值對N(X)集合中的路口按端到端最小投遞代價從小到大的順序進行排序，得到有序排序后的路口集合N*(x);在獲取N*(x)以后，車輛V將選擇N* (X)中最高優(yōu)先級且當前路口正有車輛行駛的方向作為數(shù)據(jù)包轉(zhuǎn)發(fā)方向，將該方向上另一端路口作為數(shù)據(jù)包的下一跳路口存入數(shù)據(jù)包頭中，并將數(shù)據(jù)包發(fā)往該方向上的最接近下一跳路口的鄰居車輛。具體實例一:I)車輛密度量化參數(shù)r” Iv1, N的選擇方法示例。首先對路段長度進行歸一化，路段(X，y)的長度歸一化為Lxy=Lxy/R。如果rxy〈l/3，則認為車輛太稀疏，很難進行多跳傳輸，因此，一種可能的方式是設(shè)定r^lO, r2=20, r3=30, N=402)下面結(jié)合附圖及實例對本發(fā)明作進一步的說明。在附圖1中，左圖表示道路拓撲以及相應(yīng)路段上的車流密度，為方便描述，設(shè)路段等長，且長度為I。設(shè)密度量化區(qū)間集合為{[O, 10], (10, 20], (20, 30], (30，⑴)}，則可將路段車流密度量化為1、2、3、4四個等級。通過將量化值取倒數(shù)后，可計算得到路段代價如附圖1中右圖所示。假設(shè)有位于路口 X處的車輛有數(shù)據(jù)發(fā)往目標節(jié)點T，該車輛將會基于最短路徑算法計算鄰居路口 A、B、C向T投遞數(shù)據(jù)的最小估計代價。根據(jù)計算結(jié)果，路口 B具有最小代價估計，因此被選作下一跳路口。當下一跳路口選定后，路口 X處的車輛則會將數(shù)據(jù)包發(fā)送給在路段XB上行駛的車輛。當`數(shù)據(jù)包到達路口 B后，則會重復(fù)上述過程，直至數(shù)據(jù)包被最終投遞給目標節(jié)點T。
權(quán)利要求
1.一種基于車流密度的物聯(lián)網(wǎng)單播數(shù)據(jù)傳輸方法，其特征在于: 根據(jù)每個路段上雙向車流密度及其路段長度信息計算該路段的代價，并結(jié)合信源S位置、信宿t位置和地圖構(gòu)造擴展圖；由該擴展圖得到網(wǎng)絡(luò)中各節(jié)點間的最短路徑；單播數(shù)據(jù)包根據(jù)所計算的路徑逐路段、逐跳端到端轉(zhuǎn)發(fā)。
2.根據(jù)權(quán)利要求1所述的傳輸方法，其特征在于: 沿最短路徑轉(zhuǎn)發(fā)數(shù)據(jù)包時，包括數(shù)據(jù)包的路段轉(zhuǎn)發(fā)階段和路口轉(zhuǎn)發(fā)階段，路段轉(zhuǎn)發(fā)中優(yōu)先將數(shù)據(jù)包轉(zhuǎn)發(fā)給最短路徑中最接近下一跳路口的車輛；路口轉(zhuǎn)發(fā)中優(yōu)先將到所有鄰居路口中距信宿投遞代價最小、且當前路口有車輛向該鄰居路口行使的路口作為數(shù)據(jù)包轉(zhuǎn)發(fā)的下一跳路口，一個路口距信宿的投遞代價為該路口到信宿的最小投遞代價。
3.根據(jù)權(quán)利要求1所述的傳輸方法，其特征在于其中根據(jù)每個路段上雙向車流密度及其路段長度信息計算該路段的代價包括如下步驟: 將城市路網(wǎng)拓撲建模成無向加權(quán)圖G(V，E)，每個路口作為一個頂點，V(G)表示路口的集合，E(G)表示路段的集合，則當路口 X與路口 y為相鄰路口時，有(X，y) e E(G)； 籲令rxy代表路段(X，y)上的車流密度值，Lxy代表路段(X，y)的長度，Numxy代表路段(X，y)的雙向車輛總數(shù)，有rxy=Numxy/Lxy ； 將車輛密度按照從疏到密劃分為N個等級，對應(yīng)密度區(qū)間集合為{[O, rj, (r1； r2],…，(rN_2, Tn^1 ], (^1, °ο )}，(Kr1Cr2〈…，00，其中=IV1-1V2，將道路上的車輛密度信息量化后并編號，記做4，當rxy e [O1T1]時，<=1;當rxy e (r1； r2]時，r: =2;…;當 rxy e (rN_1； )時計算每個路段(X，y) e E(G)的路徑代價權(quán)值W。
4.根據(jù)權(quán)利要求3所述的傳輸方法，其特征在于，所述結(jié)合信源s和信宿t位置和地圖構(gòu)造道路拓撲擴展圖G’包括: V(G’)=V(G)，E(G’ ) =E(G)； 如果s處于圖G中某路段(x，y)之中，則在s所在位置加一個新的虛擬路口 O，HG’ )=V(G，) + {0}，E(G，)=E(G’ ) + {(x, O), (O，y)} - {(x，y)}，其中 “ + ” 代表集合的合并運算，代表集合的減運算，令rx() = r0y = rxy ;否則，如果信源s正處于原圖G中的某一路口，這時，則直接將該路口記做為O ; 如果t處于圖G中某路段(i，j)之中，則在t所在位置加一個新的虛擬路口 D，V(G，)=V(G’)+ {D}，E(G’)=E(G’)+ {(i，D)，(D，j)} - {(i，j)}，令 riD = rDJ = 否則，如果信宿 t正處于原圖G中的某一路口，則直接將該路口記做為D ； 構(gòu)造擴展圖G’完畢。
5.根據(jù)權(quán)利要求4所述的傳輸方法，其特征在于，所述由擴展圖得到網(wǎng)絡(luò)中各節(jié)點間的最短路徑包括: 根據(jù)道路拓撲擴展圖G’和G’中每一個路段的路徑代價權(quán)值，利用Dijkstra最短路算法計算從拓撲圖中從任意路口 i到目標路口 D的最短路徑及其路徑代價CiD，i將隨數(shù)據(jù)包的逐路段轉(zhuǎn)發(fā)而變。
6.根據(jù)權(quán)利要求5所述的傳輸方法，其特征在于，所述單播數(shù)據(jù)包根據(jù)所計算的路徑逐路段、逐跳端到端轉(zhuǎn)發(fā)包括路段轉(zhuǎn)發(fā)階段和路口轉(zhuǎn)發(fā)階段: 在路段轉(zhuǎn)發(fā)中，對于每個持有數(shù)據(jù)包的車輛來說，如果鄰居節(jié)點中存在更接近下一跳路口的車輛，則將數(shù)據(jù)包轉(zhuǎn)發(fā)給該車輛，如果存在多個這樣的鄰居，則轉(zhuǎn)發(fā)給最靠近下一跳路口的車輛，如果不存在這樣的鄰居，該車輛則自己攜帶該數(shù)據(jù)包，直至到達下一跳路口，或遇到比自己更靠近下一跳路口的車輛，如果行進過程中遇到信宿t，則直接將數(shù)據(jù)包轉(zhuǎn)交給信宿，路段上的中 間轉(zhuǎn)發(fā)節(jié)點不允許改變數(shù)據(jù)包的下一跳路口方向； 在路口轉(zhuǎn)發(fā)中，當持有數(shù)據(jù)包m的車輛V位于路口 X時，X e V(G’)，會首先確定X的鄰居路口集N (X)，然后根據(jù)車流密度量化后的擴展圖G’計算每個鄰居路口 y到信宿t所在路口的最小投遞代價Cyt，其中y e N(X)，隨后根據(jù)計算得到每個鄰居路口的Cyt值對N(X)集合中的路口按端到端最小投遞代價從小到大的順序進行排序，得到有序排序后的路口集合N*(x);在獲取N*(x)以后，車輛V將選擇N* (X)中最高優(yōu)先級且當前路口正有車輛行駛的方向作為數(shù)據(jù)包轉(zhuǎn)發(fā)方向，將該方向上另一端路口作為數(shù)據(jù)包的下一跳路口存入數(shù)據(jù)包頭中，并將數(shù)據(jù)包發(fā)往該方向上的最接近下一跳路口的鄰居車輛。
全文摘要
本發(fā)明屬于無線傳感網(wǎng)絡(luò)協(xié)議技術(shù)領(lǐng)域，具體涉及一種基于車流密度的物聯(lián)網(wǎng)單播數(shù)據(jù)傳輸方法，根據(jù)每個路段上雙向車流密度及其路段長度信息計算該路段的代價，并結(jié)合信源s位置、信宿t位置和地圖構(gòu)造擴展圖；由該擴展圖得到網(wǎng)絡(luò)中各節(jié)點間的最短路徑；單播數(shù)據(jù)包根據(jù)所計算的路徑逐路段、逐跳端到端轉(zhuǎn)發(fā)。
文檔編號H04W40/18GK103079250SQ201210546689
公開日2013年5月1日 申請日期2012年12月16日 優(yōu)先權(quán)日2012年12月16日
發(fā)明者趙壯, 賀靜, 梅武鋼, 尹崇祿 申請人:北京泛聯(lián)至誠科技有限公司