|
节点u 更远，这与假设矛盾，所以，假设不成立，原命题成立。证毕。 图3 区域边界上圆弧的交点情况 Fig.3 Cross at the boundary of areas 135 引理6：节点u，u′ ∈N[v]，若交点a 仅是圆C(u)与C(u′ )的交点，且a 在区域A(N[v]) 的边界上，则节点u，u′ ∈B(v)。 证明：根据引理4，可证引理6。证毕。 根据引理5 和引理6，对于节点1 2 , ,..., k u u u ∈N[v]，如果能够判断C(ui)与C(uj)的两个 140 交点中至少有一个位于区域A(N[v])的边界上，则可以判断出节点ui 与uj 是否需要加入集合 B(v)中。 引理7：已知点a 是以N[v]中节点为圆心的几个圆的交点，∀ u∈N(v)，若D(a,u)≥ R， 则交点a∈Q(v)。 证明：因为D(a,u)≥ R,因此集合N[v]中不存在节点u，使得A(u)覆盖点a，所以，点a 145 是区域A(N[v])边界上的点，即a∈Q(v)。证毕。 根据以上引理，FWCDS 算法的主算法（转发集求取算法）如下。 主算法采用覆盖的思想，通过判断圆弧的交点是否在区域A(N[v])的边界上，确定是否 将产生此交点的两个圆的圆心加入集合B(v)。 主算法： 150 算法输入：N[v]，P。 算法输出：B(v)。 算法步骤： (1)初始化B(v)= ∅ ，P=∅ 。 (2)从(N[v] −P)={u1,u2,…,un}中选取节点u1。P=P ∪ {u1}。 155 (3)令x = filter(u1，N[v] −P)，若x 不等于False，则将x、u1 加入集合B(v)中。 (4)返回第2 步直至无法执行。 (5)pruning(B(v)，N[v])。 (6)结束。 算法的第3 步求取与节点u1 相交，且在区域A(N[v])上的节点，本过程由算法filter 完成。 160 图3 表示了算法区域边界上圆弧的交点情况，图3(1)表示交点d 仅是两个圆的交点，图3(2) 表示交点d 是多个圆的交点。算法的第5 步需要处理图3 (2)中多个圆在A(N[v])边界上交于 一定的情况，本过程由算法pruning 处理。filter 与pruning 算法如下： 算法的filter 如下： 算法输入：u1，N[v] −P，Q=∅ 。 165 算法输出：Q，返回值。 算法步骤： (1)若( N[v]−P) ≠ ∅ ，则从N(v) −P中选取节点ui，( N[v]−P)= N[v]−P− {ui}，否 则跳到第4 步。 (2)计算圆C(u1)与C(ui)的交点a，b。 170 (3)对于∀ u∈N[v]，若D(a,u) ≥ R，则Q=Q∪{b}；若D(b,u) ≥ R，则Q=Q∪{b}，返 回u，否则，跳到第1 步。 (4)返回False。 (5)结束。 算法pruning 过程如下： 175 算法输入：B(v)，N[v]，Q。 算法输出：B(v)。 (1)令Q={d1,d2,…,dk}，从Q 中选择d1， 1 Q=Q−{d}。 (2)令N(d1)={u1,u2,…,ui|ui ∈B(v),2≤i≤|B(v)|),D(u,d1) ≤ R,且不存在d∈Q，点d 在圆 C(ui)上}，对于ux,uy ∈N(d1)，在d1 的邻居节点集合N(d1)的所有节点中，若ux 距离uy 最远， 180 则B(v)=B(v) −N(d1)+{ux,uy}。 (3)返回第1 步，直至不能执行。 (4)结束。 图4 pruning 算法第2 步N(d)的选择 185 Fig.4 Selecting N(d) at the 2nd step of pruning algorithm pruning 算法第2 步处理多圆交于一点的问题时，需要选择一个d 的邻居节点集合N(d)， 但这个N(d)不包括这样的节点：存在除d 外的另一个交点已经在A(N[v])的边界上。图4 反 映了这个情况，图4(1)中的全部节点，除了一个交点d 外，另一个交点均在A(N[v])的边界 190 上，所以N(d)= ∅ 。图4(2)中由于C(u1)与C(u6)，C(u5)与C(u7)的交点在边界上，因此不在 N(d)中，所以有N(d)={u2,u3,u4}。 另外，算法的第2 步由定理1 保证。 定理1：若点a 是A(N[v])边界上弧的交点，则N(a)中距离最远的两个节点在区域A(N[v]) 上。 195 证明：反证法，令N(a)={u1,u2,…,ui|i ≤K(a)}，其中ui∈N[v]，若ux,uy ∈N(a)，且节点ux 与uy 在区域A(N[v])上，连接a 与节点ui，则角x y ∠u au 最大。 假设存在∠uxxauyy>∠uxauy，则必然有区域A( xx u )或A( yy u )，覆盖了边界上的交点x 或y，于是点x 和y 不在区域A(N[v])的边界上，因此，节点ux 与uy 不在区域A(N[v])的上， 这与原命题矛盾，所以假设不成立，原命题成立。证毕。 200 2.2 FWCDS 次算法 在图G=(V,E)中，主算法分布式的在每个节点运行，每个节点计算出自己的转发集。 当节点集V 中的所有节点计算出转发集后，则需要实施次算法来完成CDS 的求取。次算法 采用染色的方案：初始将所有的节点染成白色，当一个节点收到特殊数据包Pa 时，将自己 标记为灰色，当一个节点确定自己为支配节点时，将自己标记为黑色。算法完成后，所有被 205 标记为黑色的节点即为支配节点，所有灰色节点即为非支配节点。算法假定在源节点s 处开 始执行（s∈V，可任意选取）。 根据以上描述，次算法如下： 算法输入：B(v)，v∈V。 算法输出：CDS 210 (1)网络中的所有节点标记自己为白色，s 标记自己为灰色。 (2)节点s 广播数据包Pa，s 的邻居N(s)中的节点收到Pa，若N(s)中的节点为白色，则 标记自己为灰色。 (3)若灰色节点s′∈N(s) ，且s′∈B(s),则s′ 广播数据包Pa。 (4)当灰色节点s 收到了带有自己标识的Pa 后，s 将自己标记为黑色。 215 (5)灰色和黑色节点收到数据包Pa 后，不再广播数据包Pa。 (6)N(s)中的节点作为s，执行2、3、4、5 步的操作。 (7)结束。 数据包Pa 的结构需满足如下条件： (a)带有特征位，用以标识Pa 而异于普通数据包。 220 (b)带有二跳转发节点的标记。如s 广播数据包Pa， s′ 收到Pa，则N( s′ )会收到打有s 标记的Pa，表明s′ 转发的是来自两跳内的节点s 的数据包。 图5 数据包Pa 传输规则描述 Fig.5 Transportation of data package Pa 225 图5 给出了在次算法中，数据包Pa 在网络中传输的示意图。Pa:-1,1 表示id 为1 的节 点收到id 为-1 的节点广播的数据包后，广播的Pa。(1)中节点v 广播数据包，节点u 和w 收 到数据包，(2)中节点u 和w 收到数据包，然后广播带有1 标识的Pa，由于黑色节点不再广 播数据包，因此节点u 和w 无法确定自己为支配节点，支配节点为v。 230 算法的第4 步需要通过判断收到的数据包Pa 所附加的标志，来判断是否要标记本节点 为黑色节点。如上所述，只有当节点自己发送的数据包通过两跳后回到自己时，节点才会确 定自己为黑色，即确定为支配节点。图6 描述了这个过程。图中仅画出了转发节点，其中黑 色节点为支配节点，图6(1)源节点s 广播数据包Pa，图6(2)的邻节点转发Pa，s 确定为支 配节点，图6(3), 6(4), 6(5), 6(6)完成从21 个转发节点中选举出13 个支配节点。 235 次算法以广播扩散的方法完成了CDS 的求取，每个转发集中的节点作为灰色节点仅转 发一次。 图6 次算法的执行过程 图6 Processing step of slavery algorithm 240 3 算法分析 3.1 算法的正确性证明 因为图G=(V,E) 是Unit-disk 图，对于任意的节点v∈V ，主算法计算所得到的 B(v) ∪ {v}是N[v]的一个导出子图，因为B(v) ⊆ N[v]，因此B(v) ∪ {v}是连通的，并且B(v) 245 是N[v]的支配节点集。 根据次算法， 对于∀ u ∈ B(v) ， u ∈ (B(v)∪{v})∩(B(u)∪{u}) ， 因此 B(v)∪B(u)∪{v,u}是连通的，并且是N[v] ∪ N[N[v]]的支配节点集。依次累推，可知道通 过主次算法所计算得到的CDS 是图G 的连通支配集。 3.2 复杂度分析 250 本算法的执行分为两部分：主算法和次算法，因此，算法的分析也按两部分分别描述。 主算法分布式的在每个节点进行，且互不依赖，互不影响，因此，每个节点具有相同的 计算时间。主算法采用覆盖的策略，需要计算哪些节点在区域A(N[v])的边界上。对于∀ v∈V， N[v]中的节点需要两两计算其交点，若令N[v]={u1,u2,…,un}，其中n= Δ +1，于是，这一过程 的计算次数为： 255 T11 =2n×((n−1)+(n−2)+L+2+1)×C=Cn(n−1) 2 11 ( 1) v v T =CΔ Δ − 公式(1) 其中C 表示节点计算所需的时间。 公式(1)是主算法中filter 算法所需要的时间，pruning 算法处理多个圆在边界交于一点的 情况，其最坏的情况是1 v Δ + 个圆相交于一个点，此时算法执行所需的时间复杂度为： 12 ( 1) 2 T C v v 260 = ′ Δ Δ + 公式(2) 其中C′ 表示节点计算所需的时间。于是，主算法的时间复杂度为： 2 1 11 12 ( 1) ( 1) 2 v v v v T T T C C Δ = + = Δ Δ − + ′ Δ + 3 (2 ) 2 ( ) v 2 v 2 v C C C C C ′ ′ = Δ + + Δ + + Δ 再来看次算法，次算法采用广播扩散的方法，先要在网络的所有节点集中选择一个节点 265 s 做为源节点，然后按照次算法提供的染色方案，最终被标记为黑色的节点作为网络的骨干 节点。算法所需要的时间为网络的最大路径长度。因此，若令网络的平均节点度数为v Δ = Δ ， 则本算法的时间复杂度为O(Δ3)。 4 仿真与结果分析 为了测试FWCDS 算法的性能，我们仿真实现了FWCDS 算法与MISB 算法[8]，Dai’s 270 算法[7]，以及OHDC 算法[9]在不同的网络环境下所得到的CDS 个数，额外消息数以及算法 的收敛时间。 网络拓扑随机产生在1000m×1000m的正方形区域上，节点的位置服从均匀分布，如 果产生的网络不是连通的，则重新产生直到整个网络连通为止。网络中的每个节点带有相同 的通信半径150m。对于每个仿真实验，产生300 个不同的网络拓扑。网络的节点数从100 275 到450 个，间隔为50 个。实验如下： 实验1：仿真比较FWCDS 算法与Dai’s 算法、OHDC 算法以及MISB 算法的CDS 大小。 图7 FWCDS 算法与Dai’s 算法、OHDC 算法以及MISB 算法关于CDS 大小的比较 Fig. 7 Compare CDS size of FWCDS, Dai’s, OHDC and MISB 280 图7 显示了实验1 的结果。MISB 算法比起其他3 个算法具有最小的CDS 尺寸，FWCDS 算法在节点密度较小时与OHDC 算法具有接近的CDS 个数，但当节点密度较大时，本算法 要优于OHDC算法，Dai’s 算法在节点密度较大时曲线趋于水平，但CDS 个数仍然比FWCDS 算法大。因此，FWCDS 算法在CDS 个数上要优于Dai’s 和OHDC 算法，在节点密度较小 285 时接近MISB 算法。 实验2：仿真比较FWCDS 算法与Dai’s 算法、OHDC 算法以及MISB 算法的额外消息 数。 根据额外消息数的定义，节点之间的邻居发现通过MAC 层的beacon 完成，因此不属 学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表 |
