无信标地理位置路由技术优化

通常情况下，为了将当前位置信息广播给所有单跳邻居，贪婪转发算法需要每个节点使用最强信号强度，周期性地交换“问候”消息（信标）。贪婪路由的信标交换过程会导致额外的能耗，它通常会独立于当前的数据流量之外发生。

Heissenbuttel和Braun在参考文献（Heissenbuttel and Braun，2004）中提出了无信标路由（Beaconless Routing，BLR）算法。参考文献（Füβler et al.，2003）中的基于竞争转发（Contention-based Forwarding，CBF）和参考文献（Blum et al.，2003）中的隐式地理转发（Implicit Geographic Forwarding，IGF），将无信标路由与IEEE 802.11媒体接入控制（MAC）层集成起来。在BLR中，节点S当前保存有将要发送到节点D的数据包，数据包中包含了节点S及节点D的位置信息，它能够重传转发请求或消息内容。当收到数据包后，拥有一个进程、作为转发候选节点的邻近节点，根据节点自身、节点S和D的相对位置坐标，来计算等待超时。位于“最佳”位置的节点引入最短延迟，并首先转发数据包（或首先响应重传）。然后，（大多数）剩余节点取消预定的相同数据包的重传。

无信标路由如图4-12所示。为了确保所有潜在转发节点检测到S传输，用来完成下一个转发的候选节点选择被限制在特定转发区。转发区具有每个节点能够获取该区域其他节点传输信息的特性。参考文献（Heissenbuttel and Braun，2004）表明，在贪婪路由失败之前，半径等于传输半径、圆心位于线段SD上，且将S作为一个端点的圆（图4-12中的虚线圆）是一个与进程和成功跳有关的理想转发区。该文献研究了几种可导致不同转发行为的延迟函数。

图4-12 BLR中的转发区

参考文献（Fuβleret al.，2003）提出了一种称为主动选择方法的技术。转发节点发送一个控制数据包给所有邻居，而不是发送整条消息。一个超时之后，邻居使用转发进程信息进行响应，超时的长短取决于邻居节点与目标之间的距离。然后，转发节点发送整个消息，说明哪个邻居将转发消息。参考文献（Zorzi，2004）提出通过使用从IEEE 802.11派生的请求发送（Request to Send，RTS）/允许发送（Clear to Send，CTS）MAC机制，来避免BLR中的复制转发现象。当前节点发送一条RTS信令，而不是整条消息，然后等待CTS信令。如果收到多条响应，则节点选择最适于转发的节点，然后直接将消息发送给该邻居。

当贪婪路由失败时，需要一种诸如面路由的恢复策略来保证传输。需要注意的是，面路由通常基于根据邻居信息构建的平面子图，这在BLR中是不可用的。为了解决这个问题，参考文献（Kalosha et al.，2008）提出了一种保证传输的无信标地理路由方案。该文献提出了两种解决方案：无信标转发平面化（Beaconless For-warder Planarization，BFP）和角中继。无信标转发平面化在不接收所有邻居消息的情况下，能够发现转发节点处局部平面子图的恰当边。然后，在子图中采用面路由。角中继直接确定面遍历的下一跳。这两种方案的详细内容将在后面提到。

无信标转发平面化是一种通用方案，主要用于构建GG和RNG。它包括两个阶段：选择阶段和抗议阶段。在选择阶段，转发者v广播一条包含自己位置的RTS消息，并将定时器设置为t_max。每个邻居u使用如下延迟函数来设置其竞争定时器：t（d）=t_max×d/r，其中d=uv，r为传输半径，t_max为最大超时。也就是说，较近的邻居设置较短的等待时间。当节点的竞争定时器到期时，节点使用一条CTS消息进行响应。如果节点w接收到另一个位于禁区N（v，w）的节点w′发送来的CTS时，w将取消其定时器。在如图4-13所示的实例中，节点根据它们与节点v之间的距离，按w₁，w₂，…，w₆升序来设置它们的定时器。节点w₁首先响应。当w₂的竞争定时器到期时，w₂向节点v发送一条包含自身位置的CTS消息进行响应。由于w₅知道CTS消息的内容，它发现w₂位于禁区N（v，w₅）中。因此，w₅取消其定时器，并成为一个隐藏节点。由于w₆不知道w₄和w₅发送的CTS内容，因而一旦竞争定时器到期，它将使用一条CTS消息进行响应。但是，由于w₄和w₅位于禁区N（v，w₆）中，因而边vw₆是犯规边，不应当包含在GG中。

(www.xing528.com)

图4-13 在BFP中选择GG边

在抗议阶段，隐藏节点抗议犯规边。如果犯规节点集非空，则隐藏节点开始使用同一延迟函数来启动其定时器。犯规节点可以被其他隐藏节点报告。否则，隐藏节点发送抗议消息。当收到来自于隐藏节点的抗议消息后，转发者删除犯规边，最终得到一个平面图。在如图4-13所示的实例中，隐藏节点w₄的定时器小于w₅的定时器。当w₄的定时器到期时，它向转发者v发送一条抗议。v删除犯规边vw₆。由于w₅知道w₄的抗议信息，它将w₆从犯规节点集中删除，该节点集随后变成空集。这样，w₅的定时器到期后，它仍然保持静默状态。

与BFP类似，角中继算法包括选择和抗议两个阶段。在选择阶段，转发节点v接收到来自于前一跳u的数据包，发送一条包含节点u和自身位置信息的RTS，并将定时器设置为t_max。每个邻居（如w）使用如下延迟函数来设置其竞争定时器：t（θ）=t_max×θ/（2π），其中θ=∠uvw采用逆时针方向。如果邻居在禁区内发现其他节点，则使用一条“非法CTS”进行响应。目的是使其他节点知道它的存在。否则，它们将被隐藏，之后需要一个抗议的机会。一旦第一个候选节点w使用合法CTS进行响应，则转发者立即发送一条SELECT消息，宣布w为第一个选出的节点。所有准备发送CTS答案的候选节点取消其定时器。一旦第一个候选节点选定，则抗议阶段开始启动。转发者设置其包含当抗议发生时间信息（如针对GG，可以将其设置为t（π/2））的抗议定时器。不允许其他CTS。每个候选节点x设置一个新定时器t（θ），它可以确定抗议的次序，其中θ=∠uvx-∠uvw。只有那些位于N（v，w）中的节点可以进行抗议。进行抗议的节点x自动成为下一跳。之后，只有那些位于N（v，x）中的节点可以进行抗议。最后，在当前选择的候选节点定时器到期后，转发者将数据包发送给该节点。

在图4-14所示的实例中，节点按w₁，w₂，…，w₆升序来设置它们的定时器。由于w₁位于区域B（前一跳u位于N（v，w₁）中），因而w₁发送一条“非法CTS”。同样，由于w₁位于区域N（v，w₂），因而w₂发送一条“非法CTS”。当w₃发送一条“非法CTS”后，它就是所选择的节点。但是，w₄抗议，它认为自己是下一跳节点。然后，w₅发送一条抗议。最后，w₅是下一跳节点，v直接将数据包发送给w₅。

图4-14 实例

（在角中继中，接收到来自于w₁，w₂，w₃，w₄发送来的非法CTS后，选择下一跳节点w₅）