一種物聯網群體訪問路由算法

章 剛， 陳慶奎，2

（1.上海理工大學管理學院，上海 200093；

2.上海理工大學光電信息與計算機工程學院，上海 200093）

隨著物聯網（Internet of Things）用戶數量的不斷上升，請求服務種類不斷地變化，群體用戶對網絡QoS路由提出了越來越高的要求，但目前QoS路由研究主要集中在針對單個源節點到單個目的節點下不精確狀態信息的多約束QoS路由［1－4］和精確狀態信息的多約束QoS路由［5－8］，主要考慮單一請求下，在滿足QoS約束要求時，選擇合適路徑，而本文考慮的是一種在約束條件下群體訪問路由選擇方式.

通常情況下，在Internet上存在兩種傳輸流量區域，分別為黑色區域和白色區域.其中，黑色區域為所流過未知流量，而且不能監測區域；白色區域為能監測和控制流量區域，主要指可以通過白色區域上路由節點之間的協同監測，監測整個區域的有效帶寬、延時和代價.在實際環境下，黑色區域和白色區域之間是相互影響的，而且兩個區域是隨時間的變化而動態地變化，兩個區域所占的帶寬也隨時間的變化而變化.

本文以文獻［9］所描述的帶延遲約束群體訪問策略為應用背景，通過對用戶聚類，將大量用戶根據興趣分成多個群體（Group），所有群體通過智能代理訪問網絡上的資源，每個代理可以為多個群體提供服務.隨著網絡上流量的迅速增加，導致網絡上路由節點狀態信息時刻改變，那么，對于任意一個請求在延時約束范圍內到達目的節點可能存在一條或多條可行路徑，則本文所要討論的問題可以描述為一種在白色區域內網絡狀態信息動態改變下帶延時約束的群體多路徑選擇問題（D2CGMP），此問題是NP（non－deterministic polynomial）問題，因此，從啟發式算法角度來解決此問題.

文獻［10］從網絡工程角度分析了網絡再造工程對QoS路由的影響，基于文獻［10］的思想，本文提出了一種群體訪問路由算法（IOT＿GR），該算法主要基于預計算方式選擇路徑，通過部署在Internet上的智能路由節點構建一塊白色區域，在黑色區域動態影響下，利用算法中所定義的多種代理間的啟發式協同路由過程，在網絡狀態信息不精確情況下，有效地提供QoS路由服務.

1 模型描述

1.1 概念描述

接入代理AA：一種面向群體的智能體代理，群體通過此代理訪問Internet資源.

路由代理RA：一種連接AA與智能路由節點的智能體代理，主要為AA提供路由路徑選擇服務.

心跳代理HA：一種智能代理，主要負責智能路由節點之間狀態信息的交換.

探測包PP：主要為路由代理RA預先探測各點之間的有效路徑，由路由代理RA產生.

1.2 定義描述

定義1 路由模型可行性.本路由模型有效資源只在白色區域，同時又有黑色區域的動態影響，因此，本文只考慮當白色區域有足夠的資源時，本路由模型才具有可行性，其余情況本文暫不考慮.

定義2 D2CGMP問題.設網絡G〈V，E〉，其中，V＝｛v1，v2，…，vm｝為節點集合，E＝｛e1，e2，…，em｝為鏈路集合，設sj作為源節點，dk為目的節點，p（sj，dk）＝（sj，v1，v2，…，vi，dk）表示從源節點sj到目的節點dk的一條路由路徑.設rst（i）sj為源節點sj上第i個群體的一組請求表示為請求集合rst（i）sj中第t個資源請求.設D表示QoS延時度量，D（e）表示鏈路e上當前的延時，令

表示請求w在當前路徑p（sj，dk）上每條鏈路e的QoS度量D值之和，同時，設表示請求在QoS度量D下的約束量表示第t個請求尋找到的一條從源節點sj到目的節點dk的可行路徑，則多群體多請求在滿足約束條件下選擇一組有效路徑p′為

式中，m為源節點個數；n為目的節點個數；N為群體個數.

