一种物联网群体访问路由算法

章 刚， 陈庆奎，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.