基于Multi-Radio Multi-Channel傳感器網(wǎng)絡(luò)無沖突信道分配算法的研究

蔡鳳麗，劉新永

(1.安徽電子信息職業(yè)技術(shù)學(xué)院電子信息系，安徽蚌埠230000;2.解放軍裝甲兵學(xué)院信息管理中心，北京100000)

一、MM傳感器網(wǎng)絡(luò)中路由選擇標(biāo)準(zhǔn)

此次研究中選擇的MM傳感器網(wǎng)絡(luò)應(yīng)滿足以下條件:網(wǎng)絡(luò)中具有一個Sink節(jié)點(diǎn)以及兩個及其以上的Sensor節(jié)點(diǎn);任何一個Sensor節(jié)點(diǎn)不得超過M個Radio;任何一個Radio中都有N個正交信道;任何一個Radio都能夠使用K級的發(fā)射功率開展具體的通信，且要滿足P1為最小的條件。將Dis(Pi)定義為節(jié)點(diǎn)位于功率Pi時的通信半徑，E(Pi)代表的是節(jié)點(diǎn)在功率為Pi處發(fā)送的一個數(shù)據(jù)包所需要耗費(fèi)的能量。

(一)最佳選擇功率

定義在節(jié)點(diǎn)S處可以在某級功率下實(shí)現(xiàn)和節(jié)點(diǎn)D直接進(jìn)行通信，功率Pi可以看做是節(jié)點(diǎn)S的最佳選擇功率。定義Pi滿足以下條件:Dis(Pi-1)＜Dis(S，D)≤Dis(Pi)，則登記為 OCP(S，D)=Pi，公式中Dis(P0)=0，Dis(S，D)代表的是節(jié)點(diǎn)S與節(jié)點(diǎn)D兩者之間的物理距離。

(二)相互干擾

在既定的兩個鏈路li=(Si，Di)以及 lj=(Sj，Dj)，其中Si、Sj分別代表的是源節(jié)點(diǎn)，Di、Dj指的是目的節(jié)點(diǎn)，li在傳感網(wǎng)中的通信功率用Pi(1≤i≤K)表示，lj在傳感網(wǎng)中的通信功率用Pj(1≤j≤k)表示。那么鏈路li與lj就可以被定義為相互干擾。只有滿足 Dis(Si，Sj)≤Dis(Pi)或者 Dis(Si，Dj)≤Dis(Pi)。Dis(Sj，Si)≤Dis(Pj)、Dis(Sj，Di)≤Dis(Pj)。則對于網(wǎng)絡(luò)中任何兩條鏈路li、lj，假如兩者相互干擾，那么就記做是 MI(li，lj)=1，反之則 MI(li，lj)=0。

二、基于MM傳感器網(wǎng)絡(luò)無沖突信道分配算法介紹

為了最大限度地控制數(shù)據(jù)通信過程中對于能量的消耗以及控制通信所影響的范圍，文中采用建立在最短路徑能量基礎(chǔ)上的一種MM傳感器網(wǎng)絡(luò)中，無沖突信道分配算法選擇時的混合功率路由算法。對于任何一個由R個節(jié)點(diǎn)(其中包括一個Sink節(jié)點(diǎn))所構(gòu)成的MM傳感器網(wǎng)絡(luò)，我們都將其代價(jià)矩陣看做是［COSTi，j］R×R。假如在節(jié)點(diǎn) Si處可以實(shí)現(xiàn)和節(jié)點(diǎn) Sj進(jìn)行特定級功率的直接通信，那么就確定為COSTi，j=E(OCP(Si，Sj)); 反之則認(rèn)為是 COSTi，j=+ ∞.通過上文所規(guī)定的代價(jià)矩陣，可以推斷出一種建立在Dijkstra最短路徑前提上的混合功率路由算法。

三、無沖突信道分配上界

(一)沖突信道

就MM傳感器網(wǎng)絡(luò)而言，通過選擇HPRA算法最終推算出網(wǎng)絡(luò)的路由之后，就相當(dāng)于明確了網(wǎng)絡(luò)中與之相對應(yīng)的路由拓?fù)?，即網(wǎng)絡(luò)的拓?fù)鋱D(TG)。TG指的是一個將Sink節(jié)點(diǎn)看做是根的樹。在研究中通過對TG進(jìn)行進(jìn)一步的邊—點(diǎn)進(jìn)一步抽象，就可以順利推出網(wǎng)絡(luò)中旬在的信道沖突圖。完成該步操作只需要兩個步驟:首先將位于拓?fù)鋱D中的任何一條鏈路li進(jìn)行抽象，最終將其定義為沖突圖中存在的電Ni;其次，針對任何兩條鏈路li以及l(fā)j，找到在沖突圖中與之相對應(yīng)的點(diǎn)Ni、Nj，假如滿足MI(li，lj)=1，那么可以將Ni以及Nj這兩點(diǎn)之間連成一條邊。

