傳輸信號時,電磁波會逐漸衰減,衰減的原因有兩個:一是傳輸距離導致的衰減;二是信號頻率導致的衰減。電磁波傳輸衰減損耗計算公式為:
Lp=32.4+20Log(f)+20Log(d)
其中,表示信號頻率,單位是MHz,d表示傳輸距離,單位是km。傳播信號的損耗隨著傳輸距離的增加而逐漸變大,在密度不同的介質中進行信息傳播,傳播信號衰減更大,每次穿過撞墻,信號強度便會縮減10%左右,信號傳播速度會降至原來的60%~70%。
信號通過無線傳輸時,也會受到繞射、散射以及反射的影響而導致信號接收差的情況。繞射就是傳播信號在無線傳輸時,如果遇到尖銳的邊緣阻擋,就會自動饒過障礙物繼續傳播的現象;散射是指信號傳輸時碰到大量比信號波小的障礙物,就會自動射散的現象;而反射現象指的是信號在傳輸過程中,遇到比信號波長的障礙物會進行反射。
除了上述原因之外,不同的無線信號還會互相干擾,這也是導致信號損耗的另一個原因。而在理想傳播路徑中,傳播的損耗公式可表示為:
Lp=10Log(d)-20Log(hs)-20Log(hr)
該公式中,hs表示發射端的電線高度,hr表示接收端的電線高度。一般來說,這兩種電線高度與信號的耗損也有關系,在一定范圍內,電線越高,信號耗損越小,當電線高度是平時的一倍時,能夠減少信號耗損6dB。現階段,由于傳輸數據的量越來越大,基于無線傳輸的調度算法開始無法滿足當前需要,越來越多的大規模無線傳輸網絡開始使用分布式調度算法,因此,分布式算法的設計受到很多通信企業的重視。
(1)圖算法調度技術
網絡連接關系可以用一個有向或無向圖來表示,這樣就能以建立圖像模型的方式來解決MAC層的調度問題。如下圖所示:
四個頂點的無向圖
該圖形模型主要由一個邊長為10cm的正方形構成,假設正方形的每一個頂點都表示一個節點,則該模型中存在四個節點,即圖中所示的①②③④。在線路對稱的情況下,設每一個節點的傳輸距離都為12m。然后,再建立信號干擾模型,如下圖:
形成的鏈路沖撞關系
既表示了鏈路的連接關系,又表示了形成的鏈路沖撞關系。
形成的鏈路沖撞關系
上圖是一個調度方案,按照尋找最大獨立集的方式,可得{{1',3'},{1”,3”},{2',4'},{2”,4”}}。
通過調度節點和1-跳干擾模型,得出的合理調度方案之一為{{1,3},{2,4}}。在特定情況下,調度問題可以轉化為其他種類的問題。例如,如果將節點作為調度對象,模型是1-跳干擾模型的情況下,調度問題就可轉化成兩種問題,第一是圖的最大化集成問題,第二是圖的點染色問題,而如果將鏈路作為相應的調度對象,也可將調度問題轉化為兩種問題,一是圖的匹配問題,二是圖的邊染色問題。圖的點染色和邊染色問題分別對應NP問題和NPC問題。調度算法的性能指標有多種,其中,算法的計算復雜度是比較重要的一個。
(2)極大獨立集算法分析
極大獨立集問題屬于NPC問題,研究該問題可以實現分布式調度算法。以下是Schneider算法的狀態轉化圖:
Schneider算法的狀態圖
平衡節點;②competitor表示競爭節點;③ruled表示平衡節點的鄰居節點;④dominator表示加入MIS的節點;⑤dominated表示dominator的鄰居節點。
在算法的運算過程中,開始時,節點都處于competitor狀態;結束時,存在兩種情況:非極大集中的節點處于dominated狀態,極大集中的節點則處于dominator狀態。
網絡中的節點會在不同的狀態進行不同的工作,當節點處于competitor狀態時,會與r值進行相關比較,然后才自動更新;當節點處于ruler狀態,節點地址發生轉移,重新進入competitor狀態。最終的結果是所有節點的最終狀態不是處于dominator狀態,就是處于dominated狀態。
算法執行時,整個過程分成三個層級,第一層級由若干個stage組成,第二層級由每個stage下包含的若干個phase組成,第三層級的每個phase由幾個domination組成。在domination階段,競爭節點會與相鄰節點比較r值,之后進行自我更新。若一個phase階段中對應的所有domination階段結束,則該phase階段結束;若每個sage對應的所有phae階段結束,則該stage階段結束;當所有的stage階段結束時,在MIS中的節點會處于dominator狀態,不在MIS中的節點會處于dominated狀態,最后,算法結束。