基于分簇的鐵路應(yīng)急通信網(wǎng)絡(luò)路由算法

謝健驪，李翠然＋

（1.蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州730070；2.北京交通大學(xué) 軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100044）

0 引 言

鐵路地形及傳輸環(huán)境的復(fù)雜性常常會(huì)使鐵路移動(dòng)通信系統(tǒng)中的基站等網(wǎng)元工作失效，此時(shí)，需要啟動(dòng)鐵路應(yīng)急通信［1］，以保證鐵路行車調(diào)度的順利進(jìn)行。GSM－R 作為我國(guó)鐵路綜合數(shù)字移動(dòng)通信系統(tǒng)［2，3］，其技術(shù)標(biāo)準(zhǔn) 《EIRENEFRSv7》［4］和 《EIRENE－SRSv15》［5］都 提 到 了 為 實(shí) 現(xiàn) 故 障 小區(qū)內(nèi)車內(nèi)終端 （節(jié)點(diǎn)）和地面終端之間的正常通信以提供鐵路沿線的無(wú)線覆蓋，需要構(gòu)建GSM－R應(yīng)急通信網(wǎng)絡(luò)。在鐵路沿線的應(yīng)急地點(diǎn)，一般來(lái)說(shuō)節(jié)點(diǎn)數(shù)目相對(duì)較多、移動(dòng)性相對(duì)較強(qiáng)，宜采用分簇結(jié)構(gòu)的GSM－R應(yīng)急通信網(wǎng)絡(luò)。綜合權(quán)重分簇算法作為一種折中各種參數(shù)影響的方法，它以優(yōu)良的簇穩(wěn)定性而成為一種常用的分簇算法。已有加權(quán)分簇算法［6－9］大都基于同構(gòu)節(jié)點(diǎn)、節(jié)點(diǎn)數(shù)目一般不超過(guò)70個(gè)且其最大移動(dòng)速度不超過(guò)120km／h而設(shè)計(jì)，無(wú)法很好地支持鐵路應(yīng)急通信中具有不同功能角色的大量異構(gòu)節(jié)點(diǎn)的高速移動(dòng)，尤其當(dāng)鐵路復(fù)雜地形的傳播環(huán)境極為惡劣時(shí)，問(wèn)題更加突出。此外，在上述文獻(xiàn)中，影響簇頭選擇的各參數(shù)權(quán)重值相對(duì)固定，因此，如何通過(guò)調(diào)節(jié)各參數(shù)權(quán)重值以適應(yīng)高速鐵路的復(fù)雜應(yīng)用環(huán)境是本文的研究重點(diǎn)。此外，我們還將對(duì)鐵路應(yīng)急通信網(wǎng)絡(luò)的分簇路由算法展開(kāi)研究，通過(guò)對(duì)平均端到端時(shí)延和平均吞吐量性能的仿真，以及與GSM－R的服務(wù)質(zhì)量 （quality of service，QoS）指標(biāo)對(duì)比分析，以驗(yàn)證所提算法在鐵路應(yīng)急通信中的適用性。

1 分簇及簇頭選擇參數(shù)的權(quán)重分配

簇頭選擇參數(shù)直接影響到分簇結(jié)構(gòu)的合理性。如何確定簇頭選擇參數(shù)以及各參數(shù)對(duì)于評(píng)估結(jié)果的重要性是影響分簇算法性能優(yōu)劣的關(guān)鍵。我們可以借助粗糙集理論解決這個(gè)問(wèn)題［2］。

（1）建立簇頭選擇參數(shù)決策表。決策表由各樣本的條件屬性值 （簇頭選擇參數(shù)的決策值）和決策屬性值 （網(wǎng)絡(luò)性能評(píng)估等級(jí)）組成。其中，樣本的條件屬性決策值vij由樣本每個(gè)條件屬性參數(shù)的測(cè)量值和其閾值vjk共同決定，見(jiàn)式 （1）；決策屬性則來(lái)自灰色聚類理論對(duì)服務(wù)質(zhì)量體系進(jìn)行預(yù)評(píng)估的結(jié)果

