摘  要：由于傳感器網絡所使用無線信道的共享性和相互干擾，節(jié)點間數(shù)據(jù)廣播會產生資源沖突,，廣播調度要解決的即是為每個節(jié)點分配到一個無沖突傳輸時隙,，其目標是找到晟優(yōu)時分復用（TDMA：Time division multiple access）調度解，使得幀長度最短而信道利用率最大．提出基于神經網絡的兩階段混合廣播調度算法．在階段一,，使用改進的頂點著色算法來獲得調度所需最短時隙數(shù)目,；在階段二，使用模糊Hopfield將節(jié)點模糊聚類為M類,，同類節(jié)點可以在同一時隙被調度,，不同類節(jié)點必須在不同時隙被調度．用該算法對3個測試拓撲圖進行調度，實驗結果表明該算法比其他算法能獲得更短的幀長度和更低的網絡延遲,，證明了所提算法的可行性和有效性．

關鍵詞：無線傳感器網絡,；廣播調度問題；Hopfield神經網絡,；圖著色

1  引  言

      在監(jiān)測區(qū)域內,，以隨機方式分布的集成有傳感器,、數(shù)據(jù)處理單元和無線通信模塊的微小節(jié)點通過自組織方式便構成了無線傳感器網絡（WSN） ^[1] ．WSN 中節(jié)點經常需要廣播消息或數(shù)據(jù)，用于同步機制,、拓撲控制或路由建立與維護等．由于無線鏈路的共享與開放性,，很容易造成消息傳輸時的相互沖突，若節(jié)點的多個相鄰節(jié)點同時向該節(jié)點廣播消息,，則必然產生相互干擾或沖突并造成廣播消息不能正確收發(fā)，大多數(shù)WSN網絡此時要求源節(jié)點重傳,，而造成節(jié)點能量額外消耗,，從因此需要對節(jié)點的消息廣播進行合理調度以延長網絡壽命^[2] ．大多數(shù)WSN使用時分復用（TDMA）作為無線信道共享與接入方式^[3] ,本文研究TDMA下WSN網絡廣播調度問題（broadcast scheduling problem,BSP），期望能實現(xiàn)在網絡拓撲穩(wěn)定下,，節(jié)點間消息無沖突傳輸,，并最大化信道利用率．

2  廣播調度問題

      記WSN網絡為無向簡單圖G＝（V,E）,頂點V＝｛v_i｝代表網絡中傳感節(jié)點，邊E＝｛e_ij｝為節(jié)點問傳輸鏈路．若傳感節(jié)點i∈V,，j∈V,，且i,j在彼此的傳感半徑內，則稱i,j為一跳相鄰節(jié)點,，即存在無線鏈路eij∈E,；若i,，j間不存在一跳相鄰節(jié)點,，但存在中間節(jié)點k使得e_ik∈E且e_kj∈E,，則稱節(jié)點i,，j為二跳相鄰節(jié)點．傳感節(jié)點問要能正確收發(fā)數(shù)據(jù),，必須滿足以下約束條件[3]:1）節(jié)點不能同時接收與發(fā)送數(shù)據(jù),，即若e_ij∈E,，則節(jié)點i與節(jié)點j必須分配以不同時隙來傳輸數(shù)據(jù),，稱作第1類約束,；2）節(jié)點不能同時接收兩個或多個相鄰節(jié)點發(fā)送的數(shù)據(jù),，即若e_j∈且e_kj∈E，則節(jié)點i,k必須在不同時隙發(fā)送數(shù)據(jù)以避免在節(jié)點j處發(fā)生沖突,，稱作第2類約束．定義二進制矩陣S＝｛sij｝表示一個傳輸調度,，ρ為WSN的帶寬利用率，用S′＝｛S¹,，S²,，…｝表示無干擾可行調度集，則最優(yōu)調度問題描述如下:

      對于給定拓撲WSN網絡,，尋找最優(yōu)調度S^opt∈S′,在滿足第l類和第2類約束條件下,，具有最短的幀長度S^opt和最大的信道帶寬利用率ρ^opt．

