基于遲滯噪聲混沌神經(jīng)網(wǎng)絡的TDMA廣播調(diào)度

孫 明，趙 琳，曹 偉，劉正亮

(1.齊齊哈爾大學計算機與控制工程學院，黑龍江齊齊哈爾161006;2.哈爾濱工程大學自動化學院，哈爾濱150001)

分組無線網(wǎng)采用共享的廣播式無線信道和分組存儲轉發(fā)技術進行數(shù)據(jù)傳輸［1－3］，能夠利用多跳路由技術實現(xiàn)遠距離節(jié)點間的相互通信，并采用時分多址接入技術(Time Division Multiple Access， TDMA)來避免節(jié)點之間的通信沖突.分組無線網(wǎng)的廣播調(diào)度問題(Broadcast Scheduling Problem，BSP)就是在通信不發(fā)生沖突的前提下，為拓撲固定的分組無線網(wǎng)絡找到一個時隙長度最小、信道利用率最大的TDMA幀［1－2］.該問題已被證明是NP－h(huán)ard組合優(yōu)化問題［4］.

神經(jīng)網(wǎng)絡是求解BSP問題的一類可行方法.Funabiki等［5］首次采用了Hopfield神經(jīng)網(wǎng)絡求解BSP問題;Salcedo－Sanz等人［6］也利用基于Hopfield神經(jīng)網(wǎng)絡的混合方法作了不同的嘗試.由于Hopfield網(wǎng)絡采用了梯度下降策略，以致于這些基于Hopfield神經(jīng)網(wǎng)絡的方法極易收斂到BSP問題的局部極小解甚至無效解.將模擬退火引入到Hopfield神經(jīng)網(wǎng)絡中，可有效地提高網(wǎng)絡的尋優(yōu)能力.如Chen等人［7］在Hopfield神經(jīng)網(wǎng)絡中引入暫態(tài)混沌動力學，提出了具有混沌模擬退火的暫態(tài)混沌神經(jīng)網(wǎng)絡(TCNN);Wang等［8］又在TCNN的基礎上加入了噪聲幅值指數(shù)遞減的噪聲項，提出了能夠表現(xiàn)出隨機混沌模擬退火的噪聲混沌神經(jīng)網(wǎng)絡(NCNN).由于NCNN的隨機混沌模擬退火結合了混沌的高效遍歷性和噪聲的隨機游動性，因此NCNN進一步提高了TCNN的全局尋優(yōu)能力.但是NCNN中的Sigmoid激勵函數(shù)很容易使神經(jīng)元過早地進入飽和狀態(tài)［9］，不利于克服局部極小，減弱了NCNN的優(yōu)化能力.利用遲滯動力學使神經(jīng)元不連續(xù)跳轉的特性，可有效地防止神經(jīng)元過早地進入飽和狀態(tài)，克服Sigmoid激勵函數(shù)的缺點.但目前所報道的遲滯激勵函數(shù)均有不足之處.例如，文獻［9，10］通過兩個相互偏離的Sigmoid函數(shù)構成了遲滯激勵函數(shù)，該類型的遲滯激勵函數(shù)是通過引入額外的Sigmoid中心參數(shù)實現(xiàn)的，增加了原系統(tǒng)可調(diào)參數(shù)的數(shù)量;文獻［2］通過等價轉換將NCNN的噪聲項轉化成Sigmoid函數(shù)的中心參數(shù)，并通過對噪聲項的控制提出了一種新的遲滯激勵函數(shù)，該方法盡管在不增加參數(shù)的情況下提高了NCNN的優(yōu)化性能，但因噪聲項時強時弱甚至為零，故這一方法不能保證遲滯動力學在優(yōu)化過程中始終發(fā)揮作用.

為了保證遲滯動力學在NCNN優(yōu)化過程中始終發(fā)揮作用，且不引入額外的系統(tǒng)參數(shù)，本文將NCNN的噪聲幅值作為Sigmoid函數(shù)的中心參數(shù)，并通過神經(jīng)元的輸入變化來控制噪聲幅值形成遲滯環(huán)，提出了一種新型的遲滯噪聲混沌神經(jīng)網(wǎng)絡.網(wǎng)絡對BSP問題的求解結果驗證了本文方法的合理性.

