留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

一种高效的物联网移动Agent路由规划算法

上一篇

下一篇

晏勇. 一种高效的物联网移动Agent路由规划算法[J]. 西南师范大学学报(自然科学版), 2020, 45(11): 73-79. doi: 10.13718/j.cnki.xsxb.2020.11.011
引用本文: 晏勇. 一种高效的物联网移动Agent路由规划算法[J]. 西南师范大学学报(自然科学版), 2020, 45(11): 73-79. doi: 10.13718/j.cnki.xsxb.2020.11.011
YAN Yong. An Efficient Routing Planning Algorithm for Mobile Agent in the IoT[J]. Journal of Southwest China Normal University(Natural Science Edition), 2020, 45(11): 73-79. doi: 10.13718/j.cnki.xsxb.2020.11.011
Citation: YAN Yong. An Efficient Routing Planning Algorithm for Mobile Agent in the IoT[J]. Journal of Southwest China Normal University(Natural Science Edition), 2020, 45(11): 73-79. doi: 10.13718/j.cnki.xsxb.2020.11.011

一种高效的物联网移动Agent路由规划算法

  • 基金项目: 四川省教育信息技术“十三五”规划课题(川教馆2019-142);阿坝州应用技术研究与开发重点资助项目(19YYJSYJ0091);阿坝师范学院自然科学重点资助项目(ASA19-17)
详细信息
    作者简介:

    晏勇(1983-),男,硕士,副教授,主要从事无线传感器网络软硬件协同设计研究 .

  • 中图分类号: TP393