(二)對基于MM傳感器網(wǎng)絡(luò)無沖突信道分配算法的特性推導(dǎo)

對于任何一個信道沖突圖CG來講，全部有滿足條件的 X(CG)≤Δ(CG)+1.成立。在公式中，v(CG)代表的是圖CG中存在的最大頂點(diǎn)度。可以推斷出，位于這樣的鏈中，所存在的最大長度一定可以用K+1表示。再加上存在于奇圈中的沖突途中一定會包含有奇數(shù)個頂點(diǎn)，任何一個頂點(diǎn)都有與之相對應(yīng)的一條鏈路，而任何一條鏈路都能夠在拓?fù)鋱D中找到與之相對應(yīng)的Sensor節(jié)點(diǎn)，那么就推出在奇圈中，應(yīng)當(dāng)最多有2K+1個與之相對應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn)。一旦網(wǎng)絡(luò)的Sensor節(jié)點(diǎn)規(guī)模超過2K+1的數(shù)值，那么一定能夠推出網(wǎng)絡(luò)的信道沖突圖絕對不會是奇圈，這就能夠進(jìn)一步的證實(shí)網(wǎng)絡(luò)通信半徑大于3倍的網(wǎng)絡(luò)最大功率通信半徑的前提下，Sensor節(jié)點(diǎn)規(guī)模滿足2倍網(wǎng)絡(luò)功率級數(shù)加1的環(huán)境下，網(wǎng)絡(luò)無沖突信道分配的信道數(shù)達(dá)到網(wǎng)絡(luò)信道沖突圖的最大值。

(三)信道分配

通過上述定理的運(yùn)用，我們設(shè)置這樣的條件:在滿足Sensor節(jié)點(diǎn)規(guī)模滿足2倍網(wǎng)絡(luò)功率級數(shù)加1的環(huán)境下，網(wǎng)絡(luò)無沖突信道分配的信道數(shù)達(dá)到網(wǎng)絡(luò)信道沖突圖的最大值的這一定理下，筆者決定使用一種滿足此次試驗(yàn)要求的信道分配算法，即所說的無沖突信道分配算法，在該種算法中假設(shè)網(wǎng)絡(luò)中一共存在△(CG)個正交信道，與此同時網(wǎng)絡(luò)符合規(guī)定的網(wǎng)絡(luò)通信半徑NCR大于3倍的Dis(PK)，且該網(wǎng)絡(luò)中的Sensor節(jié)點(diǎn)規(guī)模超過2K+1。

(四)實(shí)驗(yàn)與結(jié)果分析

我們假設(shè)位于整個網(wǎng)絡(luò)中存在這么一個，即Sink節(jié)點(diǎn)，該節(jié)點(diǎn)和數(shù)目大于二的Sensor節(jié)點(diǎn)相互影響。假如Sensor節(jié)點(diǎn)中，其剛開始工作的初始能量確定為1000個單位，那么其就能夠在3級功率的條件下開展工作。至于每級的功率x，我們將其通信半徑Dis(x)看做是用公式KD與(x-1)兩者相乘所得數(shù)據(jù)之后與BD相加的值，在傳輸過程中，我們將一個數(shù)據(jù)包所消耗的能量E(x)定義為KE與x兩者之間相乘所得到的的數(shù)值，在此次試驗(yàn)中KD值最終與BD相等，同時與KE的值相一致全部等于1，節(jié)點(diǎn)要保證順利接收一個數(shù)據(jù)包必須消耗一個單位的能量。在實(shí)驗(yàn)過程中，假設(shè)任何一個節(jié)點(diǎn)所擁有的信道數(shù)目為△(CG)，任何一個Sensor節(jié)點(diǎn)在實(shí)際工作中都有與之相對應(yīng)的1～△ (CG)個Radio以輔助其正常工作。MMH選擇通過ZCAA算法實(shí)現(xiàn)對信道的科學(xué)分配，通過使用HPRA算法實(shí)現(xiàn)對路由的選擇，SMH網(wǎng)絡(luò)中保證有數(shù)量足夠的信道數(shù)，操作人員通過使用HPRA算法實(shí)現(xiàn)對路由選擇。在SSM網(wǎng)絡(luò)中往往有且只有一個Radio以及一個Channel，可以在最大功率下進(jìn)行工作，運(yùn)用最短路徑算法對進(jìn)行路由完成工作，接下來操作人員需要單獨(dú)使用MMH、SMH和SSM對以上闡述工作中的工作進(jìn)行表示，并對其開展相應(yīng)的協(xié)議規(guī)定和運(yùn)用。

［1］W H Tam，Y C Tseng.Joint multi-channel link layer and multi-path routing design for wireless mesh networks.Proc of IN-FOCOM，2010，(7).

［2］梁振球，陳 雅.無線傳感器網(wǎng)絡(luò)移動代理路由算法的仿真研究［J］. 計(jì)算機(jī)仿真，2011，(2).