1 廣播調(diào)度問題BSP

記分組無線網(wǎng)為無向簡單圖G=(V，E)，其中V={1，2…，N)表示節(jié)點集合，E表示節(jié)點之間的無線鏈路集合.如果節(jié)點i和j之間存在無線鏈路(i，j)∈E，則節(jié)點i和j為一跳節(jié)點;如果節(jié)點i和j不為一跳節(jié)點即(i，j)?E，但存在節(jié)點k，使得(i，k)∈E和(k，j)∈E，則節(jié)點i和j為兩跳節(jié)點.在分組無線網(wǎng)中，任何一跳節(jié)點或兩跳節(jié)點的同時廣播均會導致通信沖突.

假設網(wǎng)絡的N個節(jié)點可在M個時隙的TDMA幀T={tij}(i=1，…，N;j=1，…，M)

中進行無沖突通信，則該TDMA幀的信道利用率ρ可表示為:

分組無線網(wǎng)的廣播調(diào)度問題(BSP)就是為拓撲固定的分組無線網(wǎng)絡找到一個時隙長度M最小和信道利用率ρ最大的TDMA幀，滿足以下的兩個約束條件:

其中:

約束條件式(3)表示每個節(jié)點在TDMA幀的M個時隙中至少廣播一次，約束條件式(4)表示一跳或兩跳節(jié)點不能在TDMA幀的同一時隙中進行廣播.

2 噪聲混沌神經(jīng)網(wǎng)絡(NCNN)

Wang等在暫態(tài)混沌神經(jīng)網(wǎng)絡(TCNN)中加入了噪聲幅值指數(shù)遞減的噪聲項n(t)，提出的噪聲混沌神經(jīng)網(wǎng)絡(NCNN)如下所示:

其中:xij(t)和yij(t)分別是第ij個神經(jīng)元在時刻t的輸出和輸入;wij，kl是第ij個神經(jīng)元和第kl個神經(jīng)元的連接權值;z(t)是神經(jīng)網(wǎng)絡的自反饋連接權值;Iij是ij第個神經(jīng)元的偏置;I0為一正常數(shù);k是神經(jīng)膜阻尼系數(shù);ε是Sigmoid激勵函數(shù)的陡度系數(shù);α是神經(jīng)元之間的耦合因子;n(t)為t時刻添加到神經(jīng)元的、噪聲幅值為A［n(t)］的隨機噪聲項，該噪聲項服從［－A［n(t)］，A［n(t)］］的均勻分布;β1和β2分別為z(t)和A［n(t)］模擬退火參數(shù).

自反饋連接權值z(t)按式(8)指數(shù)遞減，又稱為混沌模擬退火，可使網(wǎng)絡首先進入混沌遍歷“粗搜索”階段，然后通過倍周期倒分岔進入梯度下降“細搜索”階段.混沌模擬退火的優(yōu)點是能夠將網(wǎng)絡的狀態(tài)搜索控制在一個包含全局最優(yōu)解或局部次優(yōu)解的分形區(qū)域內(nèi)，由于該分形區(qū)域只占整個狀態(tài)空間的一小部分，因此混沌模擬退火具有較高的優(yōu)化效率.但是，混沌模擬退火具有完全確定的動力學特性，在某些初始條件下不能保證找到全局最優(yōu).而式(9)所示的噪聲幅值A［n(t)］的模擬退火，則可使網(wǎng)絡的狀態(tài)搜索表現(xiàn)出隨機游動性，其優(yōu)點是能夠克服混沌模擬退火確定性動力學的缺陷，而且噪聲項的隨機游動性在混沌動態(tài)消失前后均可發(fā)揮作用.故通過結合混沌的高效遍歷性和噪聲的隨機游動性，NCNN的全局尋優(yōu)能力好于TCNN.NCNN中這種z(t)和A［n(t)］相結合的模擬退火方式又稱為隨機混沌模擬退火.

