摘 要：由于傳感器網(wǎng)絡(luò)所使用無線信道的共享性和相互干擾，節(jié)點(diǎn)間數(shù)據(jù)廣播會產(chǎn)生資源沖突，廣播調(diào)度要解決的即是為每個節(jié)點(diǎn)分配到一個無沖突傳輸時隙，其目標(biāo)是找到晟優(yōu)時分復(fù)用（TDMA：Time division multiple access）調(diào)度解，使得幀長度最短而信道利用率最大．提出基于神經(jīng)網(wǎng)絡(luò)的兩階段混合廣播調(diào)度算法．在階段一，使用改進(jìn)的頂點(diǎn)著色算法來獲得調(diào)度所需最短時隙數(shù)目；在階段二，使用模糊Hopfield將節(jié)點(diǎn)模糊聚類為M類，同類節(jié)點(diǎn)可以在同一時隙被調(diào)度，不同類節(jié)點(diǎn)必須在不同時隙被調(diào)度．用該算法對3個測試拓?fù)鋱D進(jìn)行調(diào)度，實(shí)驗(yàn)結(jié)果表明該算法比其他算法能獲得更短的幀 長度和更低的網(wǎng)絡(luò)延遲，證明了所提算法的可行性和有效性．
關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；廣播調(diào)度問題；Hopfield神經(jīng)網(wǎng)絡(luò)；圖著色
1 引 言
在監(jiān)測區(qū)域內(nèi)，以隨機(jī)方式分布的集成有傳感器、數(shù)據(jù)處理單元和無線通信模塊的微小節(jié)點(diǎn)通過自組織方式便構(gòu)成了無線傳感器網(wǎng)絡(luò)（WSN） [1] ．WSN 中節(jié)點(diǎn)經(jīng)常需要廣播消息或數(shù)據(jù)，用于同步機(jī)制、拓?fù)淇刂苹蚵酚山⑴c維護(hù)等．由于無線鏈路的共享與開放性，很容易造成消息傳輸時的相互沖突，若節(jié)點(diǎn)的多個相鄰節(jié)點(diǎn)同時向該節(jié)點(diǎn)廣播消息，則必然產(chǎn)生相互干擾或沖突并造成廣播消息不能正確收發(fā)，大多數(shù)WSN網(wǎng)絡(luò)此時要求源節(jié)點(diǎn)重傳，而造成節(jié)點(diǎn)能量額外消耗，從因此需要對節(jié)點(diǎn)的消息廣播進(jìn)行合理調(diào)度以延長網(wǎng)絡(luò)壽命[2] ．大多數(shù)WSN使用時分復(fù)用（TDMA）作為無線信道共享與接入方式[3] ,本文研究TDMA下WSN網(wǎng)絡(luò)廣播調(diào)度問題（broadcast scheduling problem,BSP），期望能實(shí)現(xiàn)在網(wǎng)絡(luò)拓?fù)浞€(wěn)定下，節(jié)點(diǎn)間消息無沖突傳輸，并最大化信道利用率．
2 廣播調(diào)度問題
記WSN網(wǎng)絡(luò)為無向簡單圖G＝（V,E）,頂點(diǎn)V＝｛vi｝代表網(wǎng)絡(luò)中傳感節(jié)點(diǎn)，邊E＝｛eij｝為節(jié)點(diǎn)問傳輸鏈路．若傳感節(jié)點(diǎn)i∈V，j∈V，且i,j在彼此的傳感半徑內(nèi)，則稱i,j為一跳相鄰節(jié)點(diǎn)，即存在無線鏈路eij∈E；若i，j間不存在一跳相鄰節(jié)點(diǎn)，但存在中間節(jié)點(diǎn)k使得eik∈E且ekj∈E，則稱節(jié)點(diǎn)i，j為二跳相鄰節(jié)點(diǎn)．傳感節(jié)點(diǎn)問要能正確收發(fā)數(shù)據(jù)，必須滿足以下約束條件[3]:1）節(jié)點(diǎn)不能同時接收與發(fā)送數(shù)據(jù)，即若eij∈E，則節(jié)點(diǎn)i與節(jié)點(diǎn)j必須分配以不同時隙來傳輸數(shù)據(jù)，稱作第1類約束；2）節(jié)點(diǎn)不能同時接收兩個或多個相鄰節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，即若ej∈且ekj∈E，則節(jié)點(diǎn)i,k必須在不同時隙發(fā)送數(shù)據(jù)以避免在節(jié)點(diǎn)j處發(fā)生沖突，稱作第2類約束．定義二進(jìn)制矩陣S＝｛sij｝表示一個傳輸調(diào)度，ρ為WSN的帶寬利用率，用S′＝｛S1，S2，…｝表示無干擾可行調(diào)度集，則最優(yōu)調(diào)度問題描述如下:
對于給定拓?fù)鋀SN網(wǎng)絡(luò)，尋找最優(yōu)調(diào)度Sopt∈S′,在滿足第l類和第2類約束條件下，具有最短的幀長度Sopt和最大的信道帶寬利用率ρopt．
3 基于神經(jīng)網(wǎng)絡(luò)的兩階段調(diào)度方法
3.1 階段
對給定拓?fù)涞臒o向圖，階段一目標(biāo)是使幀時隙長度降為最短，即用最少時隙數(shù)M完成調(diào)度．圖的頂點(diǎn)著色問題（VCP）求解是NP完全的，目前的求解方法主要是啟發(fā)式算法．雖然順序著色只能找到次優(yōu)解,但其復(fù)雜度最小。計算量比其他最優(yōu)和次優(yōu)算法要低1～2個數(shù)量級．考慮到傳感節(jié)點(diǎn)的能量和計算能力有限，這里結(jié)合最大飽和度與最大度數(shù)準(zhǔn)則設(shè)計新的頂點(diǎn)著色算法．
算法包含如下3個處理環(huán)節(jié)：1）確定幀時隙長度上下界．對于有N個結(jié)點(diǎn)WSN網(wǎng)絡(luò)，最優(yōu)幀長度范圍為Lm≤M≤N，其中Lm＝maxdegi＋1,degi為節(jié)點(diǎn)i的度數(shù)；2）執(zhí)行初始化時隙分配．令待初始化節(jié)點(diǎn)集合為G＝｛ni,i=1,2,…,Lm｝,G由圖中具有最大度數(shù)的節(jié)點(diǎn)n1及與n1相距l(xiāng)跳節(jié)點(diǎn)的相鄰節(jié)點(diǎn)ni構(gòu)成，將時隙i分配給節(jié)點(diǎn)ni；3）改進(jìn)的順序著色算法．
算法
輸入：原始WSN拓?fù)銰＝（V,E）.
輸出：節(jié)點(diǎn)時隙調(diào)度矩陣S=｛Sij｝N×M.
Step1 網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)渑判颍畬?jié)點(diǎn)按照度數(shù)遞減規(guī)律排序并存儲為隊(duì)列Q=｛ni,i＝1,2,…，N｝，得到網(wǎng)絡(luò)節(jié)點(diǎn)的最大度數(shù)△G；
Step2 確定時隙下確界．置初始時隙數(shù)M＝△G十1，調(diào)度矩陣S＝｛0｝N×M；
Step3 節(jié)點(diǎn)時隙初始化調(diào)度．不失一般性，將第i個時隙分配到節(jié)點(diǎn)ni，得已調(diào)度節(jié)點(diǎn)集Gc＝｛ni,i＝1,2,…，M｝,令Sii=1,計數(shù)器P＝M＋1；
Step4 對未調(diào)度節(jié)點(diǎn)排序．按照最大飽和度準(zhǔn)則對剩下的N-Lm個頂點(diǎn)排序，存儲為隊(duì)列
Q′＝｛nj,j=Lm+1,…,N｝；
Step5 調(diào)度Q′中節(jié)點(diǎn)nj．搜索滿足2跳內(nèi)約束的時隙，記不同時隙數(shù)為Nc，依據(jù)Nc值分別執(zhí)行以下處理：
①若Nc＞1,將第一個可用時隙指派給節(jié)點(diǎn)nj，Sij=1；
②若Nc＝1,將該唯一時隙指派給節(jié)點(diǎn)nj，Sij=1；
③若Nc＝0,則此時無空閑時隙指派給節(jié)點(diǎn)nj，轉(zhuǎn)Step7；
Step6 判斷是否所有節(jié)點(diǎn)已完成調(diào)度．若P＝N，算法停止；否則令P=P＋1，轉(zhuǎn)Step5；
Step7 新增一個時隙，重新調(diào)度．令M＝M＋1，轉(zhuǎn)Step5．
算法Step1排序的計算量為O（|N|）,Step4排序的計算量為O（|N-Lm|3）,N為網(wǎng)絡(luò)頂點(diǎn)數(shù)，Lm是頂點(diǎn)最大度數(shù)加1,整個算法的計算量約為O（|N|3）
3.2 階段二
在階段二，使用模糊Hopfield神經(jīng)網(wǎng)絡(luò)對WSN網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行模糊聚類[4、5] ，分類數(shù)為階段一中求得的M，輸入樣本為待調(diào)度節(jié)點(diǎn)．同一類中的所有節(jié)點(diǎn)可以在同一個時隙同時被調(diào)度；不同類中的節(jié)點(diǎn)必須在不同時隙被調(diào)度．考慮N×M結(jié)構(gòu) Hopfield網(wǎng)絡(luò)，節(jié)點(diǎn)i是否在第j個時隙傳輸數(shù)據(jù)由Hopfield處在（i,j）位置神經(jīng)元的輸出Pij確定．利用第2節(jié)中的約束條件來設(shè)計優(yōu)化目標(biāo)，即Hopfield網(wǎng)絡(luò)能量函數(shù)E．首先，所有的數(shù)據(jù)包應(yīng)該在一個時隙內(nèi)同步傳送；其次，當(dāng)節(jié)點(diǎn)i時隙j傳輸數(shù)據(jù)時，其他所有節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)不能分配在時隙j；最后，當(dāng)節(jié)點(diǎn)i傳輸數(shù)據(jù)時，i的二跳相鄰節(jié)點(diǎn)也不能被分配到時隙j去傳輸數(shù)據(jù)．能量函數(shù)E大小反映網(wǎng)絡(luò)當(dāng)前時隙調(diào)度與最優(yōu)調(diào)度間差距，在考慮所有以上約束條件后，本文所設(shè)計能量函數(shù)E如下：
其中：ni表示第i個節(jié)點(diǎn)，dij為節(jié)點(diǎn)i，j間歐氏距離，權(quán)值w1和w2為正且滿足w1+w2＝l,權(quán)系數(shù)取值會影響網(wǎng)絡(luò)收斂性，需合理選取．Vi為第i類歐氏中心，即
．（i,j）位置神經(jīng)元輸入為Iij＝（ni-vi）2＋△Iij，神經(jīng)元輸出為Pij，外部激勵項(xiàng)△Iij取常數(shù)．Hopfield網(wǎng)絡(luò)優(yōu)化流程如下：
Step1 初始化網(wǎng)絡(luò)內(nèi)神經(jīng)元（i,j）輸出Pij:
Step2 更新模糊隸屬度函數(shù)
，重新計算類中心vi；
Step3 由式（1）計算能量函數(shù)；
Step4 判斷網(wǎng)絡(luò)是否收斂于穩(wěn)定狀態(tài)，若|E（n+1）-E（n）|〉ε（ε為閾值），轉(zhuǎn)Step2；否則，網(wǎng)絡(luò)收斂，算法終止．
4 實(shí)驗(yàn)結(jié)果與分析
對TS-HNN算法的調(diào)度性能進(jìn)行分析，與平均退火策略（MFA） [2] 、基于遺傳算法的Hopfield神經(jīng)網(wǎng)絡(luò)（HNN-GA） [4]和含噪混沌神經(jīng)網(wǎng)絡(luò)（NC-NN） [5]3種方法調(diào)度性能比較．使用3種不同拓?fù)涞臏y試網(wǎng)絡(luò)Case 1～3[6] . 實(shí)驗(yàn)中使用的數(shù)據(jù)包為固定長度，時隙長度設(shè)置為每包所需傳輸時間；節(jié)點(diǎn)問以泊松分布隨機(jī)收發(fā)數(shù)據(jù)包．每種拓?fù)浣Y(jié)構(gòu)運(yùn)行50次，取平均值進(jìn)行比較．表1給出本文算法（TS-HNN）與其他3種方法求解得到的網(wǎng)絡(luò)最小延遲η和幀長度M．在節(jié)點(diǎn)數(shù)較少（Case 1）或平均度數(shù)不高時（Case 3），4種算法都能找到最優(yōu)幀長M＝8；對于節(jié)點(diǎn)數(shù)較多具有復(fù)雜結(jié)構(gòu)網(wǎng)絡(luò)（Case 2），TS-HNN也能找到次優(yōu)幀長；且TS-HNN在3種拓?fù)湎露季哂凶畹偷木W(wǎng)絡(luò)時延．測試拓?fù)銫ase 1調(diào)度結(jié)果如圖l所示，填充有黑色的方格代表所在節(jié)點(diǎn)（node）在該時隙（slot）可被調(diào)度．圖2詳細(xì)描述了網(wǎng)絡(luò)時延隨數(shù)據(jù)包（packets）服務(wù)速率變化的情況．隨著服務(wù)速率增加，網(wǎng)絡(luò)時延也在變長，在節(jié)點(diǎn)數(shù)較少時（Case 1），4種算法的時延相差不大，如圖 2（a）；當(dāng)節(jié)點(diǎn)數(shù)增加時（Case 2）,4種算法下的網(wǎng)絡(luò)時延差異明顯增大，如圖2（b）．
5 結(jié)束語
調(diào)度是一類經(jīng)典的帶約束資源優(yōu)化分配問題本文以傳感器網(wǎng)絡(luò)為研究背景，提出了一種基于圖著色與神經(jīng)網(wǎng)絡(luò)的兩階段廣播調(diào)度算法．算法的基本思想是將廣播調(diào)度問題求解轉(zhuǎn)化為兩階段目標(biāo)尋優(yōu)：第1階段借助頂點(diǎn)著色思想搜索給定拓?fù)鋀SN的具有最短時隙數(shù)目的幀結(jié)構(gòu)；第2階段在上述幀結(jié)構(gòu)下使用模糊Hopfield網(wǎng)絡(luò)為每個節(jié)點(diǎn)增添額外的無沖突傳輸時隙，從而使得在原有幀長度下盡可能多的讓更多節(jié)點(diǎn)實(shí)現(xiàn)并行無干擾傳輸，以最大化信道利用率，仿真實(shí)驗(yàn)證明了所提方法的有效性．
參考文獻(xiàn)：
[1]PENG Y,SOONG B H,WANG L.Broadcast scheduling in packet radio networks using mixed tabu- greedy algorithm[J].Electronics letters,2004,40（6）:375-376.
[2]WANG G,ARISARIN.Optimal broadcast scheduling in packet radio networks using mean gield annealing[J].IEEE Journal on Selected Areas in Communications.1997,15（2）:250-260.
[3]YEO J,LEE H.An efficient broadcast scheduling algorithm for tdmad- hoc networks[J].Computer Operations Research,2002,29（13）:1793-1806.