D2CGMP問題中所有的解路徑p′都屬于白色區域下解空間，都是滿足約束的一組有效可行路徑集合.由于白色區域時刻在變，因此，這組有效路徑解也時刻在變.

定義3 互不相交路徑.雖然D2CGMP問題可以尋找到一組滿足約束條件的有效路徑，但是，對于一組具有公共路由節點或者公共鏈路的路徑，依然會出現流量過載和可靠性低等問題，而互不相交QoS路由不僅能克服流量過載，實現信息分流，同時也提高了信息傳輸的可靠性，因此，本文考慮選擇有效路徑必須為互不相交路徑，給定網絡G〈V，E〉，V為節點集合，E為鏈路集合，則對于任意從源節點sj到目的節點dk的兩條路徑p1和p2滿足式（1）和式（2），說明p1∩p2＝?.

式（1）表示除源節點sj和目的節點dk外，對于任意一個中間節點v，出度數與入度數相等，參數M表示中間節點v上所有的鏈路數，同時，節點v的度d（v）滿足式（3）.

式中，nsv，nvt分別表示源節點sj到中間節點v有鏈路，中間節點v到目的節點dk有鏈路，則整體表示為從源節點sj出來的鏈路數等于進入目的節點dk的鏈路數.

證明 如果p1與p2為相交的兩條路徑，則在路徑p1與p2上必然存在一個中間節點v，使得其所有的邊數與其余所有中間節點的邊數不一致，以至于不能滿足式（1）；如果p1與p2為相交的兩條路徑，但是沒有公共的源節點與目的節點，則必然不能滿足式（2）；如果p1與p2為不相交的兩條路徑，有公共的源節點與目的節點，則對于任意一個中間節點v，其都滿足式（1）和式（2）.證畢.

定義4 路由節點狀態信息更新概率.路由節點觸發更新狀態信息的條件在于，當路由節點上的負載量達到一個閾值C時，就觸發更新機制.在此Q設為隊列，保存當前路由節點接收但沒有處理的請求量，令max Q和min Q分別表示觸發路由節點狀態信息更新時Q的最大量和最小量，則路由節點j狀態信息更新概率

1.3 算法描述

定義5 群體訪問過程示意圖，如下圖1所示.

圖1 群體訪問網絡過程示意圖Fig.1 Multi－groups accessing Internet process

圖1中網絡結構由智能路由節點構成，總共分為配置接入代理AA的節點、配置路由代理RA的節點、路由層路由節點Ri和目的節點Di，i∈n，rsti為群體提交一組資源訪問請求，由圖1可知，不同的AAi為不同的rsti提供服務，同時，rsti的一組請求由不同的用戶請求組成，其目的節點可以相同，也可以不同，如rst1向AA1提交一組請求，但是，請求資源所在目的節點不相同，為圖1中的橙色實線請求，在約束條件下分別尋找到兩條有效路徑AA1→RA1→R1→R4→D1和AA1→RA2→R2→R5→D3.同樣，rst3向AA3提交一組請求，同時，請求資源所在目的節點相同，為圖1中的綠色實線請求，雖然目的節點相同，但是，由于要滿足約束條件，因而產生兩條有效路徑分別為AA3→RA3→R1→R3→R5→Dn和AA3→RA3→R2→R5→Dn.

定義6 全局代價表.設三元組Ep＝（sj，dk，cost（p））為路徑p所對應的全局代價表，其中，sj為源節點，dk為目的節點，cost（p）為從源節點sj到目的節點dk所在路徑p的代價函數，網絡中每個路由節點都需要計算出經過本節點的所有路徑代價值，并利用心跳代理HA進行路由節點間信息交互，發送給其相鄰的路由節點，相鄰路由節點在此基礎上進行路由選擇，從而能有效地減少預計算的時間，同時構成路由算法的協同策略基礎.