盡管NCNN從模擬退火的角度提高了網(wǎng)絡的優(yōu)化性能，但其采用的激勵函數(shù)式(6)很容易使神經(jīng)元過早地進入飽和狀態(tài)，不利于克服局部極小，從而減弱了網(wǎng)絡的優(yōu)化性能.遲滯激勵函數(shù)可使神經(jīng)元不連續(xù)地跳轉，能夠防止神經(jīng)元過早地進入飽和狀態(tài).然而，目前所報道的遲滯激勵函數(shù)均有不足之處，或增加了系統(tǒng)的參數(shù)，或不能保證遲滯動力學一直發(fā)揮作用.本文針對遲滯激勵函數(shù)的這一現(xiàn)狀，提出了一種具有新遲滯激勵函數(shù)的遲滯噪聲混沌神經(jīng)網(wǎng)絡模型.

3 遲滯噪聲混沌神經(jīng)網(wǎng)絡

本文提出了一種不同于文獻［2］的新型遲滯噪聲混沌神經(jīng)網(wǎng)絡(Novel Hysteretic Noisy Chaotic Neural Network，NHNCNN)，如下所示:

其中:Δyij=yij(t)－yij(t－1)，表示神經(jīng)元輸入的變化.與NCNN比較可知，NHNCNN并未增加額外的網(wǎng)絡參數(shù).NHNCNN的遲滯激勵函數(shù)如式(10)所示，該遲滯激勵函數(shù)將噪聲幅值A［n(t)］作為Sigmoid函數(shù)的中心參數(shù)，并通過神經(jīng)元輸入的變化Δyij來控制噪聲幅值以形成遲滯環(huán)，如圖1所示.此遲滯激勵函數(shù)的運行機制可描述為:當Δyij＞0時，神經(jīng)元采用圖1左邊的Sigmoid函數(shù);而當Δyij≤0時，神經(jīng)元采用圖1右邊的Sigmoid函數(shù).通過這種機制，遲滯激勵函數(shù)可使神經(jīng)元不連續(xù)地跳轉，從而避免了神經(jīng)元過早地演化到飽和狀態(tài)，達到了克服局部極小的目的.

小學階段的學生對新事物充滿好奇，對生活的一切都有著較大的探索興致。因此，教師在開展思想品德教育時，要為學生創(chuàng)造既豐富又熟悉的教學情境，將課堂教學內(nèi)容和學生的衣食住行聯(lián)系起來，真正引導其意識到思想品德課程的重要性。例如，教師在講解《互幫互助一家親》的章節(jié)內(nèi)容時，可以先請學生回憶自己和家人一起合作完成的某件事，然后再將學生分成若干人一組，通過游戲比賽的形式讓學生體會團結協(xié)作的重要性，在促進學生與學生之間感情的同時提升教學效率和質(zhì)量。

圖1 遲滯激勵函數(shù)與Sigmoid激勵函數(shù)

隨機噪聲項n(t)服從［－A［n(t)］，A［n(t)］］的均勻分布，故該噪聲項時強時弱甚至為零.對于隨機噪聲項n(t)，有|A［n(t)］|≥|n(t)|成立.因此，與文獻［2］中用n(t)作為Sigmoid函數(shù)中心參數(shù)的遲滯激勵函數(shù)相比，本文所提出的用噪聲幅值A［n(t)］作為Sigmoid函數(shù)中心參數(shù)的遲滯激勵函數(shù)式(10)能夠始終發(fā)揮出遲滯動態(tài)的優(yōu)化作用.網(wǎng)絡在遲滯激勵函數(shù)式(10)的作用下可同時表現(xiàn)出混沌、遲滯和隨機游動等豐富的動態(tài)特性，即使在退出混沌遍歷搜索后，網(wǎng)絡仍可在遲滯動態(tài)和隨機游動的作用下避免梯度下降到局部極小.