對(duì)于鐵路應(yīng)急通信網(wǎng)絡(luò)中的簇頭選擇參數(shù)，除了考慮一般的簇頭選擇因素外，還需要兼顧GSM－R節(jié)點(diǎn)業(yè)務(wù)等級(jí)的差異性等鐵路通信特色。因此，本文的簇頭選擇過(guò)程將綜合考慮節(jié)點(diǎn)度與理想節(jié)點(diǎn)度之差 （Dv）、節(jié)點(diǎn)的相對(duì)簇穩(wěn)定性 （Sv）、節(jié)點(diǎn)與其1跳鄰居節(jié)點(diǎn)的距離之和 （Pv）、節(jié)點(diǎn)已消耗的電池能量 （Cv）、節(jié)點(diǎn)的類型 （Tv）、節(jié)點(diǎn)的移動(dòng)性 （Mv）等6個(gè)參數(shù)。假設(shè)由各參數(shù)的取值構(gòu)成的評(píng)估決策表見(jiàn)表1。

表1 評(píng)估決策

表1中，條件屬性中的樣本值是根據(jù)對(duì)該參數(shù)的實(shí)際測(cè)量值進(jìn)行分級(jí)量化后的結(jié)果；評(píng)估等級(jí)值 “1，2，3”的含義分別為簇頭選擇參數(shù)使分簇結(jié)構(gòu)的合理性強(qiáng)、使分簇結(jié)構(gòu)的合理性一般、使分簇結(jié)構(gòu)不合理。

（2）計(jì)算決策屬性D 的條件屬性集C 正域posC（D）和D 的 ｛C－cj｝正域pos｛C－cj｝（D），其中 ｛C－cj｝為屬性集C 減去屬性cj后的子集。根據(jù)表1中的數(shù)據(jù)，計(jì)算得

（3）計(jì)算決策屬性D 對(duì)條件屬性集C 的依賴度γC（D）和D 對(duì) ｛C－cj｝的依賴度γ｛C－cj｝（D）

（4）計(jì)算條件屬性cj關(guān)于決策屬性D 的重要性σCD（cj）。條件屬性子集C′C 關(guān)于D 的重要性被定義為

于是，可得各屬性的重要性為

（5）計(jì)算各屬性重要性的歸一化權(quán)重wj

將式 （8）代入式 （9），可得權(quán)重集W 為

可見(jiàn)，決策表中的不同屬性 （簇頭選擇參數(shù)）具有不同的重要性 （權(quán)重）。若權(quán)重為0，則說(shuō)明該參數(shù)存在與否都不會(huì)影響評(píng)估的結(jié)果，此參數(shù)在本次評(píng)估中被定為冗余參數(shù)。對(duì)應(yīng)表1的數(shù)據(jù)，本次評(píng)估中的簇頭選擇有效參數(shù)及其權(quán)重分配為：節(jié)點(diǎn)度與理想節(jié)點(diǎn)度之差 （Dv）權(quán)重為3／8，節(jié)點(diǎn)的相對(duì)簇穩(wěn)定性 （Sv）權(quán)重為1／4，節(jié)點(diǎn)已消耗的電池能量 （Cv）權(quán)重為1／4，節(jié)點(diǎn)的類型 （Tv）權(quán)重為1／8。

（6）計(jì)算節(jié)點(diǎn)v的組合權(quán)重Wv

在鄰居節(jié)點(diǎn)中選擇具有最小Wv值的節(jié)點(diǎn)作為簇頭，其一跳鄰居節(jié)點(diǎn)成為該簇的成員并不再參與分簇。若當(dāng)具有最小Wv值的節(jié)點(diǎn)數(shù)目大于或等于兩個(gè)時(shí)，從節(jié)約節(jié)點(diǎn)發(fā)射功率的角度出發(fā)，則選擇剩余能量最多的節(jié)點(diǎn)成為簇頭。之后，簇頭節(jié)點(diǎn)發(fā)送 “Hello”消息，收到此信息的節(jié)點(diǎn)成為簇成員節(jié)點(diǎn)，至此，簇頭選擇和分簇過(guò)程結(jié)束。

2 分簇路由算法與仿真