定義7 帶延時約束的路徑預計算策略.設網絡拓撲結構為G〈V，E〉，其中，V＝｛v1，v2，…，vm｝為網絡所有節點的集合，E＝｛e1，e2，…，em｝為網絡鏈路的集合.對于每個RA，每隔一段時間T會產生一個探測包PP，探測當前源節點到目的節點所有有效路徑.對于每條路徑而言，在時間T，PP從源節點i出發到目的節點j，經過路由節點k時，查詢全局代價表Ep，如果存在一條有效路徑，則根據全局代價表Ep，在加入路由節點k時，重新計算路徑代價，如果滿足約束條件，則更新全局代價表Ep，并通過心跳代理HA發送到相鄰路由節點；如果不滿足約束條件，則根據式（5）計算一條從源節點i到目的節點j的有效路徑，其中，延時分為傳輸延時和排隊延時，如果當前總延時超過約束值，則路徑丟棄；否則，當前路由節點更新全局代價表Ep，并通過心跳代理HA發送到相鄰路由節點，則

定義8 路由節點狀態更新下全局代價表更新策略.當路由節點根據式（4）其概率pk達到閾值時，路由節點會廣播其更新狀態，此時路由節點狀態信息已經改變，因此，不能再根據更新前狀態值去計算.每個路由節點接收到其中路由節點狀態更新廣播后，重新計算其全局代價表Ep，并更新Ep.如果更新后的狀態對路徑沒有影響，則此條路徑依然有效；如果更新狀態后對路徑有影響，則從當前路徑中刪除此路由節點，并把此路由節點的上跳節點指向其下跳節點，最后更新Ep.

2 實驗與分析

2.1 實驗環境

實驗環境基于NS2（network simulator version 2）網絡仿真環境由仿真工具模擬大規模協同網絡場景，驗證IOT＿GR與當前一些重要算法間的差異，通過NS2仿真平臺，產生模擬的物理拓撲結構，在此拓撲基礎上建立節點之間的連接，最后部署本路由模型，按照模擬的物理拓撲分別創建了100～500個節點，鏈路的帶寬為2Mbps，鏈路上的延時為10～1 000ms，在網絡拓撲結構上分別配置IOT＿GR算法、MP－POC算法［3］、H＿MCOP算法［6］，同時設置參數.仿真測試硬件環境：1臺DELL臺式電腦，配置CPU Intel（R）Core（TM）2Duo E7400，主頻2.8GHz，內存2G，硬盤173.0G，操作系統：安裝Ubuntu 10.04Kernel Linux－2.6.32－30－generic GNOME 2.30.2操作系統.

實驗主要從擴展性、算法執行時間和算法對資源的消耗量這3個方面測試IOT＿GR算法與當前典型算法之間的差異，現給出具體的實驗結果與分析.

2.2 實驗結果

2.2.1 擴展性測試

實驗1 實驗分別模擬了兩組拓撲結構分別為100個節點拓撲結構和500個節點拓撲結構，同時模擬了3種算法在兩種拓撲結構下其服務路由滿意率SRQoS變化過程，由此分別比較當拓撲結構增大和群體請求數增加時3種算法的服務路由滿意率QoS的變化率.其中，服務路由滿意率SRQoS為請求服務成功個數與請求服務總數之比.圖2（a）描述了100個節點下服務路由滿意率X.

圖2 在各個節點下服務路由滿意率Fig.2 Satisfaction rate of server route under different nodes

由圖2（a）可知，當群體請求數比較少時，3種算法的路由滿意率比較接近，而且都超過80%；當群體請求個數超過50以后，3種算法的路由滿意率有下降趨勢，MP－POC算法和H＿MCOP滿意率都低于80%，而IOT＿GR算法依然超過80%.如圖2（b）所示，描述500個節點下服務路由滿意率.由圖2（b）可知，當群體請求數超過100時，和圖2（a）相比，3種算法的路由滿意率都呈現下降趨勢；當群體請求個數超過300以后，3種算法的路由滿意率均低于80%；當群體請求個數達到500以后，MP－POC算法和H＿MCOP滿意率都接近60%，而IOT＿GR算法依然超過60%.由此可見，隨著拓撲結構的擴大和群體個數的增加，IOT＿GR模型路由滿意率始終在80%上下徘徊，滿意率并沒有發生較大的波動.

2.2.2 算法平均執行時間測試