網(wǎng)絡的優(yōu)化性能與噪聲幅值A［n(0)］的大小有關.當噪聲幅值A［n(0)］太小時，遲滯激勵函數(shù)中Sigmoid函數(shù)的偏離程度太小，神經(jīng)元的不連續(xù)跳轉很弱，從而不能有效地防止神經(jīng)元過早地進入飽和狀態(tài);同時，太小的噪聲幅值A［n(0)］也將減弱噪聲項n(t)的隨機游動，從而不能有效地克服混沌模擬退火確定性動力學的缺陷.但隨著噪聲幅值A［n(0)］的逐漸增大，神經(jīng)元的不連續(xù)跳轉將逐漸增強，噪聲項n(t)的隨機游動對混沌模擬退火的影響也將越來越大，從而NHNCNN相對于NCNN在優(yōu)化上的優(yōu)勢也將越來越明顯.而當噪聲幅值A［n(0)］太大時，噪聲項n(t)的隨機游動過于強大，以致能降低混沌遍歷搜索的效率，破環(huán)混沌的倒分岔，影響神經(jīng)元的收斂速度，從而導致NHNCNN不能在有效的時間內(nèi)找到理想的優(yōu)化解.

以下通過神經(jīng)元的狀態(tài)演化仿真來分析噪聲幅值A［n(0)］對神經(jīng)元的影響.當神經(jīng)元的耦合因子α=0時，模型(10)～(13)就變?yōu)镹HNCNN神經(jīng)元模型.同文獻［1－2］，取NHNCNN神經(jīng)元的參數(shù)k=0.9，z(0)=0.08，I0=0.65;模擬退火參數(shù)β1=0.003，β2=0.008.當噪聲幅值A［n(0)］分別固定在0.0001、0.003和0.01時，神經(jīng)元的狀態(tài)演化如圖2～4所示.不難看出，當噪聲幅值A［n (0)］取很小值如0.000 1時，神經(jīng)元的狀態(tài)演化沒有表現(xiàn)出明顯的遲滯動態(tài)特性和隨機游動性，而只表現(xiàn)出混沌倒分岔行為，此時NHNCNN神經(jīng)元的演化行為與TCNN神經(jīng)元相近，能夠通過4 000次迭代收斂;當噪聲幅值A［n(0)］增大到0.003時，神經(jīng)元的遲滯動態(tài)特性和隨機游動性則比較明顯，神經(jīng)元的混沌也具有一定的倒分岔行為，此時神經(jīng)元既具有豐富的動態(tài)特性又具有較高的優(yōu)化效率;當噪聲幅值A［n(0)］增大到0.01時，遲滯動態(tài)和隨機游動對混沌的破壞程度非常嚴重，嚴重影響了神經(jīng)元的優(yōu)化效率，此時神經(jīng)元需要迭代6 500多次才能收斂.由以上分析可知，A［n(0)］=0.003時的神經(jīng)元明顯優(yōu)于其他兩種情況的神經(jīng)元.

圖2 A［n(0)］=0.0001時NHNCNN神經(jīng)元的狀態(tài)演化圖

4 基于NHNCNN的兩階段BSP優(yōu)化方法

基于NHNCNN求解BSP的第1階段是利用NHNCNN獲得廣播調(diào)度所需的具有最小時隙長度的TDMA幀，并保證所有的節(jié)點在該TDMA幀中進行1次廣播;第2階段則是在第1階段TDMA幀的基礎上，利用NHNCNN增加節(jié)點的廣播次數(shù)，最大化信道利用率.

4.1 第1階段優(yōu)化方法

求解BSP的第1階段優(yōu)化方法可描述為:

Step 1初始化TDMA幀的最小時隙長度M.令

式(15)中E1是能量函數(shù)［5］，

式(16)中W1和W2是能量函數(shù)的系數(shù);式(16)的第1項表示每個節(jié)點需在TDMA幀中進行1次廣播，第2項表示一跳或兩跳節(jié)點不能在TDMA幀的同一個時隙進行廣播.將式(16)代入到式(15)中可得:

Step 3網(wǎng)絡在每次迭代后，均將其輸出xij(i= 1，…，N;j=1，…，M用式(18)轉化為對應的TDMA幀

若在規(guī)定的迭代次數(shù)內(nèi)，轉化成的TDMA幀滿足約束條件(3)和(4)，則停止計算，此時得到的TDMA幀即是時隙長度最小的TDMA幀;否則，令M =M+1，并轉到Step 2繼續(xù)計算.

4.2 第2階段優(yōu)化方法

求解BSP的第2階段優(yōu)化方法可描述為:

Step 1 利用第1階段獲得的TDMA幀，初始化NHNCNN在第2階段的神經(jīng)元輸出:若t(1)ij(i= 1，…，N;j=1，…，M)=1，則將第2階段神經(jīng)元的輸出xij固定為1，并且不予計算更新;

Step 2 對于xij≠1的神經(jīng)元，將式(20)代入到NHNCNN中計算更新，

式(19)中E2是NHNCNN在第2階段中使用的能量函數(shù)［5］:

式(20)中W3和W4是能量函數(shù)的系數(shù);式(20)中的第一項表示一跳或兩跳節(jié)點不能在TDMA幀的同一個時隙進行廣播，第二項表示最大化TDMA幀的信道利用率.將式(20)代入到式(19)中可得:

Step 3 采用與第1階段相同的方法將網(wǎng)絡第2階段的輸出轉化成TDMA幀…，M)，若其滿足約束條件(3)和(4)，則TDMA幀就是BSP的最終調(diào)度結果;否則，令=1，…，N;j=1，…，M).

5 仿真結果與分析

為了驗證遲滯噪聲混沌神經(jīng)網(wǎng)絡(HNCNN)在求解分組無線網(wǎng)絡廣播調(diào)度(BSP)上的優(yōu)越性，分別將本文提出的NHNCNN算法、NCNN［1］以及文獻［2］中的方法用于求解30節(jié)點70邊［3］、40節(jié)點66邊［3］以及78節(jié)點108邊［2］的BSP問題.為了方便與NCNN［1］以及文獻［2］中的方法進行比較，本文依據(jù)NCNN［1］以及文獻［2］中方法的網(wǎng)絡參數(shù)設置，將NHNCNN的參數(shù)設置為k=0.9，ε= 0.004，α=0.015，z(0)=0.08，I0=0.65，β1= 0.001，β2=0.000 1，并分別利用NHNCNN、NCNN以及文獻［2］中的方法在A［n(0)］等于0.003、0.006、0.008和0.010時對每個BSP問題進行了50次仿真比較.仿真比較結果如表1～3所示，表中以獲得的同時具有最小時隙長度和最大信道利用率的最好解(用Mmin/ρmax表示)及數(shù)量(用個數(shù)表示)為性能指標，來評價NHNCNN、NCNN以及文獻［2］中方法的優(yōu)化性能.已知30節(jié)點70邊BSP的最優(yōu)解是Mmin=10、ρmax=0.123 3，40節(jié)點66邊BSP的最優(yōu)解是Mmin=8、ρmax=0.212 5，70節(jié)點108邊BSP的最優(yōu)解是Mmin=6、ρmax=0.268 5.

表1 各種算法在不同的值時對30節(jié)點70邊BSP的仿真結果比較

表2 各種算法在不同的值時對40節(jié)點66邊BSP的仿真結果比較

表3 各種算法在不同的A［n(0)］值時對70節(jié)點108邊BSP的仿真結果比較