An Efficient Routing Planning Algorithm for Mobile Agent in the IoT

  • 摘要: 针对现有物联网数据聚合方法存在网络生命周期短和数据传输时延较高等问题,提出了一种高效的基于马尔可夫决策过程(Markov Decision Process,MDP)的移动Agent物联网数据聚合路由规划算法.该算法使用k-中心点算法对物联网设备进行分簇,基于角度的移动Agent分配过程将簇头分成若干组,利用MDP参数(设备和信宿间的欧式距离、设备的剩余能量及其数据优先级)为每组簇头中的每个移动Agent提供路由规划,以实现高效的数据聚合.实验结果表明:与其他方法相比,本文方法在物联网的网络生存周期、能耗、数据传输时延和可靠性方面均有明显的改善.
  • 加载中
  • 图 1  本文方法的数据聚合过程流程图

    图 2  IoT的能量消耗

    图 3  活动设备数量

    表 1  物联网的可靠性和数据传输延迟

    本文方法 Tree-DA Cluster-DA
    稳定性 0.024 53 0.017 21 0.017 64
    数据传输延迟 328 ms 386 ms 360 ms
    下载: 导出CSV
  • [1] MENDEZ M D, PAPAPANAGIOTOU I, YANG B J. Internet of Things: Survey on Security[J]. Information Security Journal: A Global Perspective, 2018, 27(3): 162-182. doi: 10.1080/19393555.2018.1458258
    [2] doi: http://www.sciencedirect.com/science/article/pii/S1389128618301208 KOUICEM D E, BOUABDALLAH A, LAKHLEF H. Internet of Things Security: a Top-down Survey[J]. Computer Networks, 2018, 141(8): 199-221.
    [3] doi: http://www.sciencedirect.com/science/article/pii/S1383762118305265 DOVOM E M, AZMOODEH A, DEHGHANTANHA A, et al. Fuzzy Pattern Tree for Edge Malware Detection and Categorization in IoT[J]. Journal of Systems Architecture, 2019, 97(6): 1-7.
    [4] doi: http://dl.acm.org/citation.cfm?id=2691966 PANG Z B, ZHENG L R, TIAN J Z, et al. Design of a Terminal Solution for Integration of In-home Health Care Devices and Services towards the Internet-of-Things[J]. Enterprise Information Systems, 2015, 9(1): 86-116.
    [5] LI W J, SONG H B, ZENG F. Policy-Based Secure and Trustworthy Sensing for Internet of Things in Smart Cities[J]. IEEE Internet of Things Journal, 2018, 5(2): 716-723. doi: 10.1109/JIOT.2017.2720635
    [6] doi: http://www.researchgate.net/publication/321941867_Usage_of_mobile_elements_in_internet_of_things_environment_for_data_aggregation_in_wireless_sensor_networks ABDULSALAM H M, ALI B A, ALROUMI E. Usage of Mobile Elements in Internet of Things Environment for Data Aggregation in Wireless Sensor Networks[J]. Computers & Electrical Engineering, 2018, 72(12): 789-807.
    [7] 张平.物联网数据聚合技术及其主要挑战[J].计算机应用与软件, 2016, 33(7): 1-4, 41. doi: http://d.wanfangdata.com.cn/Periodical/jsjyyyrj201607001
    [8] doi: http://dl.acm.org/doi/10.1016/j.jnca.2017.08.006 POURGHEBLEH B, NAVIMIPOUR N J. Data Aggregation Mechanisms in the Internet of Things: a Systematic Review of the Literature and Recommendations for Future Research[J]. Journal of Network and Computer Applications, 2017, 97(5): 23-34.
    [9] doi: http://www.sciencedirect.com/science/article/pii/S0167739X16307439 AL-TURJMAN F. Cognitive Routing Protocol for Disaster-inspired Internet of Things[J]. Future Generation Computer Systems, 2019, 92(10): 1103-1115.
    [10] doi: http://www.sciencedirect.com/science/article/pii/S004579061630218X ZHU T, DHELIM S, ZHOU Z H, et al. An Architecture for Aggregating Information from Distributed Data Nodes for Industrial Internet of Things[J]. Computers & Electrical Engineering, 2017, 58(6): 337-349.
    [11] LI R N, STURTIVANT C, YU J G, et al. A Novel Secure and Efficient Data Aggregation Scheme for IoT[J]. IEEE Internet of Things Journal, 2019, 6(2): 1551-1560. doi: 10.1109/JIOT.2018.2848962
    [12] FITZGERALD E, PIÓRO M, TOMASZWSKI A. Energy-Optimal Data Aggregation and Dissemination for the Internet of Things[J]. IEEE Internet of Things Journal, 2018, 5(2): 955-969. doi: 10.1109/JIOT.2018.2803792
    [13] doi: http://dl.acm.org/doi/abs/10.1016/j.compeleceng.2016.09.025 LI Z, ZHANG W S, QIAO D J, et al. Lifetime Balanced Data Aggregation for the Internet of Things[J]. Computers & Electrical Engineering, 2017, 58(8): 244-264.
    [14] doi: http://www.researchgate.net/publication/332362294_Efficient_and_privacy-preserving_certificateless_data_aggregation_in_Internet_of_things-enabled_smart_grid SUN A J, WU A, ZHENG X K, et al. Efficient and Privacy-preserving Certificateless Data Aggregation in Internet of Things-Enabled Smart Grid[J]. International Journal of Distributed Sensor Networks, 2019, 15(4): 268-279.
  • 加载中
图( 3) 表( 1)
计量
  • 文章访问数:  651
  • HTML全文浏览数:  651
  • PDF下载数:  93
  • 施引文献:  0
出版历程
  • 收稿日期:  2020-03-20
  • 刊出日期:  2020-11-20

一种高效的物联网移动Agent路由规划算法

    作者简介: 晏勇(1983-),男,硕士,副教授,主要从事无线传感器网络软硬件协同设计研究
  • 阿坝师范学院 电子信息与自动化学院,四川 阿坝州 623002
基金项目:  四川省教育信息技术“十三五”规划课题(川教馆2019-142);阿坝州应用技术研究与开发重点资助项目(19YYJSYJ0091);阿坝师范学院自然科学重点资助项目(ASA19-17)