實驗2 在拓撲結構為100個節點拓撲結構下進行實驗，同時模擬3種算法在拓撲結構下，通過3組不同的群體個數，測試3種算法平均執行時間的變化過程.圖3描述了100個節點下的算法平均執行時間S.

圖3 算法平均執行時間Fig.3 Average execution time of algorithm

由圖3可知，群體個數在50時，3種算法的平均執行時間都比較少，均小于0.1；當群體個數超過100時，3種算法的平均執行時間都上升，尤其是H＿MCOP算法上升最快；當群體個數超過150時，MP－POC和H＿MCOP平均執行時間都超過0.3，但IOT＿GR算法平均執行時間比較少.

2.2.3 算法對資源消耗量測試

實驗3 資源消耗量包括鏈路消耗和節點消耗，在此用歸一化方式線性整合鏈路消耗和節點消耗，根據式（6）計算，其中，C為資源消耗量，C（e）為鏈路消耗，C（v）為節點消耗，α和β分別為鏈路和節點的權值，則

在拓撲結構為100個節點拓撲結構下進行實驗，同時模擬3種算法在拓撲結構下，通過3組不同的群體個數，測試3種算法對資源消耗量的變化過程.圖4描述了300個節點下的資源消耗量.U為單位消耗量.由圖4可知，在群體個數不超過100時，3種算法的消耗量都維持在2以下；當群體個數達到200時，3種算法的消耗量都上升，MP－POC和H＿MCOP消耗量都超過3；當群體個數達到300時，H＿MCOP消耗量超過5，雖然MP－POC和IOT＿GR都有上升，但是與H＿MCOP相比都將近減少了一個消耗量，尤其是IOT＿GR的消耗量最低.

圖4 資源消耗量Fig.4 Resource consumption level

3 結 論

針對路由節點狀態信息不斷變化，造成QoS路徑選擇無效性，本文提出了一種物聯網群體訪問路由算法（IOT＿GR），給出了該模型的具體實驗結果與分析.實驗表明，IOT＿GR算法在擴展性、算法執行時間及資源消耗度等方面比傳統的典型算法有一定的改善，但本模型并未過多地考慮數據安全、數據壓縮和數據傳輸等方面，這是作者下一步要研究的工作.

［1］ Zheng Yanxing，Wang Xiaoqing.Normal measure based multi－constrained path selection［J］.Journal of Software，2007，18（3）：636－645.

［2］ Tian Jing，Zheng Yanxing.Pareto optimal path selection in the presence of inaccurate state information［J］.Journal on Communications，2007，28（3）：68－77.

［3］ Turgay K，Krunz M.Bandwidth－delay constrained path selection under inaccurate state information［J］.IEEE／ACM Transactions on Networking，2003，11（3）：384－398.

［4］ Mieghem P，Kuipers F.Concepts of exact qos routing algorithms［J］.IEEE／ACM Transcations on Networking，2004，12（6）：851－864.

［5］ Turgay K，Marwan K.Routing multimedia traffic with QoS guarantees［J］.IEEE Transactions on Multimedia，2003，18（8）：429－443.

［6］ Xiong Ke，Qiu Zheng ding.Link－disjoint routing algorithm under multiple additive QoS constraints［J］.Journal on Communications，2010，31（6）：127－135

［7］ Sawada N，Kaneko K.Pairwise disjoint paths in pancake graphs［C］／／Proceedings of the Eighth International Conference on Parallel and Distributed Computing，Applications and Technologies.2007：376－382.

［8］ Xu D H，Chen Y，Xiong Y Z，et al.On the complexity of and algorithm for finding the shortest path with a disjoint counterpart［J］.IEEE／ACM Transcations on Networking，2006，14（1）：147－158.

［9］ Chen Qingkui，Jia He.Control Strategy of Group Behavior for Internet of Things［C］／／Proceedings of 2011 IEEE Ninth International Conference on Dependable，Autonomic and Secure Computing（DASC）.2012：1167－1171.

［10］ Lin Chuang，Li Yin.Optimization approaches for QoS in computer networks：A survey［J］.Chinese Journal of Computers，2011，34（1）：1－14.