解决最小能量广播问题的局部算法

迄今为止，针对广播问题，主要是将跳数作为性能指标进行讨论的。文献中经常用到的另一种指标是节点之间的发射和接收功率。如果节点能够调整其发射功率（这是本节我们所做的假设），则可采用该指标。选择转发节点及其传输半径，使得网络中所有节点都能接收到该消息，且最大限度地降低用于消息传输的总功率的问题，称为最小能量广播问题。当前解决方案的详细综述见参考文献（Ingelrest et al.，2005；Liu et al.，2005）（少数其他解决方案见参考文献（Stojmenovic et al.，2007））。

参考文献（Wieselthier et al.，2000）描述了一种集中式广播增量功率（Broad-cast Incremental Power，BIP）。它是诸多现有集中式解决方案中最为流行的一种。在BIP算法中，每次向现有增加树中添加一个节点，这样能够确保每步（增量式）的额外功率最小化。存在两种选择：添加新的传输，或提高现有传输节点的传输半径，这样就可以添加具有最低可能额外功率的新节点。在实践中，广播增量功率和所提出的其他方法与MST运行机理类似，因为对于距离d处来说，在功率量度模型p（d）=d^α+c中，2≤α，除非在网络密度方面c非常大。集中式算法的主要优点在于每个节点用于收集和维护全局网络视图的通信开销。该开销不是BIP（Wie-selthier et al.，2000）和所有提出的其他集中式解决方案的一部分。

参考文献（Ingelrest and Simplot-Ryl，2008）描述了一种BIP算法的局部版，称为局部广播增量功率（Localized Broadcast Incremental Power，LBIP）。每个节点需要维护两跳信息，而不是整个网络范围内的信息。针对两跳邻域内的所有节点，发送方节点做出BIP决策。它附有一个记录表（A，R_A）以及为实现广播所传输的消息，其中A为单跳邻居，R_A>0为邻居A所采用的非零传输半径。不需要向指定为无源的邻居节点发送指令。首次接收到广播消息的节点，首先检查它们是否被指定进行重传。如果确实如此，节点使用自身存储的两跳消息，来为其邻居依次计算传输半径。这可能会增加输入消息指定的节点传输半径，也可能会增加某些指定邻居的传输半径，但不会降低传输半径。也就是说，它们可能会从已经完成的局部BIP构建开始，并将无法“看”到的两跳邻居添加到树中。需要注意的是，若干个邻居可能并行进行这种计算。然后，第一个传输消息的邻居将会对其他邻居产生影响，使其在宣布其决定之前调整结果。如果某个节点接收到针对同一节点（它本身或邻居）多个半径的若干条指令，则节点将会选择较大的半径。奇怪的是，该算法在总能耗方面的性能，与集中式BIP协议的性能非常接近，而保持了局部特性。该算法与基于MPR的广播算法特性类似，也包含了重传邻居集和消息。由于增加的消息长度将在媒体接入层次影响算法性能，在该层次上，较长的消息会提高碰撞的概率，因而这看来是LBIP算法的主要缺点。当广播相对较短的消息时，该问题尤为突出，因为增加的消息长度会提高其在总长度中的百分比。当将MPR广播方案与参考文献（Ingelrest et al.，2007）中的基于CDS的广播方案进行比较时，这是一个极易发现的非常类似的问题。与本章提及的其他一些协议相比，LBIP的另一个缺点是它需要收集两跳邻居信息，而不是单跳邻居信息。

正面我们描述针对最小能量广播问题的现有局部算法，它们不会增加消息的长度。对于小值常数c（与其他常数α有关）来说，MST是一种最优树，但需要全局信息。给定一个用于连接所有节点的稀疏图，局部算法（第一个算法是由Car-tigny、Simplot、Stojmenovic在参考文献（Cartigny et al.，2003）中给出的）基于决定其传输半径的每个节点，这样在所选结构中它的所有邻居被现有传输所覆盖。当采用邻居去除技术时，一些节点可能根本不传输信息（如果某个节点发现在所选结构中它的所有邻居已经被现有传输所覆盖，则它根本不需要传输消息）。

我们考虑图2-22所示的实例，在该实例中，MST用作一种稀疏结构。来自于源S的消息与传输半径一起发送，传输半径等于源S与该结构中最远邻居C之间的距离。节点A和B也会接收到该信息。节点A需要覆盖剩余邻居D，因而选择半径|AD|。同样，节点B需要覆盖节点C，因而选择半径|BE|。节点D传输消息及半径|DK|，通过选择半径|KC|，反过来可以覆盖节点C（节点K再生产来自于节点S的传输已经覆盖了节点C）。节点E覆盖其邻居F，而其邻居F选择半径|FH|，这是结构中到剩余邻居G、J、F最长的半径。节点G不需要重传信息，因为它的所有邻居已经被现有传输所覆盖，如来自于节点F的传输（采用了邻居去除技术）。最后，节点H覆盖邻居I。叶节点不重传信息。

图2-22 为实现最小能量广播，在稀疏结构中覆盖邻居

为了实现算法局部化，在参考文献（Cartigny et al.，2003）提出的RBOP算法中，采用RNG来代替MST；在参考文献（Cartigny et al.，2005）提出算法面向局部广播协议（Localized Broadcast Oriented Protocol，LBOP）中，MST由LMST所代替。采用RNG结构来代替MST时，将会导致能耗大约增加1倍，而LMST结构会使能耗大约增加50%。在LMST中，相对较少的额外边证明，其能耗比较高，由于这些边都是长边。(www.xing528.com)

