Search Advanced

Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

2020 Volume 45 Issue 11
Article Contents
Previous Article Next Article

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
shu

An Efficient Routing Planning Algorithm for Mobile Agent in the IoT

  • College of Electronic Information and Automation, Aba Teachers University, Aba Sichuan 623002, China

More Information
  • Received Date: 20/03/2020
    Available Online: 20/11/2020

  • MSC: TP393

  • To solve the problem of short network lifecycle and high data transmission delay in existing data aggregation methods of Internet of things, an efficient routing planning algorithm for data aggregation of mobile Agent Internet of things based on Markov decision process (MDP) is proposed. This algorithm uses the k-medoids algorithm to cluster the devices of the Internet of things, and the angle-based mobile agent allocation process divides the cluster head into several groups. The MDP parameters (the Euclidean distance between the device and the sink, the residual energy of the device and its data priority) are used to provide routing planning for each mobile Agent in each cluster head to achieve efficient data aggregation. The experimental results show that, compared with other methods, this method can significantly improve the network life cycle, energy consumption, data transmission delay and reliability of the Internet of things.
  • 加载中
  • [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

    CrossRef Google Scholar

    [2] KOUICEM D E, BOUABDALLAH A, LAKHLEF H. Internet of Things Security: a Top-down Survey[J]. Computer Networks, 2018, 141(8): 199-221.

    Google Scholar

    [3] 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.

    Google Scholar

    [4] 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.

    Google Scholar

    [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

    CrossRef Google Scholar

    [6] 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.

    Google Scholar

    [7] 张平.物联网数据聚合技术及其主要挑战[J].计算机应用与软件, 2016, 33(7): 1-4, 41.

    Google Scholar

    [8] 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.

    Google Scholar

    [9] AL-TURJMAN F. Cognitive Routing Protocol for Disaster-inspired Internet of Things[J]. Future Generation Computer Systems, 2019, 92(10): 1103-1115.

    Google Scholar

    [10] 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.

    Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [13] 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.

    Google Scholar

    [14] 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.

    Google Scholar

  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(3)  /  Tables(1)

Export Citation
PDF
XML

Article Metrics

Article views(686) PDF downloads(97) Cited by(0)

Access History

Other Articles By Authors

An Efficient Routing Planning Algorithm for Mobile Agent in the IoT

  • Received Date: 20/03/2020
  • Available Online: 20/11/2020

Abstract: To solve the problem of short network lifecycle and high data transmission delay in existing data aggregation methods of Internet of things, an efficient routing planning algorithm for data aggregation of mobile Agent Internet of things based on Markov decision process (MDP) is proposed. This algorithm uses the k-medoids algorithm to cluster the devices of the Internet of things, and the angle-based mobile agent allocation process divides the cluster head into several groups. The MDP parameters (the Euclidean distance between the device and the sink, the residual energy of the device and its data priority) are used to provide routing planning for each mobile Agent in each cluster head to achieve efficient data aggregation. The experimental results show that, compared with other methods, this method can significantly improve the network life cycle, energy consumption, data transmission delay and reliability of the Internet of things.

    HTML

  • 物联网(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路由规划方法，用于物联网数据聚合.

1.   物联网模型

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

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

2.   基于MDP的移动Agent路由规划

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

    • 2.1.   IoT设备群集和簇头分组

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

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

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

    • 2.2.   马尔可夫决策过程(MDP)

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

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

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

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

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

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

    式(4)中w1，w2，w3和w4是奖励参数的影响系数.

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

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

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

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

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

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

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

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

    • 2.3.   基于MDP的移动Agent路由规划

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

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

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

    每个值初始化

    迭代算法

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

3.   实验结果与分析

  • 所有实验的仿真均由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次的平均值)，w1，w2，w3和w4奖励参数的影响系数[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)中：HPRD，MPRD和LPRD是到达信宿的高优先级、中优先级和低优先级数据的数量，HPGD，MPGD和LPGD表示由某些设备生成的高优先级、中优先级和低优先级数据的数量.如表 1所示，与Tree-DA和Cluster-DA相比，本文方法的系统可靠性分别提高了1.42倍和1.39倍.此外，本文方法的平均数据传输延迟分别比Tree-DA和Cluster-DA提高了15.02%和8.88%.

4.   结语

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

Figure (3)  Table (1) Reference (14)

Catalog

    Copyright Journal of Southwest China Normal University(Natural Science Edition)

    Address： Tel：023-68252540，68254576，68254478 E-mail：xbbjb@swu.edu.cn

    Supported by:Beijing Renhe Information Technology Co. Ltd

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return