3  基于神經網絡的兩階段調度方法

3.1  階段

      對給定拓撲的無向圖，階段一目標是使幀時隙長度降為最短,，即用最少時隙數(shù)M完成調度．圖的頂點著色問題（VCP）求解是NP完全的,，目前的求解方法主要是啟發(fā)式算法．雖然順序著色只能找到次優(yōu)解,但其復雜度最小,。計算量比其他最優(yōu)和次優(yōu)算法要低1～2個數(shù)量級．考慮到傳感節(jié)點的能量和計算能力有限，這里結合最大飽和度與最大度數(shù)準則設計新的頂點著色算法．

      算法包含如下3個處理環(huán)節(jié)：1）確定幀時隙長度上下界．對于有N個結點WSN網絡,，最優(yōu)幀長度范圍為Lm≤M≤N,，其中Lm＝maxdegi＋1,degi為節(jié)點i的度數(shù)；2）執(zhí)行初始化時隙分配．令待初始化節(jié)點集合為G＝｛n_i,i=1,2,…,L_m｝,G由圖中具有最大度數(shù)的節(jié)點n₁及與n₁相距l(xiāng)跳節(jié)點的相鄰節(jié)點n_i構成,，將時隙i分配給節(jié)點n_i,；3）改進的順序著色算法．

      算法

      輸入：原始WSN拓撲G＝（V,E）.

      輸出：節(jié)點時隙調度矩陣S=｛S_ij｝_N×M.

      Step1  網絡節(jié)點拓撲排序．對節(jié)點按照度數(shù)遞減規(guī)律排序并存儲為隊列Q=｛ni,i＝1,2,…，N｝,，得到網絡節(jié)點的最大度數(shù)△G,；

      Step2  確定時隙下確界．置初始時隙數(shù)M＝△G十1，調度矩陣S＝｛0｝_N×M,；

      Step3  節(jié)點時隙初始化調度．不失一般性,，將第i個時隙分配到節(jié)點n_i，得已調度節(jié)點集Gc＝｛n_i,i＝1,2,…,，M｝,令S_ii=1,計數(shù)器P＝M＋1,；

      Step4  對未調度節(jié)點排序．按照最大飽和度準則對剩下的N-L_m個頂點排序，存儲為隊列
 

Q′＝｛n_j,j=L_m+1,…,N｝,；

      Step5  調度Q′中節(jié)點n_j．搜索滿足2跳內約束的時隙,，記不同時隙數(shù)為Nc，依據(jù)Nc值分別執(zhí)行以下處理：

      ①若N_c＞1,將第一個可用時隙指派給節(jié)點n_j,，Sij=1,；

      ②若N_c＝1,將該唯一時隙指派給節(jié)點n_j，S_ij=1,；

      ③若N_c＝0,則此時無空閑時隙指派給節(jié)點n_j,，轉Step7；

      Step6  判斷是否所有節(jié)點已完成調度．若P＝N,，算法停止,；否則令P=P＋1，轉Step5,；

      Step7  新增一個時隙,，重新調度．令M＝M＋1，轉Step5．

      算法Step1排序的計算量為O（|N|）,Step4排序的計算量為O（|N-Lm|³）,N為網絡頂點數(shù),，Lm是頂點最大度數(shù)加1,整個算法的計算量約為O（|N|³）

