工業(yè)無線網(wǎng)絡簇信道分配算法研究.pdf

1、隨著信息技術的高速發(fā)展，工業(yè)無線網(wǎng)絡成為自動化領域研究的熱點。它成為一種新興的，面向設備間短程的，信息交互的工業(yè)無線通信技術，適合部署在工業(yè)生產現(xiàn)場環(huán)境或人類不宜到達的區(qū)域，具有很強的抗干擾能力、超低能耗、實時通信等技術特征，是對現(xiàn)有工業(yè)通信技術在工業(yè)應用方向上的功能擴展和提升，也是對現(xiàn)有的現(xiàn)場總線控制網(wǎng)絡的重要補充和完善。WIA-PA是我國863項目支持下，由中科院、西南大學等10余家單位自主研發(fā)的適用于過程自動化的工業(yè)無線網(wǎng)絡技術，

2、其形成的技術規(guī)范于2008年獲得IEC的采納，列入國際標準制定計劃。
　　 WIA-PA網(wǎng)絡底層基于IEEE802.15.4標準，物理層為IEEE802.15.4的各種信道，鏈路層兼容了IEEE802.15.4的超幀結構并根據(jù)工業(yè)無線的需求對其進行了擴展。WIA-PA采用集中式與分布式相結合的無線通信資源分配方式。在MESH層，網(wǎng)關為路由設備集中分配資源，在STAR層，路由為下面的每個現(xiàn)場設備分配資源。本文主要研究WIA-PA在

3、MESH層網(wǎng)關為路由設備集中分配的資源——簇信道。所謂簇信道，即是每個簇在進行簇內事務時所使用的信道。為了避免干擾，保證網(wǎng)絡通信的可靠性，相鄰的簇使用不同的簇信道進行通信，不相鄰的在通信距離以外的簇則可以使用相同的信道。因此，WIA-PA的簇信道分配問題可轉化為圖的點著色問題。
　　 作者在參與WIA-PA項目的工作中，針對簇信道分配問題，進行了研究和探討，經(jīng)過分析表明目前現(xiàn)有的點著色算法不能滿足WIA-PA這一工業(yè)無線網(wǎng)絡的特

4、定要求。傳統(tǒng)的經(jīng)典算法以及啟發(fā)式算法與其混合算法復雜度高，運行時間長，不能滿足WIA-PA的實時性要求；Welsh-Powell算法執(zhí)行效率快，卻不能適應網(wǎng)絡拓撲的變化。為此，針對WIA-PA工業(yè)無線網(wǎng)絡，本文基于通過每個代表一種顏色的集合維護不相鄰的、可以著相同顏色的頂點，其信道分配的過程就是將頂點劃分圖的獨立集的過程，也就是將頂點加入到某個集合的過程的思想，提出了一種簡單高效的基于集合思想的圖著色算法SBK-Coloring。該算法

5、復雜度低，效率高；且當網(wǎng)絡拓撲結構改變時，保留了原先的分配策略，避免了大量網(wǎng)絡信息的更新與網(wǎng)絡參數(shù)的重新設置，并提高了網(wǎng)絡的實時性，降低了節(jié)點能耗。
　　 通過仿真實驗，與兩個典型的圖著色算法混合遺傳算法、Welsh-Powell算法進行分析比較，表明SBK-Coloring算法的執(zhí)行效率明顯超過了混合遺傳算法，不管是不同規(guī)模的稀疏圖還是不同規(guī)模的稠密圖，其算法的執(zhí)行時間均不超過幾十毫秒，而混合遺傳算法少到幾秒，多至幾分鐘幾十分

6、鐘不等。SBK-Coloring算法相比Welsh-Powell算法，在中小規(guī)模的稀疏圖上表現(xiàn)相當，但隨著問題規(guī)模的擴大，優(yōu)勢就越明顯。當頂點數(shù)增加到400個時，SBK-Coloring算法相對Welsh-Powell算法的執(zhí)行時間大約提高了47.8％，當頂點數(shù)增加到1000時，則大約提高了56.5％。同樣，在稠密圖上，當頂點數(shù)增加到95個時提高了約56.6％，增加到500個頂點時約提高了88.7％，1000個頂點時約提高了76.1％。