解决地理位置路由物理层问题的个案研究

在当前的文献中，几乎所有地理路由在通信模型中都使用了UDG。在UDG中，两个节点可以互相通信，当且仅当它们之间的距离不大于公共传输半径。但是，正如前面章节所讨论的，由于未将接收信号强度的变化情况考虑在内，因而UDG模型并不现实。参考文献（Stojmenovic et al.，2005）指出，信号强度波动的影响有时会比节点移动性的影响还要显著。因此，数据包接收属于概率事件。除了距离之外，接收信号强度还取决于其他因素，如环境条件和传输介质。

参考文献（Zorzi and Armaroli，2003）将进度作为一项路由决策的度量标准。由中继节点提供的进度可以定义为传输节点到预期目标的距离减去中继节点与目标节点的距离，乘以数据包从传输节点成功发送到中继节点的概率。这种思路在多篇论文中再次出现（没有引用（Zorzi and Armaroli，2003）），包括参考文献（Kuruvi-la et al.，2005）（2004年10月的会议版）、参考文献（Zuniga Zamalloa et al.，2008）（2004年10月的会议版）和参考文献（Lee et al.，2005）。

参考文献（Kuruvila et al.，2005；Kuruvila et al.，2006）提出了服从任何现实物理层协议、具有固定和可变数据包的地理路由协议。该协议考虑了包含和不包含确认消息两种情况。对于给定物理层模型来说，为了使用基于位置的路由，第一步是为比特和数据包接收概率找到一个合理准确的近似值。参考文献（Kuruvila et al.，2005；Kuruvila et al.，2006）使用了对数正态阴影模型。它用一个函数P（q，x）来表示，近似值与实际值误差在5%以内，其中q取决于所考虑数据包的长度L和两个节点之间的距离x。函数为

式中，β为功率衰减因子，取值范围为2～6；R是确定的，P（q，x）=0.5。比特接收概率为P（1，x），而对于长度L=120bit的数据包，其接收概率为P（2，x）。

在参考文献（Kuruvila et al.，2005）提出的aEPR-u（预期进度路由）中，节点接收路由数据包后，至多发送u条确认消息。主要目标是实现转发过程中的预期进度最大化。在如图4-4所示的实例中，C为当前节点，A为C的邻居，D为目标节点。假定|CD|=c，|AD|=a，|CA|=x。如果所有数据包都被成功接收，则C将向A转发数据包，以满足|c-a|最小化。在物理层模型中，A接收到来自于C的数据包概率为p（x）（p（x）的定义已经在第1章第1.5节中进行了介绍）。两个相距x的节点之间的预计总跳数（数据包数）为f（u，x）=1/[p（x）（1-（1-p（x））u）]+u/[（1-（1-p（x））u）]（参见第1章）。aEPR-u（包含确认消息的预期进度路由）选择能够实现（c-a）/f（u，x）最大化的邻居。

参考文献（Kuruvila et al.，2006）中的局部协议没有采用逐跳确认。该文献指出，如果在源节点和目标节点之间配置大量中间节点，且相邻节点之间的距离趋于0，则数据包传送概率趋于1。基于观测数据，端到端路由（End-to-End Routing，EER）局部路由简单将数据包给能够实现p（x）最大化的邻居，即在比C更靠近D的邻居中，与C距离最近的邻居。该过程持续进行，直至到达目标，或节点无法找到比自己更靠近目标的邻居。与EER不同，nEPR（不包含确认消息的预期进度路由）算法将数据包转发给能够实现预期进度p（x）（c-a）最大化的邻居。算法仅考虑那些比当前节点更靠近目标节点的邻居。(www.xing528.com)

参考文献（Kuruvila et al.，2006）提出的InEPR（迭代预期进度路由）是nEPR的一种改进变形。该算法工作原理如下：与nEPR类似，首先，当前节点C找到能够满足p（|CA|）（|CD|-|AD|）最大化的邻居A。对于A和C的所有公共邻居，C找到满足p（|CB|）×p（|BA|）＞p（|CA|），且能够实现p（|CB|）×p（|BA|）最大化的节点B。算法仅考虑那些比C更靠近目标的邻居。通过对邻居逐个进行检查，不断迭代重复该过程，直至无法改进。节点C最终将数据包转发给邻居B，邻居B采用相同的过程进行数据包转发。通过寻找指向A的最短加权路径C，B₁，B₂，…，B_n，A，可以将该算法进行推广。采用Dijkstra最短加权路径算法，概率乘积的对数可以表示为log（p（AB₁）p（B₁B₂）…p（B_nA））=log（p（AB₁））+…+log（p（B_nA））。

参考文献（Kuruvila et al.，2006）提出的基于投影进度的算法，与nEPR方案仅仅在进度度量上有所区别。进度是使用点积CD·CA，而不是使用c-a进行度量，其中CD·CA表示两个向量的点积。当前节点C将数据包转发给邻居A，它比节点C更靠近目标节点，且满足p（|CA|）（CD·CA）最大化。除了采用投影进度方法来寻找第一个候选节点外，迭代投影进度方案（Kuruvila et al.，2006）与InEPR相同。

参考文献（Stojmenovic et al.，2005）对每跳上可变数据包长度和具有逐跳确认消息的路由情形进行了研究。局部算法采用预计传输比特数（能耗），而不是aEPR-u和InEPR中的预计跳数。针对具有逐跳确认消息的路由，aEPR-u和InEPR中的预计跳数f（u，x）被预计比特数g（b，k）所代替。同时，参考文献（Stojm-enovic et al.，2005）还对可变数据包长度和不含逐跳确认消息的路由进行了研究。

迄今为止，描述的算法都是基于物理层的贪婪位置路由解决方案。可以对传输保证路由的恢复过程（Bose et al.，1999）进行修正，以应用于物理层模型。面路由建立在各边都比较短的平面图基础之上。这样，平面图中的那些边在物理层模型中具有相对较高的接收概率。因此，与UDG模型中的恢复模式影响方式类似，恢复模式对物理层路由的影响会继续存在。对于面上的每种访问模式，节点最短路径成本可以根据成本度量标准进行计算，该标准将数据包接收概率考虑在内。

参考文献（Frey et al.，2005）指出，通过修改选择最佳转发邻居标准，设置恰当的超时，BLR修正版也可以应用于物理层。给定节点多次公告数据包转发请求，以确保最佳转发邻居能够接收到该请求。同样，最佳转发邻居多次响应，以确保响应能够被接收，它能够被选中。复制数据包的数目取决于详细的物理层模型。