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

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

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

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

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

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

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