在GSM－R應(yīng)急自組網(wǎng)系統(tǒng)中，采用分簇路由算法能夠減少節(jié)點(diǎn)移動(dòng)對(duì)算法的影響，降低路由維護(hù)開(kāi)銷以及路由洪泛的范圍，加快路由查找過(guò)程。另外在分簇結(jié)構(gòu)中，簇成員只需維護(hù)到簇內(nèi)其它節(jié)點(diǎn)的路由信息，而到簇間的路由則借助簇頭和網(wǎng)關(guān)的轉(zhuǎn)發(fā)完成，這不僅減少了參與路由查找的節(jié)點(diǎn)數(shù)目，而且能夠降低路由通信開(kāi)銷，具有很好的可擴(kuò)展性。

2.1 分簇路由算法

基于上述分簇過(guò)程可知：簇內(nèi)節(jié)點(diǎn)具有相似的移動(dòng)性，并且簇的大小充分考慮了GSM－R應(yīng)急網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目以及節(jié)點(diǎn)的計(jì)算處理能力，因此在簇內(nèi)適合采用主動(dòng)路由算法。它為每個(gè)節(jié)點(diǎn)保存了一張到簇內(nèi)其它節(jié)點(diǎn)的本地路由表，并周期性地向其鄰居進(jìn)行廣播以實(shí)時(shí)更新。這樣，簇內(nèi)節(jié)點(diǎn)間的路由不用花費(fèi)時(shí)間去進(jìn)行路由查找，有效地減少了GSM－R應(yīng)急網(wǎng)絡(luò)中地面節(jié)點(diǎn)之間以及車內(nèi)節(jié)點(diǎn)之間的通信時(shí)延。

在每個(gè)簇內(nèi)，每個(gè)節(jié)點(diǎn)僅知道到其一跳范圍內(nèi)的鄰居節(jié)點(diǎn)的路由信息，為了得到該節(jié)點(diǎn)到簇內(nèi)所有節(jié)點(diǎn)的本地路由表，同時(shí)避免洪泛方式耗費(fèi)大量的簇內(nèi)路由查找時(shí)延，在此定義一種簇內(nèi)路由請(qǐng)求數(shù)據(jù)包RREQ，其格式見(jiàn)表2［10］。

表2 RREQ 格式

經(jīng)過(guò)一段時(shí)間的RREQ 包交互，簇內(nèi)每個(gè)節(jié)點(diǎn)都會(huì)形成一張到簇內(nèi)其它節(jié)點(diǎn)的本地路由表，并且該路由表還包含到相鄰簇的網(wǎng)關(guān)／分布式網(wǎng)關(guān)的路由。

由于GSM－R應(yīng)急通信節(jié)點(diǎn)的隨機(jī)移動(dòng)性，特別是位于高速行駛的列車內(nèi)的節(jié)點(diǎn)，其相對(duì)于地面上的節(jié)點(diǎn)具有較高的移動(dòng)速度，車地間的網(wǎng)絡(luò)拓?fù)漕l繁變化，因此簇間路由算法宜采用按需路由算法［11］，以減少車地間拓?fù)涓淖儗?duì)路由算法的影響，降低簇間路由建立和維護(hù)的通信開(kāi)銷。簇間路由算法通過(guò)將路由請(qǐng)求數(shù)據(jù)包RREQ 發(fā)送到網(wǎng)關(guān)／相鄰簇的分布式網(wǎng)關(guān)，以搜索相鄰簇的簇內(nèi)路由，相鄰簇再搜索到其相鄰簇的簇內(nèi)路由，依次進(jìn)行下去，直至找到目的節(jié)點(diǎn)。該路由算法能夠發(fā)現(xiàn)多條路由，對(duì)于路由的選擇，它綜合考慮了路徑中節(jié)點(diǎn)的剩余能量、簇頭的數(shù)目以及總跳數(shù)，并為各因素分配一定的權(quán)值，選擇路徑中權(quán)重最小的作為最佳路由，其余作為備用路由。

