CoopSink: 一种提高协作Ad Hoc无线网络能源效率的新技术

可在www.sciencedirect.com在线获取理论计算机科学电子笔记302（2014）29-51www.elsevier.com/locate/entcs协作Ad Hoc无线网络T. F. Neves1 J.L. Bordim2巴西利亚大学计算机科学系巴西巴西利亚摘要协作通信（CC）是一种利用空间分集的技术，其允许多个节点协作地将信号中继到接收器，使得接收器可以组合接收到的信号以获得原始消息。 CC可以与拓扑控制相结合，以较小的增加为代价来增加连通性在能源消耗方面。 本文的工作重点是探索CC，以提高与汇聚节点的连接在adhoc无线网络中。更准确地说，这项工作提出了一种新的技术，命名为CoopSink，它结合了CC和拓扑控制技术，以增加连接到一个汇聚节点，同时确保能源效率的路线。 仿真结果表明，该算法的连通性和路由到汇聚节点的代价都得到了提高到6. 8和2。3倍，分别与其他类似的策略相比关键词：拓扑控制，无线网络，网络协议，协同通信。1介绍Ad hoc无线网络是其中节点可以彼此通信而无需求助于集中式基础设施的网络。这些网络具有大量的民用和军用应用，从战场通信支持、搜索和救援行动到目标监视和跟踪。ad hoc网络中的主要挑战之一是降低能耗，因为这些节点通常由电池供电[2]。由于电池更换在操作期间可能不是可行的选项，因此改进和优化无线网络中的能量消耗的替代方案受到极大关注。这一事实推动了对旨在延长网络寿命的节能策略的追求[25，5]。这些节能建议可以分为两个主要类别：（i）允许节点在活动/空闲操作模式之间交替的技术;以及（ii）允许节点调整其传输功率的技术最近的作品在第一1电子邮件：tfn. cic.unb.br2电子邮件：bordim@unb.brhttp://dx.doi.org/10.1016/j.entcs.2014.01.0191571-0661 © 2014 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。30T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29可以在[34，9，30]中找到。拓扑控制策略属于第二类，并且在文献[22，8]中进行了大量探索。拓扑控制包括允许无线节点选择相邻节点的子集和/或调整传输功率，目的是在保持网络连接的同时降低能耗[7，3，23]。在传统的多跳无线网络中，中间节点相互协作请注意，此过程发生在网络层。另一方面，协作通信（CC）是一种物理层技术，其允许单天线设备通过探索空间分集来受益于多输入多输出（MIMO）系统的一些优点[28]。该技术允许节点改善信号质量和传输范围。在CC中，当源节点发送分组时，源附近的一组辅助节点偷听信号，并且同时将相同信号的独立副本目的地节点然后组合接收到的信号以获得原始分组。最近的工作已经探索了具有拓扑控制技术的CC以减少能量消耗[5]。已经研究了增加网络连接和提高网络寿命的方法[35，33]。然而，据我们所知，没有工作到目前为止，探讨了CC，以增加连接到自组织无线网络中的水槽。由于电池耗尽和节点故障导致的链路故障可能会阻止无线节点到达信宿。在这种情况下，可以探索CC以改善网络连接性，并允许建立到汇聚节点的替代路由。这项工作提出了一种新的技术，名为CoopSink，它结合了CC和拓扑控制在一个ad hoc无线网络，以增加连接到水槽，同时确保能源效率的路线。该提议可以应用于[4]中描述的环境，其中存在配备有用于查询广播的大范围无线电的汇聚节点，并且节点协作以克服链路故障并向汇聚节点报告信息。这种情况类似于亚马逊高塔天文台（ATTO）项目中发现的情况，其目标是在亚马逊森林中间放置一个高高的中心塔，并在较小和战略性放置的传感器的帮助下，获得对二氧化碳，CH4和N20等温室气体来源的可靠估计。所提出的技术已经通过模拟进行了评估，结果证实，CoopSink是能够提高网络的连通性，并提供能源效率的路由到汇。更准确地说，仿真结果表明，连接和路由到sink改善了到6. 8和2。3倍，分别与其他类似的战略相比本文其余部分的组织如下。第二节对拓扑控制和协作通信的相关研究进行了综述第3节描述了通信和网络模型，并正式在这项工作中解决的主要问题。第4节描述了CoopSink协议，第5节给出了仿真结果，将所提出的方案与其他类似和突出的策略进行了比较。第6节结束工作。T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）293162相关作品本节简要回顾了探索无线网络中拓扑控制和协作通信的密切相关的工作。2.1拓扑控制拓扑控制是一种根据特定条件改变网络拓扑结构的技术例如，拓扑控制可用于优化网络功耗，降低路由成本和控制消息的数量，提高吞吐量或满足某些QoS要求[5，15，11]。根据[5]，拓扑控制协议可以分为：（i）集中式;或（ii）分布式。集中式协议认为全局信息是可用的，例如拓扑信息、路由信息、全局存储状态等。然而，即使在全局信息可用的情况下，已经证明以最小的总能量消耗找到强连接拓扑是NP完全问题[6]。在集中式协议中，Ramanathan et al.[27]提出了优化网络连接同时提高网络寿命的替代方案。分布式协议考虑k跳相邻信息，其中k通常为1或2。Li等人[20]提出了一种基于锥的TC算法，旨在优化能耗，同时保持网络连通性。为了实现这一点，每个节点调整其发射功率以覆盖多个相邻节点，条件是它们彼此相距最多α度作者证明，α=5π的度足以保持网络连接，活力文中还讨论了基本算法的几种优化方案，并定义了一种基于信标的拓扑维护协议。 在最近的工作中，Li等人[21]提出了一种局部最小生成树（LMST）算法。LMST的工作原理是让每个节点基于1跳邻居信息构建本地化的MST。最终拓扑的构造使得最大节点度为6。全面的调查可以在[22，14]中找到2.2协同通信（CC）协作通信（CC）是由[19]和[26]引入的允许单天线设备探索MIMO系统的特性的技术在协作通信中，一组节点传输原始信号的独立副本预期接收器获得发射信号的独立版本，这减少了通过多径传播的衰落效应。在这个通信模型中，每个无线节点被假定为传输数据，并作为一个合作代理，中继来自其他用户的数据。CC以前用于能量高效广播[1]，构建连通支配集[32]，路由[17]等应用。CC技术可以分为放大转发和解码转发[19]。在前者中，接收信号的噪声版本的节点放大并中继该噪声版本。然后，接收器将信息32T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29由发送器和中继节点两者发送。当采用解码转发时，中继节点必须在重传之前首先解码信号。由于CC链路区域的成本通常高于传统链路，因此通常采用选择合适节点的方法。在用于识别中继节点的最佳集合的技术中有接收信噪比（SNR）和/或剩余电池能量。本文研究了协作通信中基于接收信号信噪比选择中继节点的解码转发方法该技术要求每个节点具有用于存储数据分组的专用存储器和可以估计每个接收分组的SNR的信号处理器，如[19]中所述。2.3协作Ad Hoc网络中扩展链路覆盖的在文献中很少有作品考虑使用拓扑控制和CC，以提高网络覆盖的ad hoc网络。在[18，31]中研究了使用CC的链路覆盖扩展的可能性。在这种情况下，Cardei等人[5]研究了结合CC的拓扑控制的使用，其目标是以最小能耗获得强连接拓扑作者证明了该问题是NP完全的，并提出了两个局部和分布式算法。这两种算法都将传统拓扑控制算法（没有CC）的结果作为输入。第一种算法使用分布式决策过程，其中每个节点使用最多两跳的邻居信息。第二种算法迭代地分配传输功率的节点，使用一跳邻居信息。Yu等人[33]提出了一种集中式拓扑控制方案，旨在增加网络连通性并降低传输功率。为了最小化协作通信链路（CC链路）的数量并降低传输成本，提出了多项式和指数（但最优）辅助决策算法Zhu等人[35]考虑当使用CC链路时选择能量高效路径的问题本文提出了两种拓扑控制算法来建立保证各条路径能量效率的协作能量空间。这两种算法都可以以分布式或本地化的方式执行。 [33]中的工作重点是保持网络连通性，目标是最大限度地减少全球能源消耗。同样，[35]中的工作侧重于通过选择高效路线来减少在自组织设置中，由于电池耗尽和节点故障导致的链路故障可能会阻止无线节点到达期望的目的地。在这种情况下，CC可以被探索以改善网络连通性并允许建立更高效的路由。这项工作解决了这个问题。据我们所知，这是探索使用CC链路来改善无线自组织网络中到汇聚节点的网络连接的第一项工作T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）2933--3网络模型与问题定义本节首先介绍了CC模型和相应的网络模型，在这项工作中使用。 在第二个时刻，该模型是典型的，这项工作的主要问题是形式化的。本节中定义的模型与[5，33，35]中使用的模型相似。3.1CC模型考虑无线自组织网络，其中每个节点vi可以利用区间[0，PMAX]内的值来调整其传输功率Pi。当P1=0时，节点在传统的协作通信模型中，只有当vi的传输功率满足等式1时，发送方节点vi才能直接与接收方节点vj通信。P i（d i，j）−α≥τ其中：α是路径损耗指数，通常在2和4之间，并且表示信号随着距离增加而衰落的速率;di，j是vi和vj之间的欧几里得距离;并且τ是vj接收到的最小信噪比（SNR），使得vj可以解码信号并获得原始消息。CC利用物理层设计的优势来组合部分信号以获得完整的信息[28]。这样，如果vi与一组辅助节点Hi，j联合发送其信号并且其发送功率之和满足等式2，则可以利用CC实现节点vi和vj之间的通信。在CC中，辅助节点是与发送节点一起协作地对信号进行解调的节点。vk∈vi<$Hi，jPk（dk，j）−α≥τ （0≤Pi≤PMAX）（2）图1a和图1b示出了可以使用CC来增加连接的场景在ad hoc网络中。在图1a中，有三个节点（v1，v2ev3），它们彼此靠近，还有一个远距离节点（v4）。传输半径，即v1的传输功率，使其能直接到达节点v2和v3。节点v2和v3有一个相邻节点，在本例中为节点v1。节点v4在其它节点的无线电范围之外。当采用CC时，节点v1可以选择节点v2和v3作为其助手来向v4发送，即H1，4=v2，v3。 在选择这些节点作为助手之后，v1首先将其数据传输给v2和v3。在第二个时刻，v1和它的助手将相同的数据传输到v4，放大了v1的传输半径。如果在v4中接收到的组合SNR大于τ，则节点能够解码信号并从v1获得原始数据，如图1b所示。当节点v1向其助手节点v2和v3发送其数据时，在第一时刻，v4也从v1接收部分数据。在某些CC模型中，这样的部分数据在CC的第二时刻期间由v4在这项工作中，为了简单起见，这样的部分数据被忽略（如[33]和[35]）。实现CC的物理层技术可以在[13]中找到。34T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29∈∈∈--⊆≤≥∈吉吉˜--(a)（b）第（1）款图 1.一、 （a） 在不同的辐射区域和不同的辐射区域（v 4）内有三个节点（v1 ， v2和v3 ）的情况。（b ） Nodev1usesnodesv2andv3ashelpernodestoincreaseradiorangeetusreachchingnodev4.3.2网络模型考虑具有n个节点的自组织网络，这些节点能够接收和组合与CC模型一致的部分接收数据。网络拓扑被建模为平面图G =（V，E），其中V = v1，v2，.，是无线节点的集合，并且E是通信边的集合。边vi vj E表示节点vi可以直接和/或使用CC向vjN（vi）是vi在其最大传输范围RMAX内的直接相邻集，对于每个vk N（vi），存在Pi PMAX，使得Pi（di，k）−ατ，遵循等式1。换句话说，vi可以直接与它在N（vi）中的邻居通信。每个节点Vi V具有唯一ID并且知道其自己的位置信息。在节点之间交换节点ID和位置信息每个节点Vi V具有唯一的无线电并且依靠电池电力运行。根据前面的信息，我们定义了几个重要的概念，类似于[35]中的概念。定义1（直接边）：直接边v i v j是E中表示节点v i可以直接向节点v j传输数据的边，即当P i ≤ P MAX时，P i使得v i可以达到v j。节点上的水平实线表示直接边。定义2（辅助节点集）：H i，j表示与v j合作通信的v i的辅助节点集。假设所有帮助节点都需要是vi的直接邻居，即H i，j N（v i），其中N（v i）是v i的所有直接邻居的集合。换句话说，N（v i）中的所有元素都是辅助节点候选者。定义3（CC边）：CC边v vj是表示该节点的E的边v i可以通过使用一组辅助节点H i，j来协作地向v j发送数据。波浪水平线用于表示CC边缘。定义4（辅助边）：辅助边是从v i到H i，j中的一个辅助节点的边。例如，在图1b中，节点v1使用节点v2和v3作为辅助节点来创建v1和v4之间的CC边，即H1 ，4=v2，v3，这样，边v1v2和v1v3被认为是辅助边。定义5（网络拓扑）：所有直接边和CC边的并集分别为E和E。类似地，直接通信图和CC通信图分别被定义为G=（V，E）和G=（V，E）。注意T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）2935i、j吉吉.i、j、dE= EE根据记法，注意，ifvivj∈E，ten：vivj=vivjifvivj||是直接边缘;以及如果v i v j是CC边缘，则v i v j=v i v j。˜定义6（直接边权重）：直接边vi vj的权重定义为：w（vivj）=τdα.定义7（CC边缘权重）：CC边缘的权重v vj被定义为：其中：（1）A（1）A（2）A（3）A（4） A（|Hi，j|+1）wCC（Hi，j），- |：是H i，j中元素的个数;|: is the number of elements in H i,j;- w（H）=τ（maxvk∈Hi，jdi，k）−αi：是节点vi的最小能耗与Hi，j中最远的节点通信;- w CC（H i，j）=.Σvk∈viτHi，j（dk，j）−α：节点的最小能耗vi与 vj通信，与 Hi，j注意，根据等式1和等式2，以下关系必须为真以存在CC边缘：max（wd（Hi，j），wCC（Hi，j））≤PMAX在从vi到vj的CC中，节点vi必须首先将其数据发送到它的助手节点在Hi，j中，并且在第二时刻，节点v i和它的助手节点必须同时向v j发送相同的数据。这样，CC边缘的权重由这两个时刻的通信成本之和组成。w d（H i，j）是第一时刻的成本，而w CC（H i，j）是使用CC传输数据的单个节点成本，也就是说，它必须乘以（H i，j+1），也就是说，在v i和v j之间的CC中涉及的节点的数量。 在这项工作中，CC模型被简化，假设vi及其助手节点的传输功率相同。此外，仅考虑每个发送器节点中的功率消耗定义8（有向路径成本）：给定图G=（V，E）中的源节点vi和目的节点vj，当且仅当存在顶点序列时，vi和vjv i，v i1，v i2，.，v ik−1，v ik，v j∈ V，使得：（v i v i1），（v i1v i2），.，（v ik−1v ik），（v ik v j）∈ E.图G中vi和vj之间的有向路径成本定义为：πG（vi，vj）=w（v i v i1）+w（v i1 v i2）+. + w（v ik−1v ik）+w（v ik vj）。36T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29⊆⊆G⊆≤P----也就是说，属于vi和vj之间的路径的所有边（直接边和CC边）的权重之和。G中vi和vj之间的最短路径的成本定义为：min（π G（v i，v j））.定义9（ESF -能量拉伸因子）：设GJ=（V，EJ）是G=（V，E）的子图，EJE，GJeG是连通图。 G j中的一对节点v i和v j相对于G中相同节点的ESF定义为：ρG′（v，v）=min（πG′（vi，vj）），Gijmin（πG（vi，vj））考虑GJ关于G的ESF为：ρ G′ = max ρ G′（v i，v j）.G Gvi，vj∈V也就是说，GJ中V中任何一对节点之间的最大ESF关于G. 图2说明了这一概念。定义10（CE-t-S -协同能量t-Spanner）：设GJ=（V，EJ）是G=（V，E）的一个子图，EJE，G和GJ是连通图。 如果其ESF小于常数t，则G j是关于G的CE-t-S，即：ρ G′≤ t。定义11（COE-t-S -协作定向能量t-Spanner）：COE-t-S是CE-t-S的一种特殊情况。设GJ=（V，EJ）是G=（V，E）的一个子图，EJE，GJ和G不一定相连（与COE-t-S不同）。 考虑一个特定的节点v o∈V和常数t。GJ是关于G和vo的COE-t-S，如果：maxμ（vi，vo）t，vi∈V其中：μ（vi，vo）=0G′最大ρGP（vi，vo），如果存在从vi到vo的路径;000，否则。3.3计算CC成本为了验证所描述的模型，请考虑图1a所示的图形。这是一个有向图G=（V，E），其中V =v1，v2，v3，v4 和E=v1v2，v1v3，v2v1，v3v1。仅作为示例，考虑α=1，τ= 1，R max=R。请注意，α= 1在实际情况中并不实用，但在示例中它使计算更容易。因此，我们可以基于等式1来计算每个节点的最大传输功率Vi∈V：T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）2937uG'（vi，VJ∈⊆2--˜14GG'ViVi(a)（b）第（1）款图 二、（a）图G=（V，E）的例子。（b）图G′=（V，E′），E′≠E的例子。 πG（vi，vj）是图G中vi到vj的最小余弦。一个对G′有约束的非零Svi，vj∈VofG′的ESF相等得到ρG'（vi，vj）=min（πG'（vi，vj））.Gmin（πG（vi，vj））PMAX（dMAX）−α=τ，PMAX（R）−1= 1，P MAX= R.注意，在所提供的设置下，每个节点Vi V具有R的最大传输功率。在G中，节点v2和v3是节点v1的邻居，即N（v1）=v2，v3。这样，节点v1可以选择N（v1）的任何非空子集作为其助手节点，以创建从v1到v4的CC边，即H1，4N（v1），遵循定义2。图1b显示了新的图表，CC边缘从v1到v4。考虑到，对于建议的例子，d12=R，d13=R，d14=2R，d24=1。73R和d34=1。80岁。从等式2，我们可以计算节点v1需要使用节点v2和v3作为帮助节点来达到节点v4的传输功率vk∈v1{v2，v3}Pk（dk，4）−1≥1，=P1（d14）−1+P2（d24）−1+P3（d3，4）−1≥1，1=P1≥1 +1 +的1，2R1、 73R1、 80R=P1≥ 0。612河注意，所有涉及的节点（v1，v2ev3）以相同的传输功率操作，即，P1=P2=P3。因此，在CC的情况下，v 1达到v 4的最小传输功率等于P1=0。612河该传输功率低于先前看到的最大传输功率，其等于P_MAX=R。到计算边v v的CC边权重我们使用定义7：1（|H1、4|+1）w（v1v4）=R−1+vk∈v1 {v2，v3}（dk4））−1uG（vi，VJ38T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29˜142⊆∈CC边缘的重量v v表1（图1b中的图形）对于不同的助手节点集H一，四。H1、 4P1{v2，v3}0。小行星612Rw（v1v4）二、小行星836{v2}0。小行星928二、小行星855{v3}0。小行星947二、小行星395=R+（|H1、4|+ 1）100。612R，=2。836河注意，CC边的权重v v，使用节点v和v作为助手，等于˜14 2 3. 与前面的例子一样，我们使用等式2来w（v1v4）=2。小行星836仅使用节点V2作为辅助节点并仅使用节点V3作为辅助节点来计算节点V1需要达到V4的传输功率表1总结了这个例子中的所有演算。分析表中的w（v v）列，可以验证CC的权重边缘˜14作为助手节点。这是因为，作为仅使用节点vv1v43可以从定义7观察到，CC边缘的权重是成本 从源节点向其助手发送数据包，与它的助手合作。因为，在该示例中，节点v2比v3更远离v1，分别为距离R和R。因此，节点v1到达节点v2比到达v3花费更多的功率。因此，只使用nodev3作为它的助手，可以节省更多的电池。CC中有效辅助集的选择问题是一个这是一个具有挑战性的问题，并已在其他作品中得到解决[12，29]。3.4问题公式化考虑一个ad hoc网络，其中节点分散在一个固定的区域中，并且在网络边界中有一个唯一的sink。汇聚节点负责从其他节点收集和请求信息。节点是固定的，也就是说，没有移动性是假设的，和下划线的网络图可以得到不相交，由于链路故障，电池耗尽等。这项工作 使用定义的符号，给定网络拓扑G=（V，E），其中v o V是sink节点，这项工作的目标是提出一种使用CC创建图G和子图GJ的技术，GJG，这样，GJ是关于G和节点vo的COE-t-S，遵循定义11。在下面的部分中，描述了这项工作4提案在本节中，描述了CoopSink（Cooperative Sink的缩写），一种用于协作adhoc网络的拓扑控制技术这项技术旨在T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）2939吉吉C，来自这些节点的耦合功率不足以创建CC链路vv，则返回错误消息（第16-18行）;∈⊆改善节点到信宿的连通性，同时使到信宿的路由的能量消耗最小化。首先，一个贪婪的启发式的帮助，集合选择问题的描述，然后CoopSink技术被描述为一个序列的四个步骤。本节的公式和算法基于第3节的定义，并假设有一个中央计算单元。4.1贪婪辅助集选择算法算法1描述了一个贪婪的启发式算法，由[33]提出并适用于这项工作。该启发式算法用于为CC选择最有效的帮助节点，并且可以用于有向图和双向图。 该算法的输出是帮助节点H的集合i、j，使得CC链路的权重v vj为最 小 化 （ 尽 管 不 能 保 证 最 佳 解 决 方 案 ） 。 考 虑 函 数 原 型GreedyHelperSetSelection（vi，N（vi），vj）以参考算法1。在下文中，描述算法和增益函数。4.1.1算法一般描述算法1有三个主要步骤：• 步骤1（第1-11行）：该步骤包括根据增益启发式对来自Vi（N（Vi））的相邻节点进行排序。 根据启发式，N（vi）中的节点带来的增益越大，它将被定位在向量B中。在此步骤中使用以下函数：函数head（X）返回向量或集合X中 的 第 一 个 元 素 ; 函 数 remove （ X ， Y ） 从 集 合 X 中 删 除 元 素 Y; 函 数SortDescending（X）接收向量X并返回相同的向量，但按降序排序;而函数indexTerms（X），其中X=[bk1，bk2，.，BK|N（vi）|]，返回向量ck1ck2Ck|N（v i）|Y=[v k1，v k2，...，V K|N（vi）|]中。增益函数在第4.1.2节中描述。•第2步（第12-21行）：这一步包括将vector中的元素C到助手集Hi，j，使得vi和它的助手集应该具有最小的根据等式2，计算用于创建CC链路的发射功率v v。 如果经过将所有元素添加到吉吉吉吉• 步骤3（第22-31行）：该步骤包括将最大数量的辅助节点添加到集合H i，j，使得下一个节点的包含不会增加CC链路权重。 在包括CC链路增加CC链路权重或者C中的所有元素已经被测试的情况下，函数返回集合Hi，j（第23-24行）。 函数W eightCC（vivj，Ω），其中vivjEt和dΩ使用Ω中的节点作为帮助节点来返回链路的CC链路权重v i v j。4.1.2增益函数算法1（步骤1）中的增益函数用于对N（vi）中的节点进行为了在能量消耗方面获得更大的增益，以创建CC链路v v.吉吉40T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29τ（di，k）CCK˜∅--对于每个节点vk∈N（vi），考虑以下值：• bk←（di，j）−α−ατvl∈{vi，vk}（dl，j）-α：节点vi可以节省的功率量，如果它添加节点vk作为助手。注意，减法中的第一个元素是vi直接与vj通信的成本，减法的第二个元素是vi使用节点vk作为助手与vj• c k=τ−α：v i与助手v k直接通信的能量成本。由于这里的目标是降低CC链路的权重，因此表示增益的bk的值应该最大化，而表示与帮助节点通信的成本的ck的值如此则增益函数考虑比率bkK 作为指示哪个节点带来更大的增益，也就是说，如果bk对于k=h是最大的，那么包含帮助节点Vh将带来比其它辅助节点更大的增益。4.2CoopSink：提案描述本节介绍CoopSink技术的步骤。CoopSink由以下四个步骤的顺序执行组成：• 步骤1：创建拓扑图，每个节点创建尽可能多的边，因为它的最大传输功率允许;• 步骤2：使用CC在网络中创建尽可能多的CC链路;• 步骤3从上一步• 步骤4：调整节点的发射功率，以最小化能量消耗，但保持网络连通性。下面的小节更好地描述了前面的每个步骤。4.2.1步骤1：图GP算法2描述了CoopSink的第一步。该步骤包括在图拓扑中创建所有可能的直接边，因为所有节点都以其最大传输功率PMAX操作。算法2将节点集作为输入：V=v1，v2，.，v n及其在映射中的信息;最大传输功率P MAX.作为输出，我们有直接图GP。 图3a和3b示出了输入图和计算的G图。在图3a中，我们有一个500 × 500米的区域，n=50个节点，没有边，即E=。 图3b示出了当节 点 基 于 其 最 大 传 输 功 率 创 建 边 时 所 得 到 的 图 。 在 这 个 例 子 中 ， PMAX=4900，R MAX=70。请注意，结果图不一定是连通的。4.2.2步骤2：图G和G算法3描述了CoopSink该步骤包括创建所有可能的CC边，将来自前一步骤的图G=（V，E）作为输入，并返回具有直接边和CC边的图G作为T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29415：b←−（di，k）7：B←[B，];当doMAXk，jv∈Ω时˜ ˜∪←| |←←∪←∪算法1：GreedyHelperSetSelection（vi，N（vi），vj）Require：vi，N（vi），vj确保：Hi，j;1：#（步骤1）2：Set：A←N（vi）;3：向量：B←[]，C←[];4：while（vk←head（A））/=bindoτk（di，j）−α6：ck=τ−α;bkck8：remove（A，vk）;九： end whileτvl∈{vi，vk}（dl，j）−α;10：B←SortDescending（B）;11：C indexTerms（B）12：#（步骤2）十三： k←0，Ω←vi;14：（P（d））<τK15：kk+1;16：如果k > C，则17：返回错误;18：如果结束19：Hi，j<$Hi，j<$A[k];20：Ω ΩHi，j第二十一章： end while22：#（步骤3）二十三： 当（k≤|N（v i）|）做24：如果（k=|N（v i）|）或（W eightCC（vivj，Ω）W eightCC（vivj，ΩC[k+1]））25：返回Hi，j;26：其他27：k←k+1;28：Hi，j←Hi，j<$C[k];29：Ω ΩHi，j30：如果结束第三十一章： end while32：返回Hi，j;然后如在小节2.3中所描述的，CC中的有效帮助集合选择是一个具有挑战性的问题，因为它在计算上是昂贵的。因此，可以使用统计学来处理这个问题。在这 项 工 作 中 ， 我 们 考 虑 [33] 中 提 出 的 贪 婪 启 发 式 具 有GreedyHelperSetSelection（vi，vj）原型的该试探法接收以下作为输入：;42T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29源节点vi;和目的地节点vj。输出是辅助集Hi，j。作为示例，考虑图3b和3c中表示的曲线图。图3b中的图是步骤1的输出图和步骤2的输入图。T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）2943∈˜ ∈≥˜∈∈算法2：CoopSink步骤1（V，PMAX）Require：VePMAX;确保：G;1：G=（V，λ）;2：对于（vi，vj∈V），3：如果（PMAX（dij）-α τ），则4：将vi vj加到GP;5：如果结束第六章： 端2. 图3c中的图形是步骤2的输出。 在这些图中，直接边vi vj E以蓝色示出，CC边vi vj E以红色示出，辅助边Hi，j以绿色示出。注意，在这个例子中，创建了大量的CC边，然而，这些是直接边，也就是说，vi vj∈E的存在不并不意味着v j v i∈ E。˜4.3步骤3：从G算法4描述了CoopSink的第三步。 此步骤包括创建图GJ，使得该图是关于G的COE-t-S，并且节点v oV.它接收以下输入：图G;常数t;和节点v oV. 它返回一个图形GJ。 图3c和3d说明了这一步中发生的情况。 图3c中的曲线图是具有多个直边和CC边的图，并且是步骤3的输入之一。在本例中，其他输入为t=1。4和v0在坐标平面中的位置（0，0）上。图3d所示的步骤3的结果图是相对于图3c中的图的COE-t-S。结果图是一个直接图导向也就是说，所有连接的节点都具有到V0的直接路由。注意，图3b上先前未连接的节点现在具有到汇聚节点v0的路径。可以注意到，一些节点区域在最后阶段仍然是断开的。图3d示出了在建立到其相邻节点的CC链路时失败的节点4.3.1步骤4：调整发射功率算法5描述了CoopSink的最后一步。该步骤包括调整输入图GJ中的所有节点的传输功率，使得COE-t-S属性被保持并且能量消耗被最小化。在下面的部分中，CoopSink技术与文献中的其他技术进行了比较。5仿真结果在前一节中，提出了一种新的技术，在合作ad hoc网络的拓扑控制，重点是增加连接，同时保持有效的路由到sink。在本节中，它是使用模拟比较的建议，在文献中。选择以下技术进行比较：CoopBridges [33]和MST-Kruskal[16]。CoopBridges从44T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29˜˜∈˜˜≤CUP←--←算法3：CoopSink步骤2（G）要求：G;确保：G;1：G=（V，V）;2：对于（vi，vj∈V），3：Hij←GreedyHelperSetSelection（vi，vj）;4：如果（wCC（Hi，j）≤PMAX），则5：将vi vj加到G;6：if（vivjGandw（vivj）>w（vivj）），则7：从G中去掉vi vj;8：如果结束9：如果结束10点整： 端11：G=G+G;算法4：CoopSink步骤3（G，t，v，o）要 求 ： G= （ V ，E ） ; 确 保 ： GJ=（V，EJ）;1：GJ←G;第二章： k←1;3：向量A←接收E中按权重排序的所有边第四章： 当（k≤|B|）做5：vi vj←A[k];6：GJP←GJP−vivj;7：如果（maxvi∈Vμ（vi，vo）t），则8：#删除边vi vj将损害ESF;9：GJP←GJP+vivj;10：如果（v v=v v），则ijij11：从B移除从vi到Hi，j中的所有节点的所有边12：如果结束13：如果结束14：kk+1;十五： end while算法5：CoopSink步骤4（GJ）要求：GJ=（V，EJ）;一曰： 对于vi∈V，2：a←maxvivj∈G′Pwd（Hi，j），3： b maxvivj∈G′wCC（Hi，j），4：Pi= maxa，b;第五章： 端直接图G（从CoopSink步骤1输出），并将所有连接组件拆分成簇。在簇内创T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）2945建尽可能多的双向CC边46T.F. Neves，J.L.Bordim/Electronic Notes in Theoretical Computer Science 302（2014）29| |500450400350300250200150100500050100150200250300350400450500面积（m）（一）500450400350300250200150100500050100150200250300350400450500面积（m）（b）第（1）款500450400350300250200150100500050100150200250300350400450500面积（m）（c）第（1）款500450400350300250200150100500050100150200250300350400450500面积（m）（d）其他事项图三. （a）具有n=50个节点和E=0的网络拓扑示例。（b）当节点以最大功率P MAX操作时，从（a）创建的有向图G。（c）图G，从（b）中的图创建，通过添加所有可能的CC边。 （d）特遣队所属装备在（c）的基础上设立。最后，使用分布式MST算法去除类间边缘和类内边缘。MST-Kruskal通过在生长的MST森林中找到连接两棵树的边，一次一条边地生长最小生成树（MST），接收图G作为输入。最初，我们的意图是将该建议与贪婪-（添加/删除）-链接技术[35]进行比较，然而，该技术假设在添加CC边之后创建的拓扑必须是连接的。CoopSink和CoopBridges都没有考虑这个这里，结果拓扑是在应用拓扑控制算法之后创建的拓扑。为了评估CoopSink性能，考虑以下指标：• M1 -到sink的连通性：在结果拓扑中具有到sink的路由的节点的百分比;• M2-平均传输功率：分配给结果拓扑中的每个节点的传输功率的平均值• M3：ESF到sink：包括从G=（V，E），EJ<$E创建子图GJ=（V，EJ），并在考虑时验证常数t的值面积（m）面积（m）面积（m）面积（m）T.F. Neves，J.L.Bo