地理位置路由成本进度比框架的应用分析

参考文献（Stojmenovic，2006）提出了一种用于设计传感器网络网络层协议的框架，包括局部路由、广播、区域覆盖等。框架建立在对成本进度比进行优化的基础上。在这种情况下，到达路由中下一跳转发节点的成本用一种特殊的度量方法表达，进度是一种到达目标节点进度的测量标准。

成本度量的实例包括跳数、功率、磁阻、功率×磁阻、延迟和预期跳数（参考文献（Stojmenovic，2006），也可参见第1章）。每条链路都有一个成本计量方法，它与所采用的假定和度量标准有关。框架假定每个节点都知道它与邻近节点链路的成本。该框架的基本思路如下：假设源节点或当前节点S有k个邻居，且仅考虑那些比当前节点更接近目标节点的邻居，以确保每一步的进度。也就是说，S向目标节点转发数据包时有k种选择。然后，节点S针对每个邻居计算C_i/P_i，i=1，2，L，k，其中C_i和P_i分别代表第i个候选邻居的成本和进度。选择具有最小成本进度比的邻居来转发数据包。接收节点连续使用该规则，来选择下一跳转发节点。路由过程不断进行，直至到达目标节点，或者没有进度邻居可用。如果没有符合要求的邻居，则丢弃该数据包，或者在丢弃数据包之前，使用基于特殊成本度量标准的恢复机制来开启一个进程。通过将框架应用到以下著名的地理路由算法中，就可以很好地说明这一点。

在上一节中介绍的贪婪路由（Finn，1987）中，成本度量指标是跳数（路由上的传输次数），转发的进度是到目标节点距离的减少程度。对拥有待传输数据包的当前节点来说，向任意一个邻居传输数据包的成本是相同的（即1跳）。在图4-1所示的实例中，节点B的成本进度比为1/（∣SD∣-∣BD∣）。在贪婪路由算法中，∣SD∣-∣BD∣可达到最小。如果进度指标定义为邻居在线段SD上的映射，则该路由算法就变成了MFR（Takagi and Kleinrock，1984）。

另一个实例是局部功率感知路由。参考文献同（Kuruvila et al.，2004）对该路由算法进行了描述。在图4-4中，节点C到达节点节点A所需的功率与CA^α+c成正比，其中α是功率衰减因子，正常取值范围为2和6之间；c是一个常数。常数c代表准确接收信号所需的能量和最小信号强度。功率指标可用来表示成本。进度定义为∣CD∣-∣AD∣（只考虑进度为正数的情况，即∣CD∣＞∣AD∣）。这样，功率感知路由的成本进度比为（∣CA∣^α+c）/（∣CD∣-∣AD∣）。所选的邻居能够确保在接近目标节点时，每单位进度的功耗最小。

图4-4 当前节点C、候选邻居A和目标节点D

需要注意的是，功率感知路由可能会导致某些节点的早期能量耗尽。如果将节点剩余能量作为磁阻考虑在成本中，则路由的目标是实现网络执行的路由任务数目最大化。例如，假定f（A）表示节点A处的归一化（在区间[0，1]内）剩余能量g（A）的倒数1/g（A）。具有更多剩余能量的节点，即f（A）值较小的节点，更愿意转发数据包，而剩余能量少的节点，即f（A）值较大的节点，不愿意这么做。路由算法选择能够实现f（A）/（∣CD∣-∣AD∣）最小化的邻居A作为转发节点，其中∣CD∣＞∣AD∣。该路由框架可应用于其他成本度量标准，如QoS要求、传输延迟、链路质量和数据。(www.xing528.com)

通过采用参考文献（Hang et al.，2004）（针对QoS度量成本）和参考文献（Kuruvila et al.，2004）描述的迭代改进方法，可以对所有基于成本进度比的路由协议进行改进。假定当前节点C选择能够实现成本进度比最小化的邻居A作为转发节点，但总体目标是实现该路由上的总成本最小化。如果存在节点C的另一个邻居B，满足成本（CB）+成本（BA）＜成本（CA），则通过节点B转发数据包要比节点A更合适。这种改进以迭代的形式不断重复，直至不存在改进的可能。需要注意的是，如果节点C已经得到了给定度量标准信息（它包括两个邻居之间的度量标准），则这种改进能够以本地化方式在节点C处进行，无需交换消息。

