Egyptian Informatics Journal（2016）17，217开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com骨干网辅助的无线传感器网络I. Snigdha，*， D. Gosaina， N. 古普塔湾a印度兰契Birla理工学院计算机科学与工程系b印度兰契Birla理工学院电子与通信工程系接收日期：2015年4月16日;修订日期：2015年9月11日;接受日期：2015年2015年12月24日在线发布摘要本文提出了一种在无线传感器网络应用中采用骨干网辅助通信的最佳汇聚点选址方案。通过将接收器放置在特定位置，可以有效地控制能量收集和延迟约束与基站放置在地理中心或随机放置在感兴趣区域末端的传统方案相比，所提出的方案将基站放置在感兴趣区域中连接节点的骨干的图论中心或质心该策略显示出每个数据包到达接收器所需的跳数的显著减少该方案适用于所有家庭的骨干辅助传感器网络中流行的图形，以确认性能的一致性和改善的通信骨干网络参数测量延迟，承载的负载和总能耗，最终影响的平均跳数的消息到达汇。©2016制作和主办由Elsevier B.V.代表开罗大学计算机和信息学院这是一篇基于CC BY-NC-ND许可证的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍无线传感器网络（Wireless Sensor Network，WSN）在世界范围内已经普遍存在。 从家庭自动化系统到关键锅炉监控，从X-Box到军事监控，它们无处不在。最近，大量的研究工作*通讯作者。电子邮件地址：itusnigdh@bitmesra.ac.in（I. Snigdh）。开罗大学计算机和信息系负责同行审查。使传感器网络的实际实施和布局能够适应[1]中提到的某些传感和监控应用的独特要求。每个无线传感器网络都受到低数据速率、能量储备以及通常多对一通信模式的限制在Steiner树[2]，最短路径树[3]或基于贪婪启发式[4]的树的帮助下，已经完成了对这种网络的性能分析。这些拓扑结构已经被用于许多路由协议和数据聚合方法，以优化能量、负载、响应时间或简单的网络寿命。基于树的骨干我们的研究的选择归因于和影响的文学作品可用于性能优化。HTECRP[5]等协议声称可以管理拥塞并执行公平性http://dx.doi.org/10.1016/j.eij.2015.09.0041110-8665© 2016制作和主办Elsevier B. V.代表开罗大学计算机和信息学院这是一个在CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词无线传感器网络;树型拓扑;水槽布置;能量;延迟PPP●2218 I. Snigdh等人在网络上通过分配特权的流量。维生素[6]提供了一个分层的骨干树算法，以提高能源效率和足够的网络寿命。虽然用于无线短距离传感器网络的局部区域生成树（LAST）协议优化了能量成本和由结构施加的干扰[7，8]，但是基于BFS的树以基站为根，为每个数据消息提供最短路径遍历，其通过采用用于崩溃节点的本地修复方法来有效地利用传感器资源，从而增加寿命[6]，类似于CTP[9，10]。此外，基于树的策略减少了重传的负担，因此可以用于拥塞管理[5]。因此，可以相信，树结构在无线传感器网络结构中是流行的，对于具有一个接收器和太多发送器节点的大多数应用，这证明我们的选择用于进一步分析是合理的。然而，这些研究集中于测量一个或多个静态或移动接收器的通信流，而没有强调接收器的放置是否也在确定上述网络统计（诸如延迟、负载和能耗）中起作用。虽然已经考虑了基于树的网络，但是汇的位置已经在根或源处完成[11]。此外，基于源的树和基于汇的树构造算法已经被分析并用于优化WSNs中的拥塞[12]。除了拥塞控制机制之外，通信中的能量能量消耗可以估计无线传感器网络，比较静态和移动汇。然而，文献[13]基于节点的移动路径和占空比来考虑能量消耗。节点的能量消耗主要取决于通信距离。减少通信距离的一种方法是部署多个静态接收器，并对每个传感器进行编程，以将数据路由到最近的接收器[14]。由于靠近汇点的节点转发和处理更多的数据，它们往往会提前耗尽。这个问题的解决方案是将感兴趣区域划分为具有静态汇的子字段[15]。然而，在采用多个汇点的主要问题是决定在哪里部署他们在监测区域，使数据中继负载是均衡的所有节点。另一种情况是除了静态接收器之外还部署移动接收器。在移动sink的情况下，随机sink移动不能保证数据已经从所有节点收集[16]。因此，需要多个移动接收器来以有效的方式改进数据收集。汇点定位策略包括确定性部署和随机部署。如[17 ， 18] 所 示 ， 已 将 汇 的 放 置 选 择 在 感 兴 趣 区 域（ROI）的端点或ROI的边缘。研究人员评估网络性能时，汇被放置在ROI的边缘的中点，ROI的中心，甚至在分块ROI的情况下，在聚类器的中心通过将汇聚节点周围的高能量节点适配为基站，可以降低汇聚节点上的负载。但是，没有关注延迟。相反，通过使用基于GA的方法观察到延迟，但没有考虑能量优化[18]。我们的文章认为，在已经连接的网络中，通过适当的水槽位置来节省能源和减少延迟实验结果表明，最优sink放置可以提高节点度，大大降低平均[19]《易经》：“以德为本，以德为本，以德为本。实验评估证实，与地理感知算法和朴素中心放置策略相比，拓扑感知算法提供了显着的生命周期改进[17，21，22]。虽然存在旨在最大化最坏情况延迟并延长WSN寿命的本地搜索技术[23]，但在实际场景中，可能存在障碍物或无线范围限制，这些障碍物或无线范围限制可能无法使sink放置可行。我们的文章，因此地址的问题，收敛- cast通信的树为基础的拓扑结构.我们试图提出一种策略，即当一个基于树的骨干网作为稳定的骨干网用于融合广播通信时，节点的选择将是最合适的我们认为，基于树的通信的性能是更好的，如果汇被放置在质心或图论中心的树。我们进一步透露，从比较或提出任何最适合的树构造算法的最优性。我们进一步假设网络采用基于树的骨干来执行必要的数据分发。这些算法在单独的计算机上使用，并且接收器重新定位可以手动执行或由移动接收器执行或者机器人我们的主要目的是隔离的最小能量消耗节点（MECN），验证良好的性能，在所研究的网络参数。我们提出了算法来确定节点适合作为sink在基于偏心率的骨干辅助网络中图的节点度所提出的策略，确保了，无论骨干网的生成策略，用于典型的WSN应用程序，最佳汇的位置落在树理论的“中心”或“质心”的图形。 由于跳数的数量基本上是由一个路由方案，决定从源到目的地的最佳路由，所提出的工作重点是确定的节点，将优化网络参数下经常采用的路由协议的网络。因此，我们的分析是基于实验结果的默认路由协议的所有家庭的树，以确认我们的观察。2. 预赛定义1（拓扑的地理中心（GC））。假设将“N”个传感器放置在场中并表示为二维平面中的（xi，yi）坐标，则任何拓扑的“GC（X，Y）”计算为GC（X，Y）= xi/n，yi/ n。定义2（拓扑的树理论中心）。为了定义'TTC'，我们首先定义树' T（V，E）'中的距离，作为节点'V i'和'V j '之间的距离' d T（V i，V j）'，这是它们之间的最小路径长度。总的来说，中心是顶点（或顶点的最小集合），其最小化涉及任意顶点与中心中的顶点之间的距离的某个函数。对于f（x） =dT（x，V），V其中' V（T）'是树T中所有顶点的集合;任何使f（x）最小化的顶点' x '被称为'中心'。或者， 中 心 可 以 被 视 为 最 小 -最 大 问 题min{max d T（x，V），V 2 V（T）}。222算法：偏心率（Tx）输入：树Tx=（V，E），以x为根。输出：节点x在Tx中的偏心率。步骤1：如果x是叶子，则返回0;步骤2：对于x的每个子元素s，递归地计算偏心率（Ts）;步骤3：返回max{Eccentricity（s）+w（x，s）}，6s2children（x）算法：权重（Tx）初始化Main_Root =TX输入：树Tx=（V，E），以x为根。输出：节点x在T x中的权重。步骤1：如果x是叶子，则返回0;步骤2：对于x的每个子元素s，递归地计算权重（Ts）;步骤3：如果（TS=Main_Root）其他return sum{Weight（s）+w（x，s）}，6s2children（x）返回max{Weight（s）+w（x，s）}，6s2children（x）最佳水槽位置219顶点' x '的偏心率被定义为从' x '到在' V（T）'中离'x '最远的顶点的距离。因此，对于V V（T），E（x）=maxd T（x，V）。因此，具有最小偏心率的顶点是“ 中 心 ” 或 “ TT C ” 。引理1. 树中顶点的偏心率可以在线性时间。证据设Tx，表示以顶点' x '为根的子树V（T），它是在顶点' x '及其所有后代上导出的子图。 让children（x）表示' x '的子集合。树的根的偏心率可以通过以下递归关系计算：dTx（x，V（Tx））=max{dTs（s，V（Ts））+w（x，s）}，6s chil-n（x）和w（x，s））节点“x”和其子节点“s”之间的边的权重。使用递归算法偏心率（Tx），偏心率可以在线性时间内计算，因为每个顶点遍历一次。H使用引理1和偏心算法，我们找到任何树的中心在多项式时间。定理1. 一棵树可以是单中心的，也可以是双中心的。事实1. 一棵树有两个或两个以上的叶子节点[24]。事实2.从x到树T中任何顶点的最大距离dT（x，V）发生在顶点是叶子/悬垂顶点时[24]。证据删除所有的叶子节点会产生一个仍然是树的图。仔细观察发现，从树中移除所有叶节点会均匀地将剩余顶点的偏心率减少一个（事实1）。因此，所有最初是中心的顶点仍然是中心。继续这个过程，我们要么有一个顶点最终是中心，要么有一条边的端点是中心。H定义3（树理论质心（TTCD））。 在树' T（V，E）'中，任何顶点' v '的子树的数量等于它的度，并且分支的总和（在子树中）对应于' v '处的子树的权重。顶点V的最重子树的权重被指定为顶点V的权重，并且最小权重顶点被指定为树T的质心。引理2. 顶点的权值可以在线性时间内计算。定理2. 每棵树都有一个由一个顶点或两个相邻顶点。证据类似于定理1的证明，通过递归迭代可以证明任何树是单中心或双中心的[24]。因此，我们可以在多项式时间内找到树的质心。H3. 系统模型我们考虑一棵树T（V，E），它是一个有序对（V，E），其中V=顶点集（由|V|顶点）和E =边集（由|E|边缘）。任何给定树的两个顶点Vi和Vj之间的距离表示为' d T（Vi，Vj）'，它表示两个顶点之间的最短路径长度 。顶 点 v 的度d （ v ） 定 义 为 与 之 关 联 的 边 的 个数，度为1的节点称为叶子/悬垂点。已知跳数的数量基本上由路由方案确定，该路由方案决定从源到目的地的最佳路由。此外，大多数路由协议选择具有最小跳数的最短路由。随着跳数的增加，到达目的地的总因此，性能是衡量方面的延迟，承载的负载和总的能量消耗，最终影响的平均跳数的消息到达汇。我们there-forth地址这些性能参数来评估我们的水槽放置方案。我们的观察所考虑的参数考虑了两种版本的树：一种遵循线性排列，而另一种关注节点的更现实的非线性排列。这些策略的承载计算可按第4节的方法计算。4. 承载力计算信宿上承载的负载与接收到的数据分组的总数有关相比之下，节点上的总负载指示为在信宿处成功的消息递送而生成和转发的分组的总数。源到宿通信的这种布置可以●图3线性树形拓扑中的传感器布置。220 I. Snigdh等人可以图示为具有不同下沉布置的线性或非线性拓扑表1表示用于图解说明进一步分析所考虑的不同策略的符号的图形表示。4.1. 线性树拓扑策略所建立的基于树的拓扑被分类在三个家庭称为情况1，情况2和情况3，随后，并进行比较的通信骨干网的性能相对于在地理中心或在感兴趣的区域的末端的汇在ROI中的不同位置处的汇的放置已经作为单独的情况进行了分析。策略1：在WSN的一端放置接收器已被考虑，因为接收器通常位于网络的一端，可以轻松访问该网络的一端，用于数据收集或电池补充目的，如图1传感器的线性排列，一端有水槽。图2传感器的线性排列，水槽在中间。图4a非线性树形拓扑：不同位置的TTC和TTCT。图4 b非线性树形拓扑：TTC和TTCT位于不同位置;另一个TTCT位于不同位置。表1图表中使用的符号颜色表示TTCT（Tree TheoreticalCentro）TTC（TreeTheoretical Centre）TTC和TTCT重合算法：Sink_Establishment（Tx）1. 对于树T的每个非叶节点x，2.设x为根3. 组合呼叫（Tx）4.将权重x和偏心率x广播到所有其他非叶节点及其NbrID6. 质心[ID]=最小值的ID（权重z）6z2非叶节点（T）5. 中心[ID]=最小值的ID（偏心率s）6z2非叶节点（T）7. SinkID =交点（中心，质心）最佳水槽位置221总承载量可计算为2* [1+ 2+ 3+···（N-1）/2]。CL¼N2-1=42策略4：最后将接收器放置在建议的位置;如图3所示的树理论中心（TTC）和质心（TTCT）。图3描绘了树形拓扑中的八个传感器，它们之间以最多“一个”边线性连接传感器（在位置4和5处）可以充当接收器。总承载量可计算为CL¼N2=4 × 3 × 10 - 4图4c位置.在相同4.2. 非线性树拓扑策略图图4a-4d描绘了非线性树拓扑中的每个场景的一个代表性树。图4c是理想情况，其中中心和质心重合，因此我们的结果不包括平凡命题。4.3. 使用的算法图4d非线性树形拓扑：TTC和TTCT在同一位置;附加TTC在不同位置。Fig. 1. 图1描绘了包括七个传感器的线性布置，其中最后一个传感器（在位置7处）起作用就像水槽一样 对于开始于节点1使其生成第一个数据包并转发，节点2生成自己的数据包并转发两个分组（它自己的分组和它接收的节点1的附加分组）。类似地，节点3将生成其自己的并且向前生成三个分组（其自己的分组和来自先前节点的两个分组）。因此，可以迭代地计算总承载载荷，C L=1+ 2+3 + 4 + 5 + 6+···N-1（WhereN是传感器总数CL<$NωN-1=21策略2：避免将接收器放置在拓扑中的某个随机位置，因为这不是期望的策略，其中结果是不可预测的、任意的和不受控制的。因此，我们不将其纳入分析。策略3：汇点位于图2所示线性拓扑的中心。图2描绘了七个传感器的类似线性布置，其中中间传感器（在位置4处）可以充当接收器。 节点1生成第一分组并将其转发到节点2，节点2转发两个分组（其自己的数据和节点1的接收数据）。类似于情况1，对于节点3继续该然而，节点7将转发一个分组，节点6将转发两个分组，节点5将转发三个分组到宿。分组转发和聚合由单向箭头描绘。的5. 结果在大多数无线传感器网络中，为了提高能量效率，数据包通过多跳通信发送到信宿。中间传感器充当路由器，并且经历来自其他传感器和路由器的高分组流。阻碍，每个节点的承载负载增加，并且对于基站或宿附近的节点，最终分组递送被相当大地延迟。最佳的水槽放置结果在打击这种情况下。我们的目标是确定最好的站点之间的部署节点，符合树结构的拓扑结构的reasons最有名的汇。算法：组合（Tx）初始化Main_Root =TX输入：树Tx=（V，E），以x为根。输出：在Tx中节点x的重量和偏心率。1：如果x是叶子，发送0到父节点;2：对于x的每个子元素s，递归地计算组合（Ts）3：权重s= sum{组合（s）+w（x，s）}，6s2个子项（x）If（TS=Main_Root）偏心率s= max{组合（s）+w（x，s）}，6s2儿童（x）将权重和偏心率发送到父节点权重s= max{组合（s）+w（x，s）}，6s2个孩子（x）非线性树拓扑：TTC和TTCT表2模拟参数。参数无线类型路由协议网络规模（ROI）节点类型电池型号路径损耗型号感应范围值802.11bAODV、DSR、FISHEYE、OLSR1500 ×1500云母粉剩余寿命估计器Two Ray10米222 I. Snigdh等人已经被调查的参数是关键路由协议的承载负载、平均端到端延迟和总能耗，这些关键路由协议即基于Ad hoc按需向量（AODV）、动态源路由（DSR）、鱼眼、优化链路状态路由（OLSR）协议[17]，由与所考虑的情况有关的图描绘为了估计所考虑的参数，随机部署节点，并使用QualNet模拟器6.0[25]在不同迭代次数上收集单个节点统计数据。QualNet提供了一个全面的环境，用于采用不同的协议，创建和动画网络场景，并分析其性能。这些节点最初是随机部署的，然后以它们在地形上类似于所提到的家庭的方式进行排列。节点一旦被布置成近似于与图1A和1B中描绘的图类似的图案。图4a、4b和4d服从无线网络中使用的不同路由协议。统计，收集了50个拓扑结构的每种类型的家庭说明和平均为三个类中的每一个，特别是属于非线性树拓扑。考虑了基于50个拓扑的平均值的结论假设。节点是位置感知的，并且它们之间存在基于预先构造的树的通信骨干。平均端到端延迟取决于消息最终到达接收端所经历的跳数所消耗的能量是通信和接收所花费的总能量的总和在空闲和休眠期间消耗的能量可以忽略不计。● 模拟参数在表2中给出。第一种情况考虑了一个图与第二种情况分析一个图与图5（a）、（b）和（c）描绘了每个协议的平均跳数。我们确认，跳数的数量是显着较少，在我们提出的网站（中心和质心）的所有协议考虑相比，平均跳数的情况下，我们把汇在年底或在（一）（（图5每个协议的平均跳数（a）情况1（b）情况2（c）情况3。●●●（（最佳水槽位置223（一）（b）第（1）款图6每个协议的总承载负载（a）情况1（b）情况2（c）情况3。（b）第（1）款（c）第（1）款图7协议的平均端到端延迟（a）情况1（b）情况2（c）情况3。224 I. Snigdh等人（一）（b）第（1）款（c）第（1）款地理中心。随着跳数的减少，每个节点的负载以及端到端延迟大大减少。这一解释是补充图中的图形结果。图6（a）、（b）和（c）描绘了每个节点的承载负载，图7（a）、（b）和（c）分别描绘了端到端延迟。此外，如果节点接收和发送路由到它们的分组的数量较少，则网络作为整体的平均能量消耗也相当少，如图8（a）、（b）和（c）所示。不同的拓扑结构产生几乎相似的结果，这促使我们考虑它们的平均值，以避免图中的冗余。我们观察到一致的结果，所有三种情况下考虑的最适合的位置的水槽的采用落在中心或在图的质心。因此，我们的研究结果抹杀的要求，把一个汇中心或在年底的区域的利益。6. 结论典型的WSN场景假设消息被路由到通常是树的根的接收器这种策略的问题的热点结束到通信中断，由于单节点故障最接近的汇。采用基于图的拓扑结构为我们提供了可变路线和汇点位置的选择偏向这种结构的论点是基于在一个汇点下实现然而，我们的文章证实，图质心放置的汇聚节点是更好的网络延迟和能源消耗，而不是有一个汇根树的通信骨干。此外，我们的研究结果表明，消息转发到汇（在跳数方面）是最少的图形的- oretic中心或质心。这确保了最小的延迟和lesser每个节点的能源消耗，因此更长的寿命。我们的结果是有限的，由于模拟环境的约束，少量的节点。这项工作可以通过将更广泛的网络与密集部署相结合来鱼眼协议的性能不佳促使我们分析我们提出的工作，将移动性在未来。引用图8（a）情况1[1] Akyildiz IF，Su W，Sankarasubramaniam Y，Cayirci E. 无线传感器网络综述。 Comput Netw 2002;38（4）：393-422.[2] Prabh KS，Abdelzaher TF.传感器网络中的节能数据缓存布局。ACM TransSens Netw（TOSN）2005;1（2）：178-203.[3] Wang ZM，Basagni S，Melachrinoudis E，Petrioli C，利用sink移动性最大化传感器网络寿命。第38届夏威夷国际系统科学年会2005年，美国电气和电子工程师协会（IEEE）[4] IncelOD，Ghosh A，Krishnamachari B. 无线传感器网络中基于树的数据采集调度算法。在：传感器网络中分布式计算的理论方面. Berlin，Heidelberg：Springer; 2011. p.407- 45[5] Messina D，Ortolani M，Lo Re G，使用数据聚合增强树型无线传感器网络鲁棒性的网络协议在：IEEE国际移动自组织和传感器系统会议上(b)案例2（c）MASS; 2007年。第1最佳水槽位置225[6] Wang J，Hyong KJ. ViTAMin：一种用于无线传感器网络路由的最小能耗虚拟骨干树算法。在：IEEE信息网络国际会议（ICOIN）; 2012年。p. 144比9[7] 杨伟东，李晓梅，李晓梅.无线传感器网络中多播树和汇聚树的干扰感知构建。在：下一代远程通信和有线/无线高级网络，计算机科学讲义，第5174卷; 2008年。p. 72比87[8] Chakraborty S，Nandi S，Karmakar S.基于树的局部修复方法延长查询驱动的无线传感器网络生命周期。IEEEInternationalConferenceonComputationalScienceandEngineering（CSE），2011年。[9] 放大图片作者：Patel D，Chawla B，Parekh C. TinyOS-2.x环境下无线传感器网络能量感知和链路质量路由。 IntJMod Eng Res 2013;3（3）：1357-65.[10] Colesanti U，Santini S.用于无线传感器网络模拟器的收集树协议技术报告编号729，苏黎世联邦理工学院计算机科学系; 2011年。[11] 放大图片创作者：Krishnamachari B，Deborah E，Wicker S.数据聚合对无线传感器网络的影响。2002年第22届IEEE分布式计算系统国际会议。p. 575-8[12] Intanagonwiwat C，Estrin D，Govindan R，Heidemann J.网络密度对无线传感器网络数据聚合的影响。2002年第22届IEEE分布式计算系统国际会议。p. 457-8[13] LeeE，Park S，Yu F，Kim S. 无线传感器网络中支持移动用户的多静态sink通信模型与协议。IEEE Trans ConsumElectron2011;56：1652-60.[14] Lee E，Park S，Lee J，Oh S，Kim S.多静态接收器无线传感器网络中支持远程和移动用户的新型服务协议。无线网络2011;17：861-75.[15] Chatzigiannakis I，Kinalis A，Nikoletseas S. 无线传感器网络中数据收集的汇聚点移动协议。载于：移动性管理和无线接入国际研讨会论文集，MWAC '06; 2006年。p. 52比9[16] 张文辉，李文辉，李文辉.在多跳无线传感器网络中部署多个sink。IEEE International Conference on Pervasive Services，2007。p. 55比63[17] 放大图片作者：Kristan MI，Gansterer WN，Haring G.静态与移动汇点：无线感测网路基本参数对能量效率的影响。Comput Commun2013;36：965-78.[18] Kosar R，Ersoy C.无线传感器网络中用于边界监视的三维地形上的汇点放置。Eng Appl Artif Intell2012;25：82-9.[19] Younis M，Akkaya K.无线传感器网络节点布局策略与技术综述。Ad Hoc Netw2008;6（4）：621-55.[20] Krishnamachari B，Estrin D，Wicker S.无线传感器网络中以数据为中心的路由建模。IEEE信息系统2002;2：39-44.[21] 唐J，郝B，森A.大规模无线传感器网络中继节点配置研究。 Comput Commun 2006;29（4）：490-501.[22] Kim H，Seok Y，Choi N，Choi Y，Kwon T.无线感测网路中最佳多汇点定位与能量有效路由。In：信息联网。宽带和移动网络的融合。Berlin，Heidelberg：Springer. p.264比74[23] 林旭，李晓，李晓，等.无线传感器网络中的选播算法研究.北京：清华大学出版社，2001. IEEE/ACM传输网络（TON）2007;18（2）：515-28。[24] Bondy JA，Murty USR。在：图论。数学研究生教材，第244卷。New York：Springer;2008.[25] Qualnet模拟器6.0.得web.scalable-networks.com余弦值.
我的内容管理
展开
