埃及信息学杂志（2011） 12、83 - 93开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章一种异构传感器网络Salah Abdel-Mageid*，Mohamed Zaki系统和计算机部，埃及爱资哈尔大学工程学院收稿日期：2010年12月17日;修订日期：2011年4月7日;接受日期：2011年2011年5月17日在线提供摘要异构传感器网络（HSNs）由于其在不显著增加成本的情况下延长网络寿命和可靠性的能力，近年来已经变得越来越熟悉。在大规模应用中部署传感器节点（即，战场和环境监测）需要分散的解决方案。在本文中，我们提出了一种新的分散的方法，使我们能够考虑传感器节点的异构特性在自适应重定位策略中，设计了新的几何方法来完美地处理最异构的传感器特性。仿真结果表明，该方案在较少的轮数内以最小的能耗和最少的计算量获得了较高的覆盖性能。性能比较也被引入到研究如何设计的参数影响网络的性能方面的网络成本，覆盖增强，和总能耗的计算复杂度和平均移动距离衡量©2011计算机和信息学院，开罗大学。由爱思唯尔公司制作和主持All rights reserved.1. 介绍无线传感器网络（WSNs）由测量、处理和通信模块组成，主要用于在小规模应用中观察事件和现象并作出反应[1然而，移动传感器节点（例如，昂贵的节点包含移动性和位置查找部分）来促进与大规模应用一起工作，作为环境监测和战场[4，5]。最近，*通讯作者。电子邮件地址：smageid@azhar.edu.eg（新加坡）Abdel-Mageid）。1110-8665© 2011计算机和信息学院，开罗大学。制作和主办Elsevier B.V.保留所有权利。开罗大学计算机和信息系负责同行审查。doi：10.1016/j.eij.2011.04.002异构传感器节点建议增加网络寿命和可靠性。此外，异构节点的网络成本比被迫选择每个节点移动的网络更便宜，特别是对于大规模应用。然而，异构节点的优化部署是我们工作的目标。针对移动传感器网络提出了许多解决方案。例如，势场势场的概念不能完全适用于异质节点。大多数部署的节点是移动的，它们具有相同的感知和通信范围。其实有关键词异构传感器网络自适应重定位;扫描半径;三角剖分制作和主办：Elsevier84S. Abdel-Mageid，M.Zaki在感测范围和通信范围之间没有任意关系，其中通信范围通常被选择为感测范围的两倍。作者在[9]和[10]中利用了著名的几何解Voronoi图，并介绍了两种利用移动支持中的异质性的解决方案，其中考虑了移动和静态传感器的存在以节省网络成本。然而，该解决方案受到Voronoi图的限制，Voronoi图在相同的传感和通信范围内工作。相应地，该解决方案受限于部署异构节点。本文介绍了一种有效的部署异构传感器节点的大规模应用的策略。设计适当的几何解来处理传感距离和通信距离之间的任意关系，以发现覆盖间隙并近似绘制其边界。一些静态节点被动态地选择来监督那些代表间隙边界的多边形各种公告用于在节点之间进行通信。例如，引线/引线公告在引线之间用于交换不完整多边形的边以构造完整多边形。此外，所提出的解决方案使移动传感器能够接收来自领导者的信息，并选择最佳位置进行移动，从而达到网络要求。在这项工作中，提出了一个模拟工具来衡量所提出的策略的有效性。第二部分简要介绍了相关的工作.第3节介绍了我们的工作，包括假设和建议的几何基础。第4节讨论了拟议的搬迁战略。第5节详细描述了拟议战略的基本操作性能比较和仿真结果将在第6节中介绍，以评估所提出的策略的设计参数。第七部分总结了本文的工作，并对今后的工作进行了展望.2. 相关作品在过去的二十年里，在移动无线传感器网络的部署和配置领域进行了大量的研究工作。一些解决方案已经基于不同的优化技术，如圆形包装，遗传算法和小规模传感器网络的群算法[11这种解决方案具有多项式复杂度（即，二次或更大）;因此，需要集中的强大节点。这样的解决方案是适合于小规模的应用程序，因为它们的运行时间明显影响部署的传感器节点的数量另一方面，已经提出了一些用于大规模应用的解决方案。例如，Howard等人[6]开发了一种部署框架，其中传感器位置是根据假定存在于传感器之间以及这些传感器与场中障碍物之间的势场确定的。假设所有传感器都是移动的并且具有相同的特性，这样的框架改善了覆盖范围;然而，它不能完美地适用于不同的感测和通信范围。此外，网络的连通性始终无法保证，并且在每个传感器达到静态平衡状态之前，可能的运动振荡损失更多的能量。作者在[7]和[8]中提出了一种聚类技术，用于具有相同特征的移动传感器，其中clust-ter heads收集有关其集群中所有设备位置的信息。簇头通过应用势场方法来确定其簇中每个传感器的新位置，即，虚拟力，描述在霍华德等人[6]。这种解决方案避免了振荡运动，其计算传感器的最终目的地。所有的计算都假定由簇头进行，这需要具有额外计算能力的强大传感器。此外，这样的工作具有传感器特性的相同限制。Wang等人[15]介绍了避免振荡运动的其他方法。介绍了VEC算法，该算法使用虚拟力的概念，并利用Voronoi图消除振荡运动。Voronoi单元的计算能够在没有发现覆盖改善时防止传感器移动;然而，覆盖性能是有限的在Voronoi布局的基础上，提出了VOR和Minimax两种不同的思想，从而改进了覆盖率。这样的工作假设所有的传感器都是移动的，具有相同的特性。事实上，当移动/静态传感器成本比增加时，网络成本也会增加。因此，提交人在[9]建议部署静态和移动传感器的组合，以节省网络成本。移动传感器根据Voronoi图移动到覆盖间隙。这样的工作可能会消耗更多的能量，传感器移动到几个位置，直到到达最终位置。因此，在[10]中增强了此类工作，其中使用一种动态然而，这种解决方案不能应用于异构传感器，特别是对于不同的传感范围，因为Voronoi图作为一种几何算法是针对相同的站点设计的。本文提出了一种新的低功耗异构传感器的几何框架，以提高覆盖性能，以最小的能量损失。所提出的框架设计轻量级的几何算法是适当的工作与低功耗节点有限的资源。此外，由于减少了传感器节点之间的消息数量，通信成本在我们的策略中是明显可以接受的。此外，由于选择了合适的移动传感器来修复覆盖间隙，因此消除了平均移动距离。唯一的工作，据我们所知，解决轻量级的几何算法部署异构传感器是我们在本文中的结果3. 预赛3.1. 假设给定一个目标场，其中数千个异构传感器随机分布在大规模区域中。传感器i的感测区域近似为半径为ri的圆，表示其感测范围。每个传感器可以通过GPS服务来确定其当前位置，或者基于定位算法来确定其当前位置，即，[16、17]。该信息可以与传感器通信范围内的所有其他传感器共享。此外，在必要时可以共享所有其他传感器特性。一种异构传感器网络的自适应重定位策略85我J2ridjJ. y-y3.2. 技术预备：圆在这项工作中，一个圆的中心是一个传感器节点，其半径代表其传感范围。当一些传感器节点彼此靠近时，它们的感测区域可能重叠。由于感测区域由圆圈表示，因此这些圆圈可以重叠绘制。一个圆可以被一个或多个圆重叠，从而产生相交弧。相交弧是圆周长中被其他圆区域覆盖的部分。一个圆的周长中没有被任何其他圆覆盖的部分称为暴露弧。在这个技术初步的想法是提出一个合适的解决方案来计算圆的暴露弧信息。在极坐标系中，根据圆心及其端点确定暴露的弧。该算法的输入是一组相交圆弧。因此，最初确定相交弧。如图1所示，两个圆Ci和Cj重叠，其中它们的半径分别为ri和rj由Cj引起的Ci的交弧是从pj到qj在逆时针方向上画出的弧。相交弧首先，确定点pj的极角h（pj）角度uj可以根据定律几何地确定，余弦（毕达哥拉斯定理）在ri，rj和dij方面如下：相交弧创建端点类，其属性为端点ID、极轴角度、相交弧ID和状态。status属性用于显示端点是下端点（pj）还是上端点（qj）。所有端点都存储在优先级队列中，其中点的优先级由最小角度确定，这意味着最高优先级点具有最小角度，范围从0到360。提出了一种确定曝光弧的半径扫描操作 如图 在图2中，假设四个圆与当前圆重叠，其中所得到的相交弧由虚线弧表示。在扫描半径操作中，扫描半径从优先级队列中的第一个点开始扫描圆周。当访问第一个元素p1时，其中p1表示弧1的下端点，弧1被存储到列表S中。然后，分别访问q4和q1在点q1，弧1从S中移除，然后列表变为空。空列表表示发 现 了 暴 露 弧 ， 则 q1 是 该 暴 露 弧 的 下 端 点 。FindExposedArcs算法描述如下：.r2，d2-r2！而且，角度uj基本上可以根据两个圆的中心来确定。/j/cos-1J Ixj-xið2Þ因此，极角h（p，j）确定如下：hpj180-/j/j2½0;360]3第二端点qj的极角确定如下：hqjhpj2/2½0;360]4Eqs。对于与当前圆C i重叠的每个圆C j，重复（1）图1传感器（Si）被传感器（Sj）覆盖。当访问弧2的下端点p2时，将p2作为暴露弧的上端点，然后将弧2存储到S中。然后，访问点q2，当q2是弧2的上端点时，弧2从S中移除，然后队列再次变为空。因此，又发现了另一条暴露弧，其下端点为q2当p3为算法 查找暴露弧（L）输入.（x，y）点的集合L表示传感器输出.一组暴露的弧属于一个圆 c碰撞并存储在队列Q1.确定相交弧2.初始化空优先级队列PQ。接下来，将相交弧端点插入PQ中，其中PQ从最小的低点开始，并以起点结束;每个端点存储从自身开始和/或结束于自身的3.初始化一个空列表S4.初始化空队列Q5.访问=false6.当PQ不为空时，DO7.p= PQ中的最高优先级终点8.从PQ中删除最高优先级端点9.如果未访问，则10.温度=p11.访问=true12.HandleEndpoint（p）13.末端回路端PROCEDURE HandleEndpoint（p）1.如果p是上端点，则2.如果列表S不为空，则3.如果I4.清除Q5.否则从列表S中删除I6.如果列表S为空，则7.将E'加8.ELSE交换（当前Q，E9.如果p是下端点，则10.如果Q中有E11.设p为E'的上端点12.将I'插入结束程序uj<$cos-1PJRJCj（xj，RiDJ拉吉拉吉（p）JCi（xi，QJð1Þ86S. Abdel-Mageid，M.Zaki算法ARS（）开始1.Announcement_1（帧（传感器k））2.为传感器k3.e（k）= SweepRadiusOperation（List_（k））4.T（k）= Sum（e（k））5.IFsensor（k）.isMobileTHEN6.A（k）=布尔多边形运算（列表1）7.Announcement_1（frame（static_sensor i），frame（mobile_sensorj））在静态传感器（i）处8.为收集的Ti创建列表T，为收集的Aj和Locj创建列表A9.如果Ti是{列表T}的最大值，则10.静态传感器（i）.Leader = True11.ELSE静态传感器（i）.Leader=假12.Announcement_2（帧1（leader r），帧（sensor i））;在引线传感器（右侧）13.为收集的Er创建列表E，为收集的引线Lr创建列表L，为完整的多边形创建列表14.Pr =创建多边形（列表E）15.Announcement_3（frame（leader r））;//发送不完整的多边形16.为收集的P创建列表P17.如果E（Pr）是E（P）的最大值，则18.将Pr附加到Pr19.为Pr的中点创建列表M，为移动传感器-中点对应创建20.M =三角测量（Pr）21.配件（选定（M）、Aj、Locj）22.Announcement_4（frame 2（leader r））;//发送选定的M和移动传感器在移动传感器处（j）23.为每个新职位创建列表F，并从领导者r24.如果F.Score（r）是最大F.Score并且connected_after_move= true，则25.移动到F位置（r）端年q1p2年q4p1Q2年q3p4p3图2扫描半径操作。其中p3是弧3的下端点，p3作为新暴露弧的上端点，然后将弧3存储到S. 当点p4被访问时，弧4被存储到S中。当q3被访问时，弧3从列表中删除。此时，q3不能开始新的暴露弧，因为列表S不是空的。最后，扫描半径重新访问p1并终止操作。扫描半径操作的时间复杂度详细说明如下。第一步，如第（1）行所示，确定当前圆的相交弧。由于交叉弧的总数是d，这样的步骤的时间复杂度是O（d）。该算法将相交 弧 每 个 端 点 从 PQ 弹 出 ， 复 杂 度 为 O （ 1 ） ， 并 由HandleEndpoint过程处理，复杂度为O（1）;因此整个循环的复杂度为O（2d），如第6行到第13行所示。因此，扫描半径操作的总复杂度是O（n），其中n是重叠圆的数量。4. 适应性迁移策略提出了自适应重定位策略（ARS），以有效地部署异构传感器用于大规模应用。异构传感器的特性可能不同，例如传感和通信范围，剩余能量;此外，它们可以是静态的或移动的。ARS策略设计了一个几何模型，该模型反过来完美地描述了通过目标场的覆盖间隙提出的解决方案主要是基于四种类型的通知规划传感节点之间的通信。(a) 单向传感器/传感器通告用于使每个传感器能够向其通信的邻居发送广播消息。该消息携带传感器ID、当前位置、移动性状态、感测范围、通信范围和剩余能量水平。当传感器从其通信的邻居接收到这样的通知时，邻居信息被登记在其邻居列表中。(b) 双向领导者/传感器通告用于使领导者能够向其携带传感器ID和新状态的邻居作为领导者。邻居可以是其他领导者或普通传感器。当相邻领导者j从当前领导者i接收到该广播消息时，领导者j将领导者i信息插入到领导者组表中。另一方面，当普通传感器接收到来自一个或多个领导者的这种类型的通知时;因此， 传感器通过一个单播消息对最近的领导者进行应答，(c) 单向领导者/领导者通告用于使领导者能够根据其领导者组表向其他领导者发送多播消息。该消息携带领导者ID及其不完整多边形当一个领导者从不完整多边形接收到来自其他领导者的信息时(d) 单向领导者/移动通知用于使领导者能够向携带领导者id、目标位置和新分数的移动传感器组发送单播消息。当移动传感器从一个或多个领导者接收时，获得最高分数的选择选择移动。自适应重定位策略算法描述如下：一种异构传感器网络的自适应重定位策略87最初，如第（1-因此，传感器确定交叉弧，如上所示，以创建来自扫描半径操作的暴露弧的列表（e）。预计这种操作运行得很快，因为当数千个传感器随机部署在监测场中时，重叠感测区域的最大数量约为几十个或更少。暴露弧的存在表明传感器被未定义的间隙区域包围。确定传感器k的暴露弧的总长度T（k当传感器是静态的时，发送携带传感器id和T（k）的通知当传感器移动时，执行附加任务。移动传感器通过考虑其邻居的位置来执行布尔多边形操作，稍后详细讨论，以确定由该移动传感器唯一监督的区域，该区域表示其当前得分。之后，移动传感器发送携带传感器id、T（k）及其当前分数的通知。而静态传感器，如第（8-静态传感器k将其总暴露弧长度T（k）与列表T进行比较。当一个传感器k发现T（k）是最大值并且它有足够的剩余能量时，它被指定为领导者。领导者是一个静态传感器，执行额外的计算。在领导者开始其任务之前，执行第二通告，其中领导者向其邻居发送携带传感器id和领导者状态的广播消息。传感器可以从多个引导者接收广播消息;因此，传感器选择最近的引导者以向该引导者发送单播消息，该单播消息一个传感器只发送给一个领导者，由一个领导者监督，节省了通信和计算成本。如第（13-22）行所示，leader执行其任务，其最初创建三个时间表。第一个列表Leader Group（L）存储其他通信的leader。第二个列表，暴露弧每个暴露的弧被转换为边（线段作为一阶近似）。然后，领导者执行多边形构造操作，稍后将详细讨论，以从边创建完整的多边形。当一个完整的多边形被构建时，它被存储在第三个临时列表中。另一方面，这种操作可能会从已知的边构造不完整的多边形。对于相邻的引线，缺失的边是已知的;因此，引线被协作以将不完整的多边形转换为完整的多边形。创建附加列表来存储不完整多边形这种通告是多播消息，其中领导者向领导者组（L）发送携带传感器id及其不完整多边形的信息的消息。当一个领导者从其他领导者接收时，它试图构建完整的多边形。但是，在将此类多边形追加到多边形列表之前，引线会检查多边形边的所有者。当引线发现它有最大数量的边时，该多边形被附加到它的多边形列表中。然后，每个引线执行三角测量操作，稍后将在详细信息，将每个间隙多边形划分为三角形，并在其中创建附加列表以存储每个三角形的中点。我们的解决方案旨在将移动传感器移动到适当的中点。事实上，中点的数量通常大于移动传感器的数量。因此，选择大面积的三角形以优化中点的数量。最后，领导者执行稍后详细讨论的拟合操作领导者执行最后的通告，其中单播消息被发送到携带领导者ID、新分数和新位置的所选择的移动传感器。如行（23-25）所示，移动传感器检查网络连通性，即，可以使用宽度搜索算法[18]，假设它将离开该区域，通过它的区域。当连通性得到保证时，移动传感器检查从领导者接收的请求。移动传感器可以从多个领导者接收。移动传感器创建一个列表来存储接收到的分数并检查最大值。最后，移动传感器移动到获得最高分数的选定位置。完成这一轮后，覆盖率表现明显提高。自适应重定位策略可以执行一个或两个其他回合以略微增加覆盖性能。在下文中，描述了所提出的策略的基本操作。5. 拟议战略5.1. 布尔多边形运算布尔多边形运算应用于移动传感器以确定其分数。例如，移动传感器S1的感测区域由虚线标记并且与异构传感器S2、S3和S4的三个感测区域重叠，如图3a所示S1的当前分数由S1唯一覆盖的虚线区域表示。该面积确定如下。所有传感器然后，根据2D多边形算法[19]实现布尔多边形运算，以确定表示两个六边形之间的并集区域的顶点。布尔运算包括多边形的并、交、差运算。布尔运算的时间复杂度是O（（p+k）logp），其中p是两个多边形顶点的总数，k是结果多边形的顶点数。对所有S1邻居递增地执行并集运算以获得表示所有邻居的感测区域的并集的多边形移动传感器S1的感测区域用A标记，其中圆形区域近似为六边形形状。执行布尔差分运算以确定表示A和A之间的差异区域的顶点。B.用C标记的差异区域代表S1电流分数。如上所示，两个六边 形 顶 点 的 总 数 因 此 ， 这 种 操 作 的 总 复 杂 度 为 O（（n+1）（p+k）logp），其中n表示其重叠的邻居的数量。实际上，重叠邻居的数量最多在几十个左右。 因此，这种操作的总复杂度是88S. Abdel-Mageid，M.Zaki--BB一C一S3S2S4S13-A：真实感知区域。3-B：近似感测区域。图3二维多边形的布尔运算时间复杂度为O（1）预期移动传感器可以以低计算如此快速地确定其当前分数布尔多边形运算也适用于领导者，其中领导者需要估计选定中点（p）处的预期分数。领导者在所选中点（p）处假设移动传感器（i），并发现预期与其感测区域重叠的传感器。领导者执行布尔多边形运算，如上所示，以确定移动传感器的新分数（i），当决定移动到选定的中点（p）时。引线对所有选定的中点重复这样的操作。假设由领导者计算的中点的最大数目是m，并且由该领导者发现的移动传感器的最大数目是n，则在领导者处的这种操作的总复杂度是O（nm）。预计项（nm）的最大值最多约为几百。5.2. 多边形构造操作多边形构造操作在引线处执行，以从尝试构造完整多边形的接收到的暴露弧中受益。最初，暴露的弧被转换成线段（边），因为一阶近似可以方便计算。边存储在双向链表中，以提供线性搜索。中的节点双向链表具有前指针和后指针。前指针用于指示下一个边缘，而后指针用于指示上一个边缘。是容易确定当前边的下一个边，当前边的上端点是下一个边的下端点。类似地，确定前一边缘。当没有节点被指定为当前节点的下一个或上一个节点时，前指针或后指针都以NULL值进行设置。这种操作搜索双重链接，以最初找到不完整的多边形。当到达具有NULL后端的第一个节点时，该节点被插入到第一个不完整的多边形数据中并从双向链表中删除。根据当前节点的前指针，分配下一个节点，然后插入到第一个不完整的多边形数据中，并从列表中删除。当到达一个具有NULL前端的节点时，构造第一个不完整的多边形结构。只要列表中有一个后面为NULL的节点，就可以发现一个不完整的多边形，如上所示。当不存在具有NULL后部的节点时，多边形构造操作开始寻找完整的多边形。从第一个节点开始，确定下一个节点，直到再次到达第一个节点，构造第一个完整的多边形，依此类推。完整的多边形存储在P列表中，不完整的多边形存储在P列表中。当引线从其他引线接收到不完整的多边形P时，也会在引线处执行多边形构造操作。领导者创建一个具有不同结构的双向链表，其中节点数据包含不完整的多边形信息。前指针和后指针最初为NULL。当不完整多边形的端点等于另一个不完整多边形的端点时，前指针或后指针被修改。然后，如上所述，搜索双向链表以找到新的完整多边形。可以将新的完整多边形中的某些多边形添加到引线信息中，以避免在其他引线处出现重复的多边形。当发现一个完整的多边形时，lea- der决定它拥有多少条边。当引线具有最大数量的边时，完整的多边形存储在P中。多边形构造操作的时间复杂度为O（n），其中n表示最大边数，因为这种操作依赖于双向链表结构。5.3. 三角测量操作三角测量操作在引导者处执行，以操纵间隙多边形，试图分配移动传感器的最佳位置，从而覆盖间隙。这种操作执行单调多边形三角剖分算法[19]，其时间复杂度为O（milogmi），其中mi是ver-n的数目。gap polygon（i）的定义每一个有mi个顶点的多边形都是di-（mi2）三角形。假设间隙多边形的数量为g，总边数为E。让平均数顶点为V，则E= gV。如果对一个多边形进行三角剖分的时间复杂度为O（VlogV），那么对g个多边形进行三角剖分的总复杂度为O（gVlogV）或O（E（logElogg））。间隙多边形的数目与边的总数相比是很小的数目。因此，这种操作的时间复杂度是O（ElogE）。与上述操作相比，这种操作的复杂度一般从O（n）的数量级增加到O（nlogn）的数量级。在将间隙面划分为三角形之后，确定每个三角形的中点并将其存储在中点列表(M)尺寸m通常，间隙多边形可以包含导致更多中点的短边。搬家是个糟糕的选择一种异构传感器网络的自适应重定位策略89ð Þ ¼因为移动传感器的数量可能不足;此外，这导致移动传感器部署的最差利用率。因此，确定总多边形面积以估计所需的移动传感器的数量（n），其中它们的感测范围被选择为给定异质传感器的感测范围的平均值。通常需要移动传感器的数量（n）小于中点的数目（m）。三角剖分操作试图通过选择具有最大面积的三角形的中点来将m减少到n。因此，中点列表大小减小到n。很明显，中点列表中的每个元素都有几个属性，中点位置和不同的新分数取决于部署的异构传感器的数量类型，如第5.1节所述5.4. 嵌合操作设计了一个重要的参数，分数与距离比（SDR），并在方程中公式化。（5）使领导者能够将最好的移动传感器安装到适当的中点。SDR定义为相对分数（Sr）除以相对距离（Dr）。SDR i;mSri;mDr i; m其中，Si;mS新i;m-Sci;和Di;mDi;mRR重复。否则，当这些条件中的一个不满足时，这种操作发现当前移动传感器不适合当前中点位置，并移动到列表中的下一个元素，等等。通常，当移动传感器的数量小于移动传感器的数量或没有移动传感器满足这样的中点要求时，一些中点可能被拒绝覆盖。假设由领导者计算的中点的最大数目是m，并且由该领导者发现的移动传感器的最大数目是n，则在领导者处的这种操作的总复杂度是O（nm）。预计项（nm）的最大值最多约为几百，如第5.1节所述。在自适应重定位策略中，部署的传感器根据其特性执行不同的操作。例如，移动传感器执行扫描半径和布尔多边形操作。另一方面，静态传感器还执行扫描半径操作，当选择静态传感器作为引导线时，将执行其他操作，例如多边形构造、三角形和拟合。时间复杂度在三角测量操作中更大，其达到O（ElogE），其中E表示在领导者处收集的边缘的最大数量，并且在布尔多边形和拟合操作中也更大，其达到O（nm），其中n表示由领导者发现的移动传感器的最大数量，并且m表示由该领导者计算的中点的最大数量事实上，E近似于（nm）的数量级;因此，的新ði;mÞ鲁里什这是一个复杂度为O（nlogn）的问题。表示在引线处收集的最大边数参数Snew（i，m）是移动传感器（i）在中点位置（m）处的新分数，Sc（i）是移动传感器（i）的当前分数，D（i，m）是移动传感器（i）的当前位置与中点位置（m）之间的距离，并且r（i）是移动传感器（i）感测范围。当SDR比为负时，这意味着移动传感器（i）在（m）处的新得分小于其当前得分。此外，在这种情况下，移动传感器移动到（m）导致覆盖性能下降。否则，当SDR比率为正时，给出最高SDR比率的中点位置（m）被选择为移动传感器（i）的新位置事实上，当中点位置（m）被选为移动传感器（i）的最佳位置时，移动传感器（i）不必是中点位置（m）的最佳传感器。因此，拟合操作就是为解决这一问题而设计的.创建FIT列表以建立移动传感器和中点的对应关系，FIT列表大小为（i·m），其中i表示移动传感器的数量，m表示中点的数量。FIT列表的每个元素由五个属性组成：{SDR，移动传感器id（i），中点位置（m），连接状态（c），移动传感器能量水平（e）}。这样的元素存储在优先级队列中，其中优先级是属性SDR;最高优先级的元素具有最大的分数与距离比。拟合操作线性搜索优先级队列以将最佳移动传感器（i）拟合到中点位置（m）。在优先级队列的每个元素处，检查三个属性：（1）SDR应该是正的，(2)连通性是有效的;（3）移动传感器的能量水平适合移动。当这些条件满足时，当前移动传感器（i）和当前中点位置 （米） 是 标记 作为 访问 到 避免这种复杂性非常适合分布式计算。此外，所提出的策略被认为是一个分布式的解决方案与适当的通信成本。通过与现有分布式移动传感器策略的性能比较，表明ARS策略能够有效地实现高覆盖率，同时具有较小的平均移动距离和适当的通信开销。6. 仿真结果和性能比较用C#语言开发了一个仿真工具来实现所提出的几何算法，并检验了上述所提出的方案（ARS）的有效性。这种仿真工具被用来执行几个实验，以了解异构传感器网络的行为。在这些实验中，为简单起见，考虑了在正方形场中的传感器部署。场地面积为60· 60米，总面积为3.6平方公里。三种不同类型的传感器，传感范围为4，5，6米，用于匹配 其 他 当 前 的 传 感 器 原 型 ， 如 Smart Dust （ UCBerkeley ），CTOS dust 和Wins （Rockwell ）[20] 。根据[21]，当前通信范围等于20 m。图4示出了当使用来自每种传感器类型的30个传感器时工具界面的不同视图， 图图4a示出了每个传感器的感测足迹作为初始位置，其中虚线感测足迹表示移动传感器，网格感测足迹表示在第一轮中被选为领导者的静态传感器。虽然图图4b示出了由引导传感器构造的间隙多边形，其中具有多个边缘的多边形指示其是由来自多个引导的集合信息构造的。90后Abdel-Mageid，M. Zaki图4模拟工具界面的不同视图图4c示出了三角测量过程的输出和所选择的中点。移动传感器的最终位置如图所示。 4d，覆盖性能明显提高。所提出的模拟器可以计算的覆盖性能的逻辑划分成小块的监测领域。部署的传感器覆盖的块的数量表示覆盖区域。当一些传感器被选择为移动时，实现一定覆盖所需的传感器的最小数量减少第一组实验的实施，以显示之间的关系所需的传感器的最小数量，以实现一定的覆盖范围的监测领域，和移动传感器的数量。最初，如上所述选择三种类型的传感器，并且当所有传感器都是静态和随机部署时，实现90%、95%和97.5%的覆盖率所需的传感器的最小数量分别为115、150180个传感器假设有10%的移动传感器，所需的异构传感器的最小数量达到100，124和140传感器，如图所示。 五、因此，当所包括的移动传感器的百分比增加时，实现一定覆盖所需的传感器的最小数量减少。网络成本取决于移动和静态传感器之间的成本比。当这个比例接近1时，最小的网络成本发生在100%移动传感器。事实上，移动传感器的成本仍然高于静态传感器的成本;相应地，当成本比增加时，网络成本随着移动传感器百分比的增加而增加。此外，选择所有传感器静态不能实现最小的网络成本，因为需要更多的传感器来实现优选的覆盖百分比。因此，移动传感器的百分比年龄的选择一种异构传感器网络的自适应重定位策略91覆盖率200 9690%覆盖率95%覆盖率18097.5%覆盖率94160921409012088100868084600% 10% 20% 30% 40% 50%移动传感器图5增加移动传感器的影响。820% 10% 20% 30% 40% 50%移动传感器(a) 覆盖性能移动/静态传感器成本比。在覆盖改善率、平均移动距离和设计通告成本等网络指标下，研究了该策略的性能。移动传感器的百分比是随机选择的，从10%到50%不等，增量为10%。应用另一组基于不同初始分布的实验，然后考虑平均结果。最初，我们选择随机部署每种传感器类型的30个传感器，总共90个传感器。这组实验的平均初始覆盖率约为83.84%。在ASR策略中，提出了三种拟合方法来评估分数距离比（SDR）参数及其在提高覆盖性能方面的作用。第一种方法，FitDis，是基于最短距离进行拟合。这样的方法43.532.521.510.500% 10% 20% 30%移动传感器的百分比FitSDRFitCovFitDis40% 50%当他们决定哪一个移动邻居时，最接近于某一中点。此外，拟合- Dis方法可以应用于它们从多个领导者接收的移动传感器本身;因此，它们可以选择最近的中点来移动。第二种拟合方法，拟合-覆盖，是将具有已知分数的移动传感器拟合到具有较高分数的中点。最后一种拟合方法FitSDR是根据分数与距离的比值将移动传感器拟合到中点。FitCov和FitDSR都适用于领导者和移动传感器，类似于FitDis方法。如下所述，在不同的场景下测量网络性能。图6示出了当领导者执行FitDis方法时的覆盖性能和平均移动距离。如图6a所示，当移动传感器的百分比增加时，覆盖性能增加。当在移动传感器上执行FitSDR或FitCov以选择其目标时，覆盖性能优于FitDis的覆盖。在50%的移动传感器中， FitSDR 和FitCov 的覆 盖率达 到95% ， 而FitDis 达到93.9%。然而，与其他方法相比，FitDis节省了运动能量1.7650%移动传感器时，如图6b所示。此外，移动传感器处的FitSDR比FitCov方法节省更多能量，即，2和2.2米，分别为50%的移动传感器。虽然FitCov方法执行更大的移动距离，但这种增量很小，因为移动-（B）平均移动距离图6领导者应用FitDis方法时的网络性能最初在引线处控制，应用FitDis方法图7显示了领导者执行FitCov方法时的覆盖性能和平均移动距离。如图7a所示，也在移动传感器处应用FitCov实现了最高的覆盖百分比，即，在50% 移动传感器时为96.2%，而应用FitSDR或FitDis会导致覆盖性能降低，即，在50%移动传感器时，分别为95.3%和95.4%。FitCov、FitSDR和FitDis在50%移动传感器下的平均移动距离分别达到6.3、5.3和5米。虽然结果表明，与应用FitDis的结果相比，在领导者处应用FitCov的覆盖性能得到了相当大的改善，但平均移动距离通过增加移动传感器的百分比而增加，如图7b所示。因此，当移动传感器的数量增加时，它们移动更长的距离以寻求最佳得分，而不管它们的能量约束。最后一组实验用于测量在领导者处应用FitSDR时的网络性能，如图8所示。结果表明，在leaders应用FitSDR方法可以在网络性能参数之间取得平衡。FitSDRFitCovFitDis所需传感器的最小数量平均移动距离（m）FitSDRFitCovFitDisFitDSRFitCovFitDis平均移动距离（m）覆盖率92 S. Abdel-Mageid，M. Zaki98 9896 9694 9492 9290 9088 8886 8684 84820% 10% 20% 30% 40% 50%移动传感器的百分比(a) 覆盖性能7820% 10% 20% 30% 40% 50%移动传感器(A) 覆盖性能43.56352.54231.52110.500% 10% 20% 30% 40% 50%移动传感器(B) 平均运动距离图7在leaders应用FitCov方法时的网络性能00% 10% 20% 30% 40% 50%移动传感器的百分比(B)平均运动距离图8在leaders应用FitSDR方法时的网络性能如图8a所示，覆盖性能近似于在领导者处应用FitCov方法的结果，即，在移动传感器上，FitSDR、FitCov和FitDis分别为95.8%、95.6%和95.5%。虽然如图8b所示的平均移动距离近似于在领先者处应用FitDis方法的结果，即，对于FitSDR、FitCov和FitDis，移动传感器处的50%移动传感器分别为1.8、1.9和1.8 m。如上所述，在50%移动传感器时，最大覆盖百分比为96.2%，最小平均移动距离为1.76m。为了总结结果，我们将50%移动传感器的结果相对于最大覆盖百分比和最小平均移动距离进行归一化，如表1和表2所示。从这些表中，我们可以很容易地发现，FitSDR方法更适合应用于领导者和移动传感器。最后，将监测区域扩展到300· 300 m，总面积为90km2，部署了1800个异质传感器来测量网络性能。当考虑大规模传感器网络时，所提出的策略有效地运行，这给出了相同的覆盖改善率和平均移动距离。表1标准化覆盖率。领导人FitDis菲茨科夫FitSDR移动传感器FitDis0.9760.9920.992菲茨科夫0.98710.993FitSDR0.9860.9900.996表2标准化移动距离。领导人FitDis菲茨科夫FitSDR移动传感器FitDis12.851.02菲茨科夫1.233.581.08FitSDR1.143.031.02对于大规模的传感器网络，FitSDRFitSDRDisCov覆盖率FitSDRFitCovFitDis平均移动距离（m）一种异构传感器网络的自适应重定位策略937. 结论和进一步的工作提出了一种有效的传感器自主部署策略以满足异构性需求。作为这项工作的一部分，轻量级几何算法被设计成能够使一组静态传感器作为领导者来监督被监测场中的覆盖间隙。然后，领导者利用设计的算法选择最佳的移动传感器，使其适应覆盖间隙。所设计的算法实现了一种有效的重新定位方法，该方法在适当的平均移动距离下最大化整体场覆盖。几个模拟实验进行了检查所提出的策略的效率。基于这样的实验结果，所提出的策略自动地增强了在传感器节点处具有最小计算量的领域中的异构传感器分布，即，时间复杂度O（n几个扩展被认为是这项研究，例如，正在努力开发这项工作，以提高设计的算法。进一步的算法精确地构造覆盖间隙的二阶近似，以最大化的覆盖。引用[1] Akyildiz IF，Su W，Sankarasubramaniam Y，Cayirci E.传感器网络综述。IEEE Commun Mag. 2002年：102-14。[2] 张文辉，张文辉，张文辉.无线感测器网路：技术、协定与应用。Hoboken，New Jersey：John Wiley and S
我的内容管理
展开