路由算法的仿真性能指標(biāo)包括：平均端到端時(shí)延和網(wǎng)絡(luò)平均吞吐量。需要指出的是，為了方便與GSM－R 平均吞吐量指標(biāo)進(jìn)行對(duì)比，網(wǎng)絡(luò)平均吞吐量TH 的單位取為Byte／h。計(jì)算式如下

其中，NR為目的節(jié)點(diǎn)在時(shí)間T 內(nèi)接收到的數(shù)據(jù)分組數(shù)目。

2.2 仿真分析

以青藏線上格爾木站－南山口站區(qū)間這一鐵路實(shí)際運(yùn)行環(huán)境為模型，利用NS2仿真工具搭建鐵路應(yīng)急通信網(wǎng)絡(luò)仿真平臺(tái)，對(duì)平均端到端時(shí)延和網(wǎng)絡(luò)平均吞吐量性能進(jìn)行仿真。仿真參數(shù)包括：網(wǎng)絡(luò)環(huán)境參數(shù)、GSM－R 節(jié)點(diǎn)相關(guān)參數(shù)、負(fù)載參數(shù)以及算法參數(shù)，主要仿真參數(shù)見(jiàn)表3。

表3 相關(guān)仿真參數(shù)值

仿真實(shí)驗(yàn)分為兩組，第一組設(shè)置節(jié)點(diǎn)最大移動(dòng)速度為3m／s，考察在應(yīng)急場(chǎng)景1中各項(xiàng)性能指標(biāo)隨參與應(yīng)急通信的節(jié)點(diǎn)數(shù)目的變化情況；第二組設(shè)置網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目為50個(gè)，考察在應(yīng)急場(chǎng)景2中節(jié)點(diǎn)最大移動(dòng)速度的不同對(duì)各項(xiàng)性能指標(biāo)的影響情況。

（1）平均端到端時(shí)延

在GSM－R網(wǎng)絡(luò)中，列車調(diào)度命令采用電路方式傳輸，電路數(shù)據(jù)的傳輸性能會(huì)直接影響到列車運(yùn)行的安全。因此語(yǔ)音業(yè)務(wù)的平均端到端時(shí)延指標(biāo)值要求為0.4～0.5s［12］。GSM－R分組域數(shù)據(jù)業(yè)務(wù)的時(shí)延等級(jí)共分為4級(jí)，根據(jù)鐵路現(xiàn)行規(guī)定，要求調(diào)度數(shù)據(jù)信息無(wú)線傳送業(yè)務(wù)的時(shí)延等級(jí)小于或等于2級(jí)。在進(jìn)行端到端數(shù)據(jù)傳輸時(shí)，產(chǎn)生的時(shí)延有兩種：一種是平均時(shí)延，另一種是95%的數(shù)據(jù)分組被傳送的最大時(shí)延。本文主要對(duì)比的是平均時(shí)延。

平均端到端時(shí)延與應(yīng)急網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目以及節(jié)點(diǎn)最大移動(dòng)速度的關(guān)系曲線分別如圖1 （a）和圖1 （b）所示。

圖1 端到端時(shí)延性能

由圖1 （a）可以看出，當(dāng)應(yīng)急網(wǎng)絡(luò)中的節(jié)點(diǎn)具有較低的移動(dòng)性時(shí)，無(wú)論節(jié)點(diǎn)數(shù)目如何變化，提出的應(yīng)急分簇路由算法EBCR （emergency－based clustering routing）的平均端到端時(shí)延均維持在0.5s以下，符合GSM－R 網(wǎng)絡(luò)語(yǔ)音業(yè)務(wù)的時(shí)延指標(biāo)和數(shù)據(jù)業(yè)務(wù)的時(shí)延指標(biāo)要求。而當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)為60個(gè)時(shí)，時(shí)延值最低，為0.251s。