從表1～3中的仿真結果可以看出，在不同的A［n(0)］值時，本文提出的NHNCNN在3個BSP問題上的優(yōu)化性能均優(yōu)于NCNN和文獻［2］中的方法.例如，在表1和表3中，當A［n(0)］等于0.006時，NHNCNN能獲得30節(jié)點70邊和78節(jié)點108邊BSP問題的最優(yōu)解，而NCNN和文獻［2］中的方法卻只能得到次優(yōu)解.而且，NHNCNN獲得的最優(yōu)解或最好解的數(shù)量均多于NCNN和文獻［2］中的方法.即，相比于NHNCNN而言，NCNN和文獻［2］中的方法或者不能獲得最優(yōu)解，或者獲得最優(yōu)解或最好解的個數(shù)少于NHNCNN.另外，隨著BSP問題規(guī)模的增加，NHNCNN相對于NCNN和文獻［2］中方法的優(yōu)勢越來越明顯，與表1的30節(jié)點70邊BSP和表2的40節(jié)點66邊BSP的仿真結果比較而言，NHNCNN在表3的78節(jié)點108邊BSP上相對于NCNN和文獻［2］中方法的優(yōu)勢更加突出.

6 結語

通過分析模擬退火和遲滯激勵函數(shù)在混沌神經(jīng)網(wǎng)絡中的優(yōu)化作用，本文提出了一種能夠始終發(fā)揮出遲滯動態(tài)優(yōu)化作用的遲滯噪聲混沌神經(jīng)網(wǎng)絡，并將該網(wǎng)絡應用于優(yōu)化分組無線網(wǎng)絡的廣播調(diào)度問題.對該遲滯噪聲混沌神經(jīng)網(wǎng)絡的神經(jīng)元狀態(tài)演化行為的研究表明，該網(wǎng)絡在適當?shù)脑肼暦底饔孟履軌蛲瑫r演化出混沌倒分岔、隨機游動和遲滯等動力學行為.對30節(jié)點70邊、40節(jié)點66邊和78節(jié)點108邊等3個廣播調(diào)度問題的仿真結果表明，該網(wǎng)絡比現(xiàn)有的混沌神經(jīng)網(wǎng)絡能夠更加有效地找到廣播調(diào)度優(yōu)化問題的最優(yōu)解或最好解.

［1］ WANG L，SHI H.A gradual noisy chaotic neural network for solving the broadcast scheduling problem in packet radio networks［J］.IEEE Trans.Neural Networks，2006，17(4):989－1000.

［2］ SUN M，ZHAO L，CAO W，et al.Novel hysteretic noisy chaotic neural network for broadcast scheduling problems in packet radio networks［J］.IEEE Trans.Neural Networks，2010，21(9): 1422－1433.

［3］ WANG G，ANSARI N.Optimal broadcast scheduling in packet radio networks using mean field annealing［J］.IEEE J.Sel.Areas Communications，1997，15(2):250－260.

［4］ EPHREMDIES A，TRUONGT V.Scheduling broadcast in multihop radio networks［J］.IEEE Trans.Communications，1990，38(6):456－460.

［5］ FUNABIKI N，KITAMICHI J.A gradual neural network algorithm for broadcast scheduling problems in packet radio networks.IEICE Trans.Fund.，vol.E82－A，no.5:815－824，1999.

［6］ SALCEDO－SANZ S，BOUSONO－CALZON C，F(xiàn)IGUEIRAVIDAL A R.A mixed neural－genetic algorithm for the broadcast scheduling problem［J］.IEEE Trans.Wireless Commun.，2003，2(2):277－283.

［7］ CHEN L，AIHARA K.Chaotic simulated annealing by a neural network model with transient chaos［J］.Neural Networks，1995，8(6):915－930.

［8］ WANG L，LI S，TIAN F，et al.A noisy chaotic neural network for solving combinatorial optimization problems:Stochastic chaotic simulated annealing［J］.IEEE Trans.Syst.Man Cybern.B，Cybern.，2004，34(5):2119－2125.

［9］ BHARITKAR S，MENDEL J M.The hysteretic hopfield neural network［J］.IEEE Trans.Neural Networks，2000，11(4):879－888.

［10］ LIU X，XIU C.A novel hysteretic chaotic neural network and its applications［J］.Neurocomputing，2007，70(13－15): 2561－2565.