对于与α有关的较大c值（在功率指标r^α+c中），许多在短边上进行的传输由于包含多个c值能耗较大。优先选择中心在某个节点的单个较大的圆，它覆盖了诸多单跳邻居，这些单跳邻居不是位于所选稀疏结构中的邻居。大的传输半径也会导致功耗过大。因此，人们希望在覆盖圆面积和功耗之间寻找一种折衷方案。参考文献（Ingelrest et al.，2006b）表明，如果某个节点决定重传消息，最优传输半径大约应为（2c/（α-2））1/α，必要时增大半径，以保持预期连通性。通过考虑包含固定区域内可变边长的规则蜂窝网格，并寻找能够实现最小化的边长，来导出该公式。另一种证明方法基于进程范例成本，由参考文献（Stojmenovic，2006）给出。传输一个数据包的成本与r^α+c成正比，而完成的进程与被覆盖的面积（即r²）成正比。对于r=（2c/（α-2））1/α来说，比值（r^α+c）/r²最小。

参考文献（Ingelrest et al.，2006b）提出的面向目标半径局部广播的协议（Target Radius Localized Broadcast Oriented Protocol，TR-LBOP）工作原理如下：每个节点管理两种邻居列表L和L′。L包含LMST邻居，L′包含其余邻居。在邻居去除超时即将期满前（在此期间，节点监听来自于其邻居的传输信息），如果L是空集，则取消重传。否则，选择足够长的半径，以到达L中最远的邻居，以及最接近目标半径的那个邻居（与上述公式中的设定一样）。对于所有密度来说，与BIP有关的TR-LBOP能量开销仍低于50%。

参考文献（Ingelrest et al.，2006b）进一步改进了面向目标半径局部广播的协议（TR-LBOP），以支持某些节点置于休眠模式，而在能量要求方面与TR-LBOP类似。首先，每个节点仅考虑那些距离不超过目标半径的邻居，并构建RNG或LMST中的邻居。使用该子图，即可构建CDS。其次，将未被CDS选中的节点转入休眠模式（周期性地将其唤醒，用于发送和接收来自于相关的最近DS节点的消息）。所选CDS中的节点仍保持激活状态，并采用TR-LBOP。每个节点选择能够覆盖其LMST邻居和目标半径的传输半径。采用针对CDS的广义覆盖规则。每个无源节点与最近的支配邻居建立连接。这种算法称为算法TR-LBOP-D。

参考文献（Chen et al.，2003）提出了PABLO算法，它需要两跳拓扑信息。每个节点A验证对于每个邻居B，是否存在一个共同邻居C，使得p（AC）+p（CB）<p（AC）。去除所有这些邻居B。在剩余邻居中，节点A选择最远的一个，并将其作为传输半径。更准确地说，它选择了所需的最大功率，来到达任一剩余邻居。作者们（Chen等）引用RBOP（Cartigny et al.，2003），该算法不是比较p（AC）+p（CB）<p（AC），而是比较max（AC，BC<AB）（根据RNG定义），其中XY表示边XY的长度。当c值较大，且网络为密集网络时，PABLO（Chen et al.，2003）和RBOP（Cartigny et al.，2003）应用效果都不太好。

参考文献（Wang et al.，2004）提出了基于局部最短路径树（Local Shortest Path Tree，LSPT）的拓扑，用于Ad Hoc和传感器网络中的功率感知路由和广播。距离为d的两个节点之间的边权重为p（d）=d^α+c。每个节点u采用Dijkstra最短路径算法，仅需根据其单跳信息，来寻找通向每个邻居节点的最短加权路径（该理念可扩展至k跳知识）。然后，节点u仅保存结构中那些通过它的边，并去除其他边。将结果发送给其邻居。之后，每个节点去除单向链路，并根据剩余逻辑链路来调整其传输半径。参考文献（Stojmenovic et al.，2007）提出使用LSPT，而不是LMST或RNG，来作为最小能量广播算法中的连通结构。这种方法将自动考虑变量c>0的影响，因为较长定向链路的效率要比指向它们的多跳路径效率更高，当接近最优目标半径时，就会出现此类现象。同时，节点也可以简单地采用目标半径（在与参考文献（Ingelrest et al.，2006b）所提TR-LBOP对应的协议中，可以选择的一种半径是（2c/（α-2））1/α）。

在许多论文中的能耗模型中，都假定c=0。例如，参考文献（Chiganmi et al.，2008）描述了两种此类算法。在内外功率（Inside-Out Power，INOP）自适应方法中，重传某个节点与每个邻居之间的最短加权路径，并选择与该节点到最远邻居的距离相等的传输功率。直接传输功率效率要比经由任意邻居的间接传输高。此时只考虑那些确认未被先前传输所覆盖的邻居。INOP方法中的每个节点在回退计时器后，做出自己的决策。换句话说，INOP与RBOP（Cartigny et al.，2003）和LBOP（Cartigny et al.，2005）类似，它使用LSPT（Wang et al.，2004）来代替RNG和LMST作为连通结构（对于任意值c来说，参考文献（Wang et al.，2004）也独立提出了这一点）。PABLO（Chen et al.，2003）可以看做是仅考虑长度为两跳的路径，而不是两个邻居之间的任意路径长度的一个版本。INOP-1算法（Chiganmi et al.，2008）建立在与针对两跳邻居的BIP类似的邻居指定方法基础上。也就是说，它与局限于c=0情形的LBIP（Ingelrest and Simplot-Ryl，2008）类似。

参考文献（Cartigny et al.，2004）提出了一种使用定向天线进行节能广播的Ad Hoc网络自适应局部方案。它遵循已提出的基于目标半径的重传理念。在这种理念中，期望半径也取决于天线角度。