由圖1 （b）可以看出，當(dāng)節(jié)點(diǎn)移動(dòng)速度增加時(shí)，時(shí)延隨之增大。這是因?yàn)?，?jié)點(diǎn)高速運(yùn)動(dòng)引起了無(wú)線鏈路通信的頻繁中斷而使端到端時(shí)延增加。當(dāng)節(jié)點(diǎn)移動(dòng)速度小于50m／s時(shí)，平均端到端時(shí)延小于0.5s，符合GSM－R網(wǎng)絡(luò)語(yǔ)音業(yè)務(wù)的時(shí)延指標(biāo)要求。而隨著節(jié)點(diǎn)移動(dòng)速度的增加，時(shí)延值不再符合語(yǔ)音業(yè)務(wù)的時(shí)延指標(biāo)要求，但符合GSM－R 數(shù)據(jù)業(yè)務(wù)的時(shí)延指標(biāo)要求。

（2）平均吞吐量

吞吐量用來(lái)表示單位時(shí)間內(nèi)在一個(gè)連接上傳遞的最大字節(jié)數(shù)。平均吞吐量是用戶在較長(zhǎng)時(shí)間內(nèi)得到的數(shù)據(jù)傳輸速率，以Byte／h 為單位來(lái)衡量。GSM－R 分組域數(shù)據(jù)業(yè)務(wù)的平均吞吐量級(jí)別主要受到無(wú)線資源的限制，同時(shí)也受到移動(dòng)臺(tái)的無(wú)線接入能力的影響。

圖2 （a）和圖2 （b）分別為網(wǎng)絡(luò)平均吞吐量隨參與應(yīng)急通信的節(jié)點(diǎn)數(shù)目以及節(jié)點(diǎn)最大移動(dòng)速度的變化曲線。

圖2 平均吞吐量性能

圖2 （a）表明，隨著節(jié)點(diǎn)數(shù)目的增加，網(wǎng)絡(luò)吞吐量也呈增長(zhǎng)趨勢(shì)。值得注意的是，當(dāng)節(jié)點(diǎn)數(shù)目足夠多 （大于80個(gè)）時(shí)，吞吐量的增長(zhǎng)將趨于平緩或基本維持不變。無(wú)論節(jié)點(diǎn)數(shù)目如何變化，EBCR 算法的平均吞吐量性能均可達(dá)到GSM－R數(shù)據(jù)業(yè)務(wù)平均吞吐量級(jí)別的12級(jí)，可提供較高的網(wǎng)絡(luò)吞吐量。

由圖2 （b）可以看出，節(jié)點(diǎn)的高速移動(dòng)會(huì)使無(wú)線通信鏈路的中斷概率增大，網(wǎng)絡(luò)的平均吞吐量下降，但基本能維持在12級(jí)以上，滿足目前鐵路數(shù)據(jù)業(yè)務(wù)吞吐量多為10級(jí)的要求。

3 結(jié)束語(yǔ)

本文提出了一種用于鐵路應(yīng)急通信網(wǎng)絡(luò)的分簇路由算法，以解決GSM－R故障小區(qū)內(nèi)的節(jié)點(diǎn)間通信問(wèn)題，該算法同時(shí)兼顧了GSM－R 網(wǎng)絡(luò)的特點(diǎn)和鐵路通信服務(wù)質(zhì)量（quality of service，QoS）指標(biāo)要求。仿真分析結(jié)果表明，當(dāng)列車高速經(jīng)過(guò)故障小區(qū)時(shí)，若列車速度不超過(guò)50m／s（180km／h）時(shí)，所提算法的時(shí)延性能滿足鐵路語(yǔ)音業(yè)務(wù)和數(shù)據(jù)業(yè)務(wù)的指標(biāo)要求，可用于在列車運(yùn)行中斷的GSM－R 應(yīng)急場(chǎng)景中傳送調(diào)度語(yǔ)音和調(diào)度數(shù)據(jù)；當(dāng)列車速度在50m／s（180km／h）和80m／s（288km／h）之間時(shí)，該算法適用于一些非關(guān)鍵性調(diào)度數(shù)據(jù)的傳輸；而當(dāng)列車速度超過(guò)80m／s（288km／h）時(shí)，所提算法不再適用于GSM－R 鐵路應(yīng)急通信。綜上可知，當(dāng)列車或移動(dòng)節(jié)點(diǎn)的速度低于60m／s （約220km／h），該算法的平均端到端時(shí)延和平均吞吐量性能指標(biāo)均達(dá)到了鐵路移動(dòng)通信系統(tǒng)GSM－R的服務(wù)質(zhì)量要求。