3.2  階段二

      在階段二,，使用模糊Hopfield神經網絡對WSN網絡節(jié)點進行模糊聚類^[4、5] ,，分類數(shù)為階段一中求得的M,，輸入樣本為待調度節(jié)點．同一類中的所有節(jié)點可以在同一個時隙同時被調度；不同類中的節(jié)點必須在不同時隙被調度．考慮N×M結構 Hopfield網絡，節(jié)點i是否在第j個時隙傳輸數(shù)據(jù)由Hopfield處在（i,j）位置神經元的輸出Pij確定．利用第2節(jié)中的約束條件來設計優(yōu)化目標,，即Hopfield網絡能量函數(shù)E．首先,，所有的數(shù)據(jù)包應該在一個時隙內同步傳送；其次,，當節(jié)點i時隙j傳輸數(shù)據(jù)時,，其他所有節(jié)點i的相鄰節(jié)點不能分配在時隙j；最后,，當節(jié)點i傳輸數(shù)據(jù)時,，i的二跳相鄰節(jié)點也不能被分配到時隙j去傳輸數(shù)據(jù)．能量函數(shù)E大小反映網絡當前時隙調度與最優(yōu)調度間差距，在考慮所有以上約束條件后,，本文所設計能量函數(shù)E如下：
 

      其中：n_i表示第i個節(jié)點,，d_ij為節(jié)點i，j間歐氏距離,，權值w₁和w₂為正且滿足w1+w2＝l,權系數(shù)取值會影響網絡收斂性，需合理選?。甐_i為第i類歐氏中心,，即．（i,j）位置神經元輸入為I_ij＝（n_i-v_i）²＋△I_ij，神經元輸出為P_ij,，外部激勵項△I_ij取常數(shù)．Hopfield網絡優(yōu)化流程如下：

      Step1  初始化網絡內神經元（i,j）輸出P_ij:
 

      Step2  更新模糊隸屬度函數(shù),，重新計算類中心v_i；

      Step3  由式（1）計算能量函數(shù),；

      Step4  判斷網絡是否收斂于穩(wěn)定狀態(tài),，若|E（n+1）-E（n）|〉ε（ε為閾值），轉Step2,；否則,，網絡收斂，算法終止．

4  實驗結果與分析

      對TS-HNN算法的調度性能進行分析,，與平均退火策略（MFA） ^[2] ,、基于遺傳算法的Hopfield神經網絡（HNN-GA） [^4]和含噪混沌神經網絡（NC-NN） ^[5]3種方法調度性能比較．使用3種不同拓撲的測試網絡Case 1～3^[6] . 實驗中使用的數(shù)據(jù)包為固定長度，時隙長度設置為每包所需傳輸時間,；節(jié)點問以泊松分布隨機收發(fā)數(shù)據(jù)包．每種拓撲結構運行50次,，取平均值進行比較．表1給出本文算法（TS-HNN）與其他3種方法求解得到的網絡最小延遲η和幀長度M．在節(jié)點數(shù)較少（Case 1）或平均度數(shù)不高時（Case 3），4種算法都能找到最優(yōu)幀長M＝8,；對于節(jié)點數(shù)較多具有復雜結構網絡（Case 2）,，TS-HNN也能找到次優(yōu)幀長；且TS-HNN在3種拓撲下都具有最低的網絡時延．測試拓撲Case 1調度結果如圖l所示,，填充有黑色的方格代表所在節(jié)點（node）在該時隙（slot）可被調度．圖2詳細描述了網絡時延隨數(shù)據(jù)包（packets）服務速率變化的情況．隨著服務速率增加,，網絡時延也在變長，在節(jié)點數(shù)較少時（Case 1），4種算法的時延相差不大,，如圖 2（a）,；當節(jié)點數(shù)增加時（Case 2）,4種算法下的網絡時延差異明顯增大，如圖2（b）．
 

5  結束語

      調度是一類經典的帶約束資源優(yōu)化分配問題本文以傳感器網絡為研究背景,，提出了一種基于圖著色與神經網絡的兩階段廣播調度算法．算法的基本思想是將廣播調度問題求解轉化為兩階段目標尋優(yōu)：第1階段借助頂點著色思想搜索給定拓撲WSN的具有最短時隙數(shù)目的幀結構,；第2階段在上述幀結構下使用模糊Hopfield網絡為每個節(jié)點增添額外的無沖突傳輸時隙，從而使得在原有幀長度下盡可能多的讓更多節(jié)點實現(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.