摘要: 针对现有物联网数据聚合方法存在网络生命周期短和数据传输时延较高等问题,提出了一种高效的基于马尔可夫决策过程(Markov Decision Process,MDP)的移动Agent物联网数据聚合路由规划算法.该算法使用k-中心点算法对物联网设备进行分簇,基于角度的移动Agent分配过程将簇头分成若干组,利用MDP参数(设备和信宿间的欧式距离、设备的剩余能量及其数据优先级)为每组簇头中的每个移动Agent提供路由规划,以实现高效的数据聚合.实验结果表明:与其他方法相比,本文方法在物联网的网络生存周期、能耗、数据传输时延和可靠性方面均有明显的改善.

English Abstract

  • 物联网(Internet of Things,IoT)是指数百万个智能传感器和日常物理设备之间的网络互连,它们位于监视环境中提供诸如无需人工干预的数据聚合等特定功能[1-2].通过多种软件和硬件技术的最新进步,IoT设备配备了传感、识别、计算、处理和联网功能,广泛用于医疗保健系统、智能环境以及智能能源系统等领域[3-5].为满足上述应用要求,数据聚合是物联网中实现服务质量(Quality of Services,QoS)要求(包括适当的传输延迟、可靠性、能耗和数据优先级)应适当解决的关键问题之一.物联网中的数据聚合主要思想是在设备上执行数据组合码,通过减少到接收器的冗余输出分组传输来加强能源优化[6-7],该过程减少注入网络的数据大小和显著降低数据聚合过程的延迟,并且传输较少的数据有助于设备高效利用能量,从而延长物联网寿命.

    目前,物联网的数据聚合基于客户端-服务器的方法执行,它利用基于树、基于簇和集中式的方法来提高系统性能[8].在基于树的方法中所有物联网设备都以树的分层形式部署,中间设备执行从叶设备到信宿的数据聚合过程.在基于簇的技术中物联网设备被分成几个具有单独簇头的簇,簇的每个成员与簇头进行通信以执行数据聚合过程.在集中式方法中所有IoT设备都与中央设备通信以执行聚合过程,并将聚合的数据传输到信宿[9].基于客户端-服务器的方法在一定程度上降低了IoT的能耗并延长了网络寿命,但是也带来了诸如数据传输延迟、IoT设备异构性、数据优先级等问题[10-11].

    文献[12]提出了两种基于混合整数规划的物联网数据聚合模型以提高数据收集过程的吞吐量.第一个模型收集所有连接互联网的网关数据,第二个模型将数据聚合并分发到所有多个目标设备,以最小化数据传输和聚合计算的成本.文献[13]提出了面向物联网的生命周期平衡数据聚合方法,该方法以协作的方式调整相邻设备的聚合延迟,在不增加端到端延迟的情况下可以平衡相邻设备之间的寿命,该方法在实践中能够动态适应网络变化.文献[14]提出了一种面向物联网智能电网的高效无证书数据聚合方案,该方案可以保证数据的机密性、完整性和隐藏用户的身份,可以抵抗重放攻击、修改攻击和冒充攻击,并且使用批量验证来提高验证效率.

    在研究了现有IoT数据聚合的基础上,为了进一步提高物联网的可靠性和网络生命周期,本文提出了基于马尔可夫决策过程(Markov Decision Process,MDP)的高效移动Agent路由规划方法,用于物联网数据聚合.

  • 本文将IoT建模为IoT=(NL),NL分别为IoT设备集和通信链路集,设监测环境的尺寸为H×W,并在其中心布置一个信宿. IoT设备是异构的,具有不同的初始能量、传输范围和数据优先级,随机分散并均匀分布在整个监控环境中.这些设备根据移动因素分为两组:①人们在日常活动期间随身携带的移动设备;②留在办公室或监控环境内任何位置的静态设备.利用运动小世界的移动性模型来模拟人们的运动,为了更准确地建立IoT模型,设每个设备都具有一些属性:移动设备间的距离不断变化,信宿固定在监控环境的中心,移动设备不断地靠近或离开它,每个IoT设备在系统初始化时都有一定的能量,数据处理和移动Agent接收/发送任务将消耗该能量直到耗尽,信宿始终有无限的能量.

    本文使用的多个移动Agent聚合来自IoT设备的数据.设每个移动Agent的总体大小为m,并且其具有用于聚合数据的存储空间dm,设备集群为k个集群,每个物联网设备将其感测到的数据发送到簇头,簇头具有足够的内存来缓冲从簇成员接收的数据.在建立簇头组后,信宿将移动Agent分配给每个组进行数据聚合.

  • 本文方法对IoT设备进行群集和对簇头进行分组,然后利用MDP对路线规划问题进行建模,最后应用值迭代导出移动Agent应该访问的IoT设备的最优顺序.本文方法的数据聚合过程如图 1所示.

  • 本文方法的首要目标是指定用于收集设备数据的簇头的实际位置,因此使用k-medoids聚类算法对设备进行群集,监视环境中的可用实际数据点.将监视环境的最佳簇数(k)作为k-medoids算法的输入,计算公式为

    式(1)中N为IoT设备集,M为监视环境的边(正方形),εfs为传输放大器的能耗,Eelec为接收或发送一位数据的能耗.物联网的能耗在很大程度上取决于数据传输所消耗的能量,因此将设备间的欧式距离作为k-medoids聚类算法的输入参数,可以提高本文方法的能量效率.

    本文方法基于角度分类方法将簇头分组在一起,将一个移动Agent分配给每个可靠的、能量高效的非重叠组.将监控环境基于估计的移动Agent数量划分为大小相同的扇区,为了找到数量相当的移动Agent,重新应用公式(1).在簇头分组中,每个组必须包含一个比预定阈值更靠近信宿的簇头以便在第一步接收移动Agent,并在聚合该组所有数据之后将其返回信宿.基于设备的传输范围,为每个物联网系统确定预定阈值.

  • 使用马尔可夫决策过程(MDP)来建模物联网上簇头中移动Agent的路由规划决策方式,以获得有效的路径规划、最优的资源消耗和最大的感知范围等效率目标. MDP由元组[SAP(sa),R(sa),γ]确定,其中S是有限状态空间,A是有限行动空间,P(sa)为在状态s中选择动作a时在状态集合上的转移概率分布,R(sa)为在状态s中采取行动a时所获得的奖励,γ是从未来动作和状态获得奖励的区间[0,1)的有限/无限贴现因子. MDP的解决方案指定出现特定状态时应选择哪个动作的策略π,在几种可能的策略中,最终目标是奖励最大化的最优策略π*.考虑以下MDP参数:

    状态空间(S):当移动Agent切换到特定设备时,查看IoT一组簇头的状态,组的状态由已在其上部署移动Agent的簇头的标识符来表示.将IoT上一组簇头中移动Agent路由规划进行建模的状态集定义为S={s1s2,…,sN},其中状态si指的是部署在设备di中的移动Agent.

    行动空间(A):表示物联网上一组簇头中移动Agent路由规划进行建模的动作集合A={a1a2,…,an},动作ai表示移动Agent转移到簇头di,这是下一步中移动Agent的目的地.显然,在任何状态下选择的动作都会影响下一步到达另一状态的转移概率.

    转移概率[P(sa)]:在采取行动时,如果簇头dj的位置不在簇头di的传输半径(移动Agent当前位置)之内,di将无法将移动Agent发送到dj,因此当IoT系统的当前状态为Si时,选择动作aj的转移概率将为零;如果移动Agent已在当前运行的先前步骤中收集了簇头dj的数据,则在该周期结束前无法选择di,此时选择动作aj的转移概率也将为零.在其他情况下,用于选择动作aj的转移概率是根据簇头之间的欧几里德距离来确定的.

    式(2)、式(3)中ri表示簇头di的传输半径,Dij表示簇头di和簇头dj间的距离,V是存储当前运行中已访问簇头的索引的集合,参数ij∈{1,2,3…,|N|}表示任何簇头(物联网设备)的索引,jV表示移动Agent只访问一个簇头一次. NormCDF指正态积分函数,表示Dij的标准正态分布.

    奖励函数R(siaj):当在状态si选择动作aj时,R(siaj)使用一些收益和罚金来计算模型的结果.

    式(4)中w1w2w3w4是奖励参数的影响系数.

    E(siaj)表示选择具有较少剩余能量的簇头的收益,应用此收益的目的是收集比其他簇头更早到期的簇头数据,以提高物联网系统的可靠性.簇头传输能力的预定阈值是接收移动Agent并将其重新发送到下一个簇头或信宿所需的总能量.

    式(5)、式(6)中,Ej(T)是簇头dj在时刻T的剩余能量,δ为预定阈值,Ej(0)是簇头dj的初始能量,Ej(R)和Ej(S)是接收移动Agent并将其发送给下一个簇头或簇头dj信宿所需的能量.

    如果簇头dj的剩余能量小于预定阈值,则它将不能接收移动Agent并将其数据传输到下一个簇头或信宿,此时用于选择簇头dj作为移动Agent下一个目的地的E(siaj)为零.否则,选择剩余能量较少的簇头作为移动Agent下一个目的地,从而带来更多的收益.

    ρ(siaj)表示取决于簇头的数据优先级的收入,用于优先收集高优先级的数据,以防止移动Agent数据存储器填满的情况下丢失数据.

    式(7)中α1α2α3考虑数据优先级收入,根据IoT各种应用的需求,数据优先级参数可以取不同的值.

    G(siaj)表示选择簇头作为移动Agent下一个目的地的收益.由于移动Agent通过访问每个簇头来增加内存中有用数据的大小,因此移动Agent倾向于逐渐接近信宿以减少注入网络的流量,从而提高了簇头的能耗和整个系统的寿命.

    式(8)中DjS是移动Agent下一个目的地选定簇头与信宿之间的欧式距离,DvS是尚未相遇的簇头与信宿之间的最小欧式距离,θ是收益,用于选择距离信宿最近的簇头作为移动Agent的下一个目的地,此参数在不同的应用程序中可以有不同的值.

    Pe(siaj)用于选择到达危险区域(监控环境的边缘地带)的簇头的惩罚,移动Agent对选择放置在监视环境边界点上的簇头作为下一个目的地不兴趣.若rS-β < DjS < rs,使用Pe(siaj)选择簇头dj作为移动Agent下一个目的地(动作aj),否则Pe(siaj)为零.rsβ分别是监测环境的半径和风险区域的半径.

  • 将网络设备的位置协调、设备的初始能量和设备的数据优先级作为本文方法的输入.当系统开始工作时,所有设备都会在物联网上广播它们的属性,信宿检查所有设备的总能量.如果簇的每个成员具有将其数据发送到簇头所需的能量,并且每个簇头具有接收移动Agent并将其重新发送到下一个目的地所需的能量,则信宿将计算任何物联网设备对之间的欧式距离以及任何物联网设备和信宿之间的欧式距离.应用公式(1)估计簇数(k),并使用k-medoids算法对IoT设备进行聚类.对分散在监控环境中的所有设备进行群集并确定簇头之后,信宿估计簇头组的数量并将其分组以向每个簇头组分配移动Agent.计算每个移动Agent的MDP参数,利用值迭代法推导出最优策略(每个移动Agent应该访问的物联网设备的最佳顺序).

    此步骤的结果是每个移动Agent访问其特定簇头组的路由规划,此时信宿向移动Agent发送其路由规划以收集数据并将其返回给信宿,信宿接收移动Agent的数据并刷新它们的数据存储器.最后,重新检查所有物联网设备的总能量(结束条件):如果簇的每个成员不具有将其数据发送到簇头所需的能量,或者每个簇头不具有接收移动Agent并将其重新发送到下一个目的地所需的能量,则结束该过程,输出最优策略集π*.

    值迭代使用状态转移概率来获得未来状态,然后计算在状态s中所采取的动作a的总奖励V(sa),某个状态的最优行动就是带来最大回报的行动,所有状态的最优操作构成最优策略π*.

    每个值初始化

    迭代算法

    如果Δ < δ,即总奖励V(sa)的变化不超过一个极小值δ,则终止算法输出最优策略,否则继续迭代.由于迭代方程的公式(12)是一个压缩映射,保证了此迭代算法的收敛性,其收敛速度为γ,每进行一次迭代,算法的最大计算复杂度为O(|S|2|A|).

  • 所有实验的仿真均由MATLAB R2018a在一台配置为Intel(R)Core(TM) i7-3520 M CPU @ 2.90 GHz和8 GB RAM的Windows 7操作系统进行,监视环境尺寸为3 400 m×3 400 m,设备初始能量εfs和传输范围εemp分别在(5~10) J和(600~1 000) m的范围内变化,εfs为10 pJ/(bit·m2),εemp为0.001 3 pJ/(bit·m4).移动软件Agent的大小为1 024 bits,可以从系统中收集2 048 bits的数据(其数据存储器为2 048比特).为了对本文方法进行评估,将测试结果与两种基于客户端-服务器的方法进行了比较.第一种是基于簇的数据聚合Cluster-DA,Cluster-DA通过利用设备的剩余能量水平及其在跳数方面的限制为大规模物联网提供节能的路由规划.第二种是基于树的数据聚合方法Tree-DA[12],Tree-DA收集所有物联网设备的数据并将其聚合分发到多个目的地以提高网络的生命周期.

    轮数是指设备从监视环境感知数据直到模拟结果数据包到达信宿的时间.模拟运行了50次以获得更准确的结果(图示的结果是运行50次的平均值),w1w2w3w4奖励参数的影响系数[13]为0.25.

    物联网的能耗是指散布在监控环境中的所有设备消耗的总能量. 图 2给出本文方法与基于簇的数据聚合Cluster-DA和基于树的数据聚合方法Tree-DA[12]的能量消耗.由图 2可以看出,从物联网设备到信宿数据传输的能耗随着轮数的增加而变大.与Tree-DA和Cluster-DA相比,本文方法的能耗低于其他两种方法,可满足物联网应用的要求.

    物联网的寿命是指系统开始工作之间的轮数与一定比例的初始设备仍在运行之间的轮数,图 3给出了随时间推移的实时设备数量和物联网的生命周期.考虑活动设备系统寿命时[14],本文方法的系统寿命分别比Tree-DA和Cluster-DA延长了4.32倍和2.32倍.这是因为本文利用人工智能技术的特点来建模移动Agent的路由规划,以实现有效的数据聚合过程.

    物联网的可靠性是评估系统在规定条件下执行其指定功能的能力的主要因素.移动Agent优先收集高优先级数据,以防止移动Agent数据存储器在被填满的情况下丢失重要数据.因此,系统的可靠性定义为到达信宿的数据优先级,表示为

    式(13)中:HPRDMPRDLPRD是到达信宿的高优先级、中优先级和低优先级数据的数量,HPGDMPGDLPGD表示由某些设备生成的高优先级、中优先级和低优先级数据的数量.如表 1所示,与Tree-DA和Cluster-DA相比,本文方法的系统可靠性分别提高了1.42倍和1.39倍.此外,本文方法的平均数据传输延迟分别比Tree-DA和Cluster-DA提高了15.02%和8.88%.

  • 为了有效地聚合来自设备的传感数据,本文提出了基于马尔可夫决策过程(MDP)的高效移动Agent物联网数据聚合的路由规划算法.该算法使用k-medoids和基于角度的分组技术对设备进行分簇,然后将指定的簇头组织成可靠、节能和不重叠的若干组用于移动Agent的分配,最后利用MDP的参数,包括设备和信宿之间的欧式距离、设备的剩余能量及其数据优先级,为每个簇头中的每个移动Agent提供有效的路由规划,以实现有效的数据聚合.实验结果表明与Tree-DA和Cluster-DA相比,本文方法在IoT能量消耗、数据传输延迟、系统寿命和可靠性方面均优于对比的方法.

参考文献 (14)

目录

/

返回文章
返回