下一步工作將研究如何在分簇路由算法的指標(biāo)權(quán)重分配合理性和算法復(fù)雜度方面取得良好的折中，以較好地適應(yīng)鐵路應(yīng)急通信場(chǎng)景的動(dòng)態(tài)變化特性。

［1］TIAN Shang，SHEN Yaoxing.Railway emergency communications［M］.Beijing：China Railway Publishing House，2008（in Chinese）. ［田裳，沈堯星.鐵路應(yīng)急通信 ［M］.北京：中國(guó)鐵道出版社，2008.］

［2］ZHONG Zhangdui，AI Bo，LIU Qiuyan，et al.Application theory of GSM－R ［M］.Beijing：Tsinghua University Press，Beijing Jiaotong University Press，2009 （in Chinese）. ［鐘章隊(duì)，艾渤，劉秋妍，等.鐵路數(shù)字移動(dòng)通信系統(tǒng) （GSM－R）應(yīng)用基礎(chǔ)理論 ［M］.北京：清華大學(xué)出版社，北京交通大學(xué)出版社，2009.］

［3］LI Cuiran，ZHONG Zhangdui，XIE Jianli，et al.Analysis of multicast routing algorithm for railway emergency communication network ［J］.China Railway Science，2012，33 （4）：83－90 （in Chinese）. ［李翠然，鐘章隊(duì)，謝健驪，等.鐵路應(yīng)急通信網(wǎng)絡(luò)組呼的組播路由算法分析 ［J］.中國(guó)鐵道科學(xué)，2012，33 （4）：83－90.］

［4］GSM－R Functional Group.UIC project EIRENE functional requirements specification V7 ［S］.2006.

［5］GSM－R Operators Group.UIC Project EIRENE system requirements specification V15 ［S］.2006.

［6］Hussein A H，Abu Salem A O，Yousef S A.Flexible weighted clustering algorithm based on battery power for mobile Ad hoc networks［C］／／IEEE International Symposium on Industrial Electronics，2008：2102－2107.

［7］Bouabdallah N，Langar R，Boutaba R.Design and analysis of mobility－aware clustering algorithms for wireless mesh networks［J］.IEEE／ACM Transactions on Networking，2010，18（6）：1677－1690.

［8］XIE Jianli，LI Cuiran，MA Qiaona.A clustering algorithm for GSM－R emergency network ［J］.Journal of the China Railway Society，2011，33 （12）：51－55 （in Chinese）.［謝健驪，李翠然，馬巧娜.一種適用于GSM－R 應(yīng)急網(wǎng)絡(luò)的分簇算法 ［J］.鐵道學(xué)報(bào)，2011，33 （12）：51－55.］

［9］Bradonjic M，Lazos L.Graph－based criteria for spectrum－aware clustering in cognitive radio networks［J］.Journal of Ad Hoc Networks，2012，10 （1）：75－94.

［10］TAO Cheng.Research on multi－h(huán)op clustering protocol for Ad hoc network ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2009 （in Chinese）.［陶成.基于多跳分簇的Ad Hoc網(wǎng)絡(luò)路由協(xié)議研究 ［D］.南京：南京航空航天大學(xué)，2009.］

［11］SUN Huitao.Study on clustering algorithms in Ad hoc network ［D］.Jilin：Jilin University，2010 （in Chinese）. ［孫慧濤.無(wú)線Ad Hoc網(wǎng)絡(luò)中分簇路由算法的研究 ［D］.長(zhǎng)春：吉林大學(xué)，2010.］

［12］ZHONG Zhangdui，WU Hao，LI Cuiran，et al.GSM－R wireless network planning and optimization ［M］.Beijing：Tsinghua University Press，Beijing Jiaotong University Press，2012 （in Chinese）.［鐘章隊(duì)，吳昊，李翠然，等.鐵路數(shù)字移動(dòng)通信系統(tǒng) （GSM－R）無(wú)線網(wǎng)絡(luò)規(guī)劃與優(yōu)化 ［M］，北京：清華大學(xué)出版社，北京交通大學(xué)出版社，2012.］