《電子技術應用》
您所在的位置:首頁 > 其他 > 設計應用 > 一種新的傳感器網絡混合廣播調度方法
一種新的傳感器網絡混合廣播調度方法
摘要: 由于傳感器網絡所使用無線信道的共享性和相互干擾,節點間數據廣播會產生資源沖突,廣播調度要解決的即是為每個節點分配到一個無沖突傳輸時隙,其目標是找到晟優時分復用(TDMA:Time division multiple access)調度解,使得幀長度最短而信道利用率最大.提出基于神經網絡的兩階段混合廣播調度算法.在階段一,使用改進的頂點著色算法來獲得調度所需最短時隙數目;在階段二,使用模糊Hopfield將節點模糊聚類為M類,同類節點可以在同一時隙被調度,不同類節點必須在不同時隙被調度.用該算法對3個測試拓撲圖進行調度,實驗結果表明該算法比其他算法能獲得更短的幀長度和更低的網絡延遲,證明了所提算法的可行性和有效性.
Abstract:
Key words :

摘  要:由于傳感器網絡所使用無線信道的共享性和相互干擾,節點間數據廣播會產生資源沖突,廣播調度要解決的即是為每個節點分配到一個無沖突傳輸時隙,其目標是找到晟優時分復用(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={SijN×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,權系數取值會影響網絡收斂性,需合理選取.Vi為第i類歐氏中心,即.(i,j)位置神經元輸入為Iij=(ni-vi2+△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.

此內容為AET網站原創,未經授權禁止轉載。
热re99久久精品国产66热_欧美小视频在线观看_日韩成人激情影院_庆余年2免费日韩剧观看大牛_91久久久久久国产精品_国产原创欧美精品_美女999久久久精品视频_欧美大成色www永久网站婷_国产色婷婷国产综合在线理论片a_国产精品电影在线观看_日韩精品视频在线观看网址_97在线观看免费_性欧美亚洲xxxx乳在线观看_久久精品美女视频网站_777国产偷窥盗摄精品视频_在线日韩第一页
  • <strike id="ygamy"></strike>
  • 
    
      • <del id="ygamy"></del>
        <tfoot id="ygamy"></tfoot>
          <strike id="ygamy"></strike>
          欧美中日韩免费视频| 欧美自拍偷拍| 一区二区欧美精品| 久久免费99精品久久久久久| 精品51国产黑色丝袜高跟鞋| 免费日韩av| 久久久999成人| 噜噜噜躁狠狠躁狠狠精品视频| 免播放器亚洲| 久久久久久久999| 欧美福利视频一区| 久久国产精彩视频| 这里只有视频精品| 欧美日韩亚洲一区二区三区在线观看| 亚洲福利电影| 亚洲第一色在线| 欧美国产日本| 久久精品国产视频| 午夜伦欧美伦电影理论片| 国产精品久久97| 久久精品国产亚洲一区二区| 国产日韩欧美高清| 亚洲第一精品夜夜躁人人躁| 在线免费日韩片| 国内伊人久久久久久网站视频| 欧美日韩性生活视频| 国产日韩欧美一区在线| aa国产精品| 影音先锋中文字幕一区二区| 国产日产亚洲精品| 亚洲欧洲偷拍精品| 国产亚洲精品福利| 久久精品人人爽| 免费看的黄色欧美网站| 国产精品啊啊啊| 欧美日本在线观看| 亚洲欧美日韩视频二区| 欧美日韩国产色站一区二区三区| 欧美一区三区三区高中清蜜桃| 性做久久久久久久免费看| 99精品视频免费在线观看| 亚洲伊人网站| 1000部国产精品成人观看| 欧美色道久久88综合亚洲精品| 亚洲国产欧美日韩精品| 欧美午夜精品伦理| 国产精品护士白丝一区av| 久久久久久久久久码影片| 久久亚洲私人国产精品va| 日韩系列欧美系列| 欧美精品性视频| 亚洲黑丝在线| 欧美丝袜一区二区| 亚洲欧美一区二区三区在线| 亚洲午夜电影| 亚洲女同性videos| 欧美成人激情视频免费观看| 久久精品麻豆| 一区二区三区四区蜜桃| 一区二区福利| 久久免费观看视频| 一区二区三区在线免费观看| 一区精品在线播放| 中文国产一区| 亚洲精品久久久久| 国内精品久久久久久久影视蜜臀| 狠狠色综合色综合网络| 欧美视频不卡| 欧美视频日韩视频在线观看| 久久精精品视频| 欧美成人一区在线| 欧美国产一区二区三区激情无套| 小辣椒精品导航| 欧美一级视频免费在线观看| 欧美影院成年免费版| 国产女精品视频网站免费| 欧美v国产在线一区二区三区| 国产精品欧美一区二区三区奶水| 一区二区三区高清在线观看| 亚洲一区二区三区激情| 一本色道久久99精品综合| 国产精品美女久久久久久免费| 欧美午夜精品久久久久免费视| 在线不卡亚洲| 久久中文字幕一区| 亚洲无亚洲人成网站77777| 精品999在线播放| 久久久久久久久久久久久久一区| 午夜精品视频在线观看| 亚洲夜晚福利在线观看| 一区二区三区四区五区精品| 国产在线乱码一区二区三区| 亚洲青涩在线| 欧美激情亚洲激情| 国产精品igao视频网网址不卡日韩| 国产精品视频久久| 国产精品高清一区二区三区| 亚洲一区3d动漫同人无遮挡| 欧美在线观看你懂的| 中文精品视频一区二区在线观看| 激情视频一区二区三区| 欧美大片18| 欧美视频不卡| 亚洲午夜精品一区二区三区他趣| 亚洲欧美日韩另类| 午夜日本精品| 欧美国产精品中文字幕| 麻豆精品国产91久久久久久| 欧美国内亚洲| 国产精品一区二区女厕厕| 久久综合久久久| 久久久久女教师免费一区| 国产一区91| 欧美一区二区三区的| 欧美精品免费观看二区| 亚洲国产精彩中文乱码av在线播放| 亚洲免费观看在线观看| 欧美日韩亚洲激情| 亚洲线精品一区二区三区八戒| 国产一区二区三区精品欧美日韩一区二区三区| 欧美电影资源| 亚洲欧洲偷拍精品| 国产精品久久久久影院色老大| 欧美日韩美女在线观看| 国产一区二区三区高清| 亚洲日本中文| 在线日韩中文字幕| 久久成人精品一区二区三区| 国内精品久久久久影院优| 欧美久久久久久蜜桃| 欧美精品在线一区二区| 一区二区三区.www| 欧美精品久久久久久久免费观看| 欧美片第1页综合| 午夜精彩国产免费不卡不顿大片| 国产精品久久久久久妇女6080| 亚洲欧美日韩国产中文| 亚洲免费影视第一页| 国产乱码精品一区二区三| 欧美人体xx| 欧美日韩综合在线| 欧美日本一区二区高清播放视频| 国产女主播视频一区二区| 亚洲视频欧洲视频| 国产精品久久久99| 老司机精品久久| 欧美午夜理伦三级在线观看| 欧美日韩八区| 亚洲欧美国产va在线影院| 欧美日韩亚洲综合一区| 亚洲福利精品| 亚洲少妇一区| 在线观看视频欧美| 欧美天堂亚洲电影院在线观看| 亚洲欧美日本在线| 国产日产高清欧美一区二区三区| 在线不卡免费欧美| 午夜欧美大片免费观看| 国产美女一区二区| 亚洲午夜电影网| 一区在线免费观看| 国产欧美日韩91| 精品999久久久| 国产视频在线观看一区二区三区| 欧美人交a欧美精品| 欧美另类专区| 欧美成人精精品一区二区频| 欧美精品成人91久久久久久久| 欧美丝袜第一区| 欧美精品福利| 国产精品久久久久久久久久尿| 欧美视频亚洲视频| 久久精品电影| 久久精品天堂| 久久综合久色欧美综合狠狠| 亚洲久久视频| 欧美一区二区精品| 国产精品久久久一区二区三区| 日韩视频久久| 日韩午夜av电影| 黑人一区二区三区四区五区| 国产精品揄拍500视频| 国产精品欧美激情| 亚洲欧美综合一区| 亚洲影院一区| 国产日韩精品在线观看| 亚洲午夜国产成人av电影男同| 欧美午夜片在线免费观看| 在线视频你懂得一区二区三区| 亚洲欧洲午夜| 国产欧美日韩亚洲一区二区三区| 99精品国产99久久久久久福利| 欧美成人免费全部观看天天性色| 国产精品美女一区二区| 亚洲成人原创| 一区二区三区国产精品| 亚洲精品乱码久久久久久黑人| 欧美人成网站| 午夜精品久久久久久| 韩国av一区二区三区| 欧美午夜电影网| 国产伦精品一区| 欧美高清视频在线| 欧美视频免费看| 亚洲人成免费| 亚洲自拍电影| 亚洲专区一区| 午夜一区二区三区在线观看| 欧美日韩视频在线观看一区二区三区| 日韩一级黄色大片| 亚洲婷婷综合色高清在线| 另类综合日韩欧美亚洲| 国产欧美日韩综合精品二区| 伊人成人在线| 欧美有码在线视频| 另类综合日韩欧美亚洲| 亚洲福利视频一区二区| 可以看av的网站久久看| 亚洲国产人成综合网站| 国产视频丨精品|在线观看| 亚洲欧美国产日韩中文字幕| 在线免费观看成人网| 99国内精品| 国产精品无码永久免费888| 亚洲欧美国产77777| 日韩视频在线观看一区二区| 欧美激情网友自拍| 欧美ab在线视频| 欧美国产日韩一区二区三区| 亚洲第一网站免费视频| 欧美在线一区二区| 亚洲视频精选在线| 欧美精品国产一区| 久久av老司机精品网站导航| 亚洲激情av| 欧美经典一区二区三区| 国产精品免费看久久久香蕉| 经典三级久久| 国产精品二区在线| 久久久天天操| 国产欧美综合一区二区三区| 欧美一级理论性理论a| 亚洲午夜精品久久| 精品999在线播放| 一区二区在线免费观看| 国产精品久久久久久久7电影| 毛片精品免费在线观看| 国产精品你懂的在线| 亚洲视频一区| 国产精品国产馆在线真实露脸| 久久视频国产精品免费视频在线| 99视频在线观看一区三区| 在线日韩成人| 久久久999精品| 9l视频自拍蝌蚪9l视频成人| 影音先锋亚洲一区| 老司机午夜精品视频| 亚洲精品视频啊美女在线直播| 亚洲成色精品| 最近中文字幕日韩精品| 亚洲人成免费| 亚洲中字黄色| 久久综合久久综合这里只有精品| 欧美午夜电影在线| 在线看国产日韩| 亚洲免费高清视频| 91久久精品国产91性色| 欧美日韩一区自拍| 一本色道久久综合狠狠躁篇的优点| 午夜亚洲激情| 一本色道88久久加勒比精品| 亚洲国产精品久久久久秋霞蜜臀| 国产精品高潮呻吟视频| 日韩视频免费观看高清完整版| 国产主播喷水一区二区| 久久综合精品国产一区二区三区| 国产区二精品视| 狠狠干狠狠久久| 欧美日韩精品久久久| 国产一区二区三区直播精品电影| 久久久久国产精品人| 亚洲美女黄色| 国产精品久久久久久久7电影| 亚洲毛片在线观看.| 久久激情网站| 麻豆国产精品777777在线| 免费中文字幕日韩欧美| 欧美精品久久99久久在免费线| 亚洲欧美偷拍卡通变态| 亚洲视频自拍偷拍| 在线一区二区三区四区| 亚洲欧美国产毛片在线| 国产视频观看一区| 欧美va天堂| 亚洲理论在线观看| 精品粉嫩aⅴ一区二区三区四区| 久久www免费人成看片高清| 激情六月婷婷综合| 亚洲视频1区2区| 国产一区二区三区日韩欧美| 亚洲自啪免费| 亚洲一二三四区| 亚洲自拍16p| 99这里只有久久精品视频| 欧美激情在线有限公司| 精品动漫3d一区二区三区| 久久人人看视频| 欧美一区二区三区啪啪| 欧美精品99| 久久手机精品视频| 一区二区三区高清在线| 在线精品一区| 久久青草久久| 免费成人黄色片| 欧美激情视频在线免费观看 欧美视频免费一| 国产精品豆花视频| 欧美自拍丝袜亚洲| 翔田千里一区二区| 国产视频一区二区在线观看| 亚洲免费黄色| 欧美影院精品一区| 欧美大胆a视频| 国产欧美亚洲日本| 国产精品久久久久77777| 欧美日韩国产一级| 在线性视频日韩欧美| 国产综合色一区二区三区| 国产一区二区三区四区|