| QCFRA_W Algorithm(G,s,D)
1. Initialize tree T with sourcenode s and clear Q;
2. For all w∈VDo//算法初始化
3. Ifw∈ADJ(s) Then
4. Dist[w]←C(s,w); Mist[w]←C(s,w);Parent[w]←s;
5. Q←Q∪{w};
6.Else
7. Dist[w]←∞; Mist[w]←∞; Parent[w]←nil;
8.End If
9. End For
10. Dist[s]←0;Mist[s]←0; Parent[s]←nil; //源节点为第 1 个已计算节点
11. While there exists a node in D thathas not been added to tree T Do
12. Select node ufrom Q which statisfies Dist[u]=min{Dist[m]|m∈Q};
13. If u isa destination nodeThen //如果是目的节点则将最短路径添加到 T
14. Establishshortest path from source node s to node u;
15．Mist[u]←0; //目的节点则需将 Mist 向量清零
16. End If
17. For all w∈ADJ(u) Do
18. IfDist[w]=∞ Then Q←Q∪{w} End If
19. IfDist[u]+C(u,w)
20.Dist[w]←Dist[u]+C(u,w); Mist[w]←Mist[u]+C(u,w); Parent[w]←u;
21. Else IfDist[u]+C(u,w)=Dist[w]Then//最短路径不惟一
22.If Mist[u]+C(u,w)
23.Mist[w]←Mist[u]+C(u,w); Parent[w]←u; //记录最优父节点
24.End If
25. End If
26. End For
27. End While
4 算法复杂性分析
4.1 算法时间复杂度分析
用 n 表示图 G 中节点数目,e 表示所有边的数目,d(u)表示节点 u 的邻接节点数目.
算法的初始化时间复杂度都是 T1=O(n). 算法的关键是从待发展节点序列Q 中选择最合适的节点进行下一步扩展.解决这一问题的关键在于使用什么样的数据结构.较常用的数据结构有数组、单双链表、堆栈、哈希散列和队列等.将待发展节点序列 Q 构造成 Fibonacci堆,则从 Q 中输出最小节点等操作可以在 O(logn)时间内完成.每一个节点最多往序列 Q 添加一次,在将该节点添加到生成树上时从 Q 中取出,并且每添加一个新节点 u 到生成树上后需要访问 d(u)个 u 的邻接节点.在所构造的 SPT 中最多包含 n 个节点,所以算法构造 SPT 时间复杂度为
T2 = nlogn +  = O(nlogn + e) .
算法的总时间复杂度为
T = T1 +T2 = O(n) + O(nlogn + e) = O(n + nlogn + e) = O(nlogn + e) .
4.2 算法空间复杂度分析
QCFRA_W 算法除了进行图的存储以外,还需要 3 个包含n 个分量的一维向量和一个待发展节点集来存储计算过程的中间信息,而待发展节点集中最多包含 n 个节点.因此,采用图的邻接表存储方式, QCFRA算法的空间复杂度为
S = O(e + n) + 4O(n) = O(e +5n) = O(e + n) .
1.1 5仿真试验
为了验证QCFRA-W的效率性，对其进行了仿真。在实验中，我们共仿真了四个算法：QCFRA-W，最大可用带宽路径算法QCFRA-W-BW，最大延时路径算法QCFRA-W-DELAY，最大延时抖动路径算法QCFRA-W-DJ，以上算法的网络拓扑采用随机网络模型。论文发表，分布式路由。网络覆盖面积100×100m2，网络节点数目设置为100个，每个节点的发射范围被限制在半径为20m的圆内。论文发表，分布式路由。当两个节点处在彼此的发射范围内，彼此之间就存在一条链路。节点的平均度数是7.48。
图1是采用上述算法的100个节点的网络拓扑图，编号为21的节点为源节点，随机选取剩余节点作为目标节点，主要参数取如下值：k=0.0005，w1=0.2，w2=0.3，w3=0.4，w4=0.1，energy_req均匀分布于[50,200]个能量单位，bandwidth_req=100K，delay_req=300ms，delay_jitter_req=3ms。
为了比较QCFRA-W算法性能，通过调整权值系数将算法进行简化处理，当w1=0，w2=1，w3=0，w4=0时得到最大可用带宽路径算法QCFRA-W-BW，当w1=0，w2=0，w3=1，w4=0时得到延时约束路径算法QCFRA-W-DELAY，当w1=0，w2=0，w3=0，w4=1时得到延时抖动约束路径算法QCFRA-W-DJ，当w1=0.5，w2=0.3，w3=0.1，w4=0.1时得到路径算法QCFRA-W。图3和图4分别是QCFRA-W、QCFRA-W-BW、QCFRA-W-DELAY、QCFRA-W-DJ四种算法在不同的网络规模下多播树费用和路由成功率的比较结果。实验结果表明，QCFRA-W、QCFRA-W-BW、QCFRA-W-DELAY、QCFRA-W-DJ四种算法在路由过程中由于都有可行链路的约束，所以它们有相近的多播树费用和路由成功率。但是用QCFRA-W算法生成的多播树，不但满足多QoS约束，同时更能真实反映WSN本质特征，所以该算法在路由成功率、多播树费用方面均具有较好的特性。
 将QCFRA-W算法和SAR算法、DD算法进行比较。网络覆盖面积100×100m2，网络节点数目设置为100个、节点传输距离为20m、数据传输率为250Kb、出错率为0、数据包长度为128bit，网络节点分布如图1，其中编号为21的节点代表Sink节点，其余节点代表传感节点。论文发表，分布式路由。
实验中，从第2s开始，每隔2s，网络都有30个随机节点构造信息包向Sink节点发送。初始时设定所有节点的初始能量为9000个能量单位，接收一个消息消耗2个单位能量，发送一个消息消耗4个单位能量。实验对两种算法的网络总体能量消耗数据进行了收集整理。由图5可以看出，和SAR算法、DD算法相比，QCFRA-W算法能显著节省网络的整体能量。结合能量均衡的路由策略，网络生存期能得到明显提高。仿真结果表明，和SAR算法相比，QCFRA-W算法的网络生存期提高了78.4%。和DD算法相比，QCFRA-W算法的网络生存期提高了76%。
1.2 5结论
多播路由算法QCFRA-W通过抉择因子能反映无线网络真实特性的剩余能量、带宽和延时等重要因素，同时通过可行链路的定义使生成的多播链路满足QoS约束，从而减少了算法的时间复杂度和消息复杂度，并与SAR算法和DD算法在能量消耗方面进行了比较。仿真实验表明：算法QCFRA-W在路由成功率、多播树费用方面均具有较好特性。
参考文献
[1]LiuYueyang,JiHong,YueGuangxin.Routingprotocolwithoptimallocationofaggregationinwirelesssensor
networks[J].TheJournalofChinaUniversitiesofPostsandTelecommunications,2006,13(1):125.
2/2 首页 上一页 1 2 |