迭代改进是通用方案（参考文献（Sanchez and Ruiz，2006），参考文献（Wu and Candan，2007），参考文献（Elhafsi et al.，2008））（采用功耗作为度量标准）的一种特殊情况。该通用方案建立在通往临时目标节点的最短加权路径基础之上。假定当前节点C选择具有最好成本进度比（在参考文献（Sanchez and Ruiz，2006）第一条建议中，临时目标节点由基于跳数的贪婪路由决定）的节点C作为转发节点。节点C不直接向A发送消息，而是构建一条从C到A的最短成本路径（使用与权重一样的成本度量标准），并将数据包转发给路径上的第一个节点B（通常情况下B=A），来实现总成本最小化。然后，节点B采用同样原理，从选择它自己的临时目标节点开始（Elhafsi et al.，2008），或者直接使用目标节点，通过构建最短成本路径，最终到达目标节点（Wu and Candan，2007）。为了避免两个邻近节点之间形成环路，我们仅考虑那些直接与临时目标节点相连的邻居。如果直至到达目标节点时，临时目标节点一直固定不变（Wu and Candan，2007），则不需要对指向最终目标节点的每步进度进行验证。否则，为了避免形成环路，只有那些靠近最终目标的节点（不仅仅是临时节点）才能参与最短路径构建（Elhafsi et al.，2008）。

如果贪婪路由（成本度量给定）无法在给定节点展开进度，则可调用恢复模式。恢复模式（在本章后面将会涉及）采用跳数作为度量标准，以保证恢复正常实现（这种解决方案是在参考文献（Stojmenovic and Datta，2004）中提出的）。但是，沿着这些预定边的总成本无法采用给定的成本度量标准进行优化。在算法（Wu and Candan，2007，Elhafsi et al.，2008）中，不是直接沿着这些边来传输数据，而是在具有最短加权路径的边的端点之间直接进行数据传输。同时，参考文献（Elhafsi et al.，2008）使用给定节点集构建了一个连通支配集，并计算通过计算其Gabriel图，来获取平面图G′。在G′上仅采用面路由来确定哪些边参与恢复过程。在每条边上，采用最短加权路径路由。这样，使用两样的方法可以得到下一条边，直至恢复过程变为可能。这种两相（贪婪-面）路由过程反复迭代，直至到达最终目标。

成本进度比框架的一个主要优点是它不需要诸如阈值的额外参数。在基于阈值的典型方法中，如果没有发现“好”邻居，则“坏”链接被取消，数据包被丢弃。但是，合理的路径中可能仅包含一个很弱的“桥”。目前，已经进行的实验表明，基于阈值的方法对于所有阈值来说性能比较差，原因可能是由于阈值限制条件过多，导致差错率过高，或者是由于阈值限制条件过于宽松，在一条路径中支持一个或多个弱链接，导致选择的路径不是最优，从而为路由生成了一个瓶颈因素。这种现象之所以发生，是由于在“可接受”链路的最终选择上，通常采用的度量标准与成本度量标准不同。例如，可能会选择最靠近目标的节点，但没有针对所选度量标准，考虑该节点几乎无法接受的状态（如延迟）。

负载均衡用于有效使用可用资源，通过平均分配负荷，保持负载节点能耗平衡。该问题用于路由数据包，避免路径拥塞，从而实现网络流量平衡，降低端到端延迟。在网络内部分配负荷有两大好处。首先，通过分配网络负荷可以充分利用网络资源。一种高效负载均衡路由协议能够提高数据包传输速率和网络吞吐量。其次，通过平均分配负荷，可以平衡能耗，延长网络的生命周期。Stojmenovic准备撰写的论文中提出了一种动态无参负载均衡地理路由协议。拥有待传输数据包的节点将数据包发送成本，与所有靠近目标节点、且未达到全负荷状态的可用邻居推进的进度进行对比。选择具有最小成本进度比负载（A）/（∣CD∣-∣AD∣）的邻居作为转发节点。在这个公式中，负载（即所选成本）可以看做是节点A处已消耗带宽与总带宽之比。成本随着消耗带宽的增加线性提高。递增成本可采用负载（A）/容量（A）来定义，容量（A）表示邻近节点A的归一化剩余带宽（容量）（Stojm-enovic准备撰写的论文）。