高效的负载均衡方法探析

针对传感器自部署，参考文献（Yang et al.，2007）提出了一种分布式负载均衡方法。该算法将目标区域划分为一个2D网格，并将节点当做负荷。目标是平衡每个网格单元中的负荷（即节点数）。图10-7a给出了6×6网格分区中每个的负荷（也称为权重）。采用该算法，每个网格单元中的节点形成一个覆盖单元的簇，且由所选簇头负责管理。

图10-7 负载均衡算法

a）节点分布 b）倍增扩展 c）扫描

在预处理阶段，首先沿着网格列执行递归倍增扩展，然后沿着网格行。这一阶段的目标是填充空簇。不同列（或行）可以同时进行。具体说来，列或行中非空簇的最大序列通过在其相邻空簇中以迭代方式栽培一粒种子（即一个节点），向某一方向进行扩展。扩展的初始跨度受到序列权重（即节点数）的影响；在每次迭代中，它将以前的扩展增加一倍。当最后一簇被覆盖，或当没有备用节点可用时，该扩展过程停止。如果适用的话，指向相反方向的扩展随后开启。

我们注意到，图10-7b给出了图10-7a中网格列4的倍增扩展。前两个簇（单元），图10-7a中用粗线标记，构成非空簇最大初始序列。该序列将扩展以填充它下面的空簇。倍增扩展到达列，经过两次迭代后终止。它可以由粗线的增长表示。在第一次迭代中，序列增加了二个簇。在第二次迭代中，它试图增加四个簇，但由于到达终点，因而扩展中途停止。在这两次迭代中，种子栽培到第三个簇和第四个簇。然后，倍增扩展终止，不存在空簇。

预处理阶段后，为了实现负载均衡，扫描阶段启动。该阶段通过两轮执行。在第一轮中，扫描每个网格行和对每个网格行进行负载均衡。在第二轮中，对每个网格列进行处理。在扫描轮中，沿着不同行（或列）的负载均衡可以同时进行。简明起见，我们考虑映射到任何一个网格行或网格列的一维数组。

在循环扫描期间，该算法首先从一端到另一端来扫描数组。在这次扫描中，每个簇i（实际上是其簇头），其权重由w_i来表示，计算其前一个簇的前缀加权和v_i=v_i-1+w_i，并将v_i传送到下一跳。最后一簇将计算数组的总权重，并将数组权重发送回源，来触发另一次扫描。在这次扫描中，每个簇i计算平衡状态下的平均簇权重及其前缀权重，然后确定其状态（过载或欠载）和沿着数组在每个方向负责提供或取回的节点数（负荷）。如果，则它处于过载状态，且它需要提供给右边与左边的节点数分别是

(www.xing528.com)

如果别，则它处于欠载状态，且它需要从右边与左边取回的节点数分别是

图10-7c显示了图10-7a中给出的网格行4扫描阶段结果。重点在此行的第4簇，即当i=4的情形。首次扫描后，它（实际上是其簇头）知道v₃=（1+7）+2=10，且其前缀加权和v₄=10+1=11。在第二次扫描中，当它从左侧接收到数组权重18后，它计算w=18/6=3且v₄=4×3=12。通过将自身的权重w₄和平均权重w比较，它意识到自身处理欠载状态。于是，它计算

和

从结果可以看出，它知道当节点通过它时，它应当从每个方向取回一个节点。

这种方法要求网络足够密集，使得负载均衡可能在整个感知邻域内进行。正如作者所承认的，当网络非常密集时，由于扫描轮数增加，因而它可能会产生大量消息开销。