基于支配集的骨干网设计优化探究

假定V为网络中的传感器节点集。k-支配集（k-DS）是V的一个子集，它使得V中的每个节点要么包含在k-DS中，要么在k跳之内到达k-DS中的至少一个节点。k-独立支配集（k-IDS）是一种k-DS，它使得节点集中的任意两个支配器之间的距离至少为k跳。参考文献（McLaughlan and Ak k-DS kaya，2007）提出一种算法，将执行器像簇头（CH）一样放置，从而最大限度地提高被覆盖的传感器数，降低数据收集时间。这可以通过寻找基础传感器网络的k跳IDS（k-IDS），并将执行器置于k-IDS中所选的传感器附近。传感器节点根据它与支配器之间的距离和支配器ID，加入到其支配器中。加权函数可用于优先选择那些具有多个k跳邻居，且远离其他簇边界的特定节点。最后，每个执行器在其簇内充当簇头，每一簇中的所有传感器距离簇头（CH）不超过k跳。

基于CDS的骨干网不一定建立在UDG的基础之上。它可以应用于诸如传感器与执行器网络的异构网络中。例如，参考文献（Stojmenovic et al.，2002，2004；Dai and Wu，2003；Carle and Simplot-Ryl，2004）提出的基于广义覆盖的算法（已经在第2.4.3节进行了介绍），可以扩展至混合网络。需要注意的是，在算法的自修剪规则（Dai and Wu，2003）中，可使用节点的键值来确定优先级。为了对该算法进行修正以应用于混合网络，可以对节点的键值进行扩展，将节点的能级包含其中，即key（s）={E_s，ID（s）}，其中E_s为节点的能级，这与参考文献（Wu et al.，2002）提出的算法类似。由于接入点的能级要比移动节点高，因而通常会选择接入点作为支配器，这样选择接入点的过程将成为广播过程的一部分。传感器与执行器网络中可采用该模型，因为在此类网络中，传感器和执行器可以分别看做是移动节点（虽然通常情况下它们是静态的）和接入点。

在图2-18所示的实例中，假定节点0是一个接入点，其他节点是移动节点。在应用参考文献（Dai and Wu，2003）提出的算法后，会得到如图2-18a所示的CDS。如果使用键值{E_s，ID（s）}，则将接入点0选进DS，结果如图2-18b所示。(www.xing528.com)

图2-18 使用不同键值选择方法构建的CDS