摘 要：由于傳感器網絡所使用無線信道的共享性和相互干擾，節點間數據廣播會產生資源沖突，廣播調度要解決的即是為每個節點分配到一個無沖突傳輸時隙，其目標是找到晟優時分復用（TDMA：Time division multiple access）調度解，使得幀長度最短而信道利用率最大．提出基于神經網絡的兩階段混合廣播調度算法．在階段一，使用改進的頂點著色算法來獲得調度所需最短時隙數目；在階段二，使用模糊Hopfield將節點模糊聚類為M類，同類節點可以在同一時隙被調度，不同類節點必須在不同時隙被調度．用該算法對3個測試拓撲圖進行調度，實驗結果表明該算法比其他算法能獲得更短的幀長度和更低的網絡延遲，證明了所提算法的可行性和有效性．
關鍵詞：無線傳感器網絡；廣播調度問題；Hopfield神經網絡；圖著色
1 引 言
在監測區域內，以隨機方式分布的集成有傳感器、數據處理單元和無線通信模塊的微小節點通過自組織方式便構成了無線傳感器網絡（WSN） [1] ．WSN 中節點經常需要廣播消息或數據，用于同步機制、拓撲控制或路由建立與維護等．由于無線鏈路的共享與開放性，很容易造成消息傳輸時的相互沖突，若節點的多個相鄰節點同時向該節點廣播消息，則必然產生相互干擾或沖突并造成廣播消息不能正確收發，大多數WSN網絡此時要求源節點重傳，而造成節點能量額外消耗，從因此需要對節點的消息廣播進行合理調度以延長網絡壽命[2] ．大多數WSN使用時分復用（TDMA）作為無線信道共享與接入方式[3] ,本文研究TDMA下WSN網絡廣播調度問題（broadcast scheduling problem,BSP），期望能實現在網絡拓撲穩定下，節點間消息無沖突傳輸，并最大化信道利用率．
2 廣播調度問題
記WSN網絡為無向簡單圖G＝（V,E）,頂點V＝｛vi｝代表網絡中傳感節點，邊E＝｛eij｝為節點問傳輸鏈路．若傳感節點i∈V，j∈V，且i,j在彼此的傳感半徑內，則稱i,j為一跳相鄰節點，即存在無線鏈路eij∈E；若i，j間不存在一跳相鄰節點，但存在中間節點k使得eik∈E且ekj∈E，則稱節點i，j為二跳相鄰節點．傳感節點問要能正確收發數據，必須滿足以下約束條件[3]:1）節點不能同時接收與發送數據，即若eij∈E，則節點i與節點j必須分配以不同時隙來傳輸數據，稱作第1類約束；2）節點不能同時接收兩個或多個相鄰節點發送的數據，即若ej∈且ekj∈E，則節點i,k必須在不同時隙發送數據以避免在節點j處發生沖突，稱作第2類約束．定義二進制矩陣S＝｛sij｝表示一個傳輸調度，ρ為WSN的帶寬利用率，用S′＝｛S1，S2，…｝表示無干擾可行調度集，則最優調度問題描述如下:
對于給定拓撲WSN網絡，尋找最優調度Sopt∈S′,在滿足第l類和第2類約束條件下，具有最短的幀長度Sopt和最大的信道帶寬利用率ρopt．
3 基于神經網絡的兩階段調度方法
3.1 階段
對給定拓撲的無向圖，階段一目標是使幀時隙長度降為最短，即用最少時隙數M完成調度．圖的頂點著色問題（VCP）求解是NP完全的，目前的求解方法主要是啟發式算法．雖然順序著色只能找到次優解,但其復雜度最小。計算量比其他最優和次優算法要低1～2個數量級．考慮到傳感節點的能量和計算能力有限，這里結合最大飽和度與最大度數準則設計新的頂點著色算法．
算法包含如下3個處理環節：1）確定幀時隙長度上下界．對于有N個結點WSN網絡，最優幀長度范圍為Lm≤M≤N，其中Lm＝maxdegi＋1,degi為節點i的度數；2）執行初始化時隙分配．令待初始化節點集合為G＝｛ni,i=1,2,…,Lm｝,G由圖中具有最大度數的節點n1及與n1相距l跳節點的相鄰節點ni構成，將時隙i分配給節點ni；3）改進的順序著色算法．
算法
輸入：原始WSN拓撲G＝（V,E）.
輸出：節點時隙調度矩陣S=｛Sij｝N×M.
Step1 網絡節點拓撲排序．對節點按照度數遞減規律排序并存儲為隊列Q=｛ni,i＝1,2,…，N｝，得到網絡節點的最大度數△G；
Step2 確定時隙下確界．置初始時隙數M＝△G十1，調度矩陣S＝｛0｝N×M；
Step3 節點時隙初始化調度．不失一般性，將第i個時隙分配到節點ni，得已調度節點集Gc＝｛ni,i＝1,2,…，M｝,令Sii=1,計數器P＝M＋1；
Step4 對未調度節點排序．按照最大飽和度準則對剩下的N-Lm個頂點排序，存儲為隊列
Q′＝｛nj,j=Lm+1,…,N｝；
Step5 調度Q′中節點nj．搜索滿足2跳內約束的時隙，記不同時隙數為Nc，依據Nc值分別執行以下處理：
①若Nc＞1,將第一個可用時隙指派給節點nj，Sij=1；
②若Nc＝1,將該唯一時隙指派給節點nj，Sij=1；
③若Nc＝0,則此時無空閑時隙指派給節點nj，轉Step7；
Step6 判斷是否所有節點已完成調度．若P＝N，算法停止；否則令P=P＋1，轉Step5；
Step7 新增一個時隙，重新調度．令M＝M＋1，轉Step5．
算法Step1排序的計算量為O（|N|）,Step4排序的計算量為O（|N-Lm|3）,N為網絡頂點數，Lm是頂點最大度數加1,整個算法的計算量約為O（|N|3）
3.2 階段二
在階段二，使用模糊Hopfield神經網絡對WSN網絡節點進行模糊聚類[4、5] ，分類數為階段一中求得的M，輸入樣本為待調度節點．同一類中的所有節點可以在同一個時隙同時被調度；不同類中的節點必須在不同時隙被調度．考慮N×M結構 Hopfield網絡，節點i是否在第j個時隙傳輸數據由Hopfield處在（i,j）位置神經元的輸出Pij確定．利用第2節中的約束條件來設計優化目標，即Hopfield網絡能量函數E．首先，所有的數據包應該在一個時隙內同步傳送；其次，當節點i時隙j傳輸數據時，其他所有節點i的相鄰節點不能分配在時隙j；最后，當節點i傳輸數據時，i的二跳相鄰節點也不能被分配到時隙j去傳輸數據．能量函數E大小反映網絡當前時隙調度與最優調度間差距，在考慮所有以上約束條件后，本文所設計能量函數E如下：
其中：ni表示第i個節點，dij為節點i，j間歐氏距離，權值w1和w2為正且滿足w1+w2＝l,權系數取值會影響網絡收斂性，需合理選?。甐i為第i類歐氏中心，即
．（i,j）位置神經元輸入為Iij＝（ni-vi）2＋△Iij，神經元輸出為Pij，外部激勵項△Iij取常數．Hopfield網絡優化流程如下：
Step1 初始化網絡內神經元（i,j）輸出Pij:
Step2 更新模糊隸屬度函數
，重新計算類中心vi；
Step3 由式（1）計算能量函數；
Step4 判斷網絡是否收斂于穩定狀態，若|E（n+1）-E（n）|〉ε（ε為閾值），轉Step2；否則，網絡收斂，算法終止．
4 實驗結果與分析
對TS-HNN算法的調度性能進行分析，與平均退火策略（MFA） [2] 、基于遺傳算法的Hopfield神經網絡（HNN-GA） [4]和含噪混沌神經網絡（NC-NN） [5]3種方法調度性能比較．使用3種不同拓撲的測試網絡Case 1～3[6] . 實驗中使用的數據包為固定長度，時隙長度設置為每包所需傳輸時間；節點問以泊松分布隨機收發數據包．每種拓撲結構運行50次，取平均值進行比較．表1給出本文算法（TS-HNN）與其他3種方法求解得到的網絡最小延遲η和幀長度M．在節點數較少（Case 1）或平均度數不高時（Case 3），4種算法都能找到最優幀長M＝8；對于節點數較多具有復雜結構網絡（Case 2），TS-HNN也能找到次優幀長；且TS-HNN在3種拓撲下都具有最低的網絡時延．測試拓撲Case 1調度結果如圖l所示，填充有黑色的方格代表所在節點（node）在該時隙（slot）可被調度．圖2詳細描述了網絡時延隨數據包（packets）服務速率變化的情況．隨著服務速率增加，網絡時延也在變長，在節點數較少時（Case 1），4種算法的時延相差不大，如圖 2（a）；當節點數增加時（Case 2）,4種算法下的網絡時延差異明顯增大，如圖2（b）．
5 結束語
調度是一類經典的帶約束資源優化分配問題本文以傳感器網絡為研究背景，提出了一種基于圖著色與神經網絡的兩階段廣播調度算法．算法的基本思想是將廣播調度問題求解轉化為兩階段目標尋優：第1階段借助頂點著色思想搜索給定拓撲WSN的具有最短時隙數目的幀結構；第2階段在上述幀結構下使用模糊Hopfield網絡為每個節點增添額外的無沖突傳輸時隙，從而使得在原有幀長度下盡可能多的讓更多節點實現并行無干擾傳輸，以最大化信道利用率，仿真實驗證明了所提方法的有效性．
參考文獻：
[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.