分布式調(diào)度問題是物聯(lián)網(wǎng)中的難點。由于物聯(lián)網(wǎng)采用的是無線傳輸信道，傳輸媒介是電磁波，因此很容易受天氣和地理環(huán)境的干擾。同時，以無線信道傳輸數(shù)據(jù)還會因為傳輸距離太遠而產(chǎn)生信號衰減和信號失真，這些特性決定了物聯(lián)網(wǎng)分布式調(diào)度的復(fù)雜性。

　　傳輸信號時，電磁波會逐漸衰減，衰減的原因有兩個：一是傳輸距離導(dǎo)致的衰減；二是信號頻率導(dǎo)致的衰減。電磁波傳輸衰減損耗計算公式為：


　　其中，表示信號頻率，單位是MHz，d表示傳輸距離，單位是km。傳播信號的損耗隨著傳輸距離的增加而逐漸變大，在密度不同的介質(zhì)中進行信息傳播，傳播信號衰減更大，每次穿過撞墻，信號強度便會縮減10%左右，信號傳播速度會降至原來的60%～70%。

　　信號通過無線傳輸時，也會受到繞射、散射以及反射的影響而導(dǎo)致信號接收差的情況。繞射就是傳播信號在無線傳輸時，如果遇到尖銳的邊緣阻擋，就會自動饒過障礙物繼續(xù)傳播的現(xiàn)象；散射是指信號傳輸時碰到大量比信號波小的障礙物，就會自動射散的現(xiàn)象；而反射現(xiàn)象指的是信號在傳輸過程中，遇到比信號波長的障礙物會進行反射。

　　除了上述原因之外，不同的無線信號還會互相干擾，這也是導(dǎo)致信號損耗的另一個原因。而在理想傳播路徑中，傳播的損耗公式可表示為：


　　該公式中，hs表示發(fā)射端的電線高度，hr表示接收端的電線高度。一般來說，這兩種電線高度與信號的耗損也有關(guān)系，在一定范圍內(nèi)，電線越高，信號耗損越小，當電線高度是平時的一倍時，能夠減少信號耗損6dB。現(xiàn)階段，由于傳輸數(shù)據(jù)的量越來越大，基于無線傳輸?shù)恼{(diào)度算法開始無法滿足當前需要，越來越多的大規(guī)模無線傳輸網(wǎng)絡(luò)開始使用分布式調(diào)度算法，因此，分布式算法的設(shè)計受到很多通信企業(yè)的重視。

　　（1）圖算法調(diào)度技術(shù)

　　網(wǎng)絡(luò)連接關(guān)系可以用一個有向或無向圖來表示，這樣就能以建立圖像模型的方式來解決MAC層的調(diào)度問題。如下圖所示：

　　該圖形模型主要由一個邊長為10cm的正方形構(gòu)成，假設(shè)正方形的每一個頂點都表示一個節(jié)點，則該模型中存在四個節(jié)點，即圖中所示的①②③④。在線路對稱的情況下，設(shè)每一個節(jié)點的傳輸距離都為12m。然后，再建立信號干擾模型，如下圖：

　　既表示了鏈路的連接關(guān)系，又表示了形成的鏈路沖撞關(guān)系。

　　上圖是一個調(diào)度方案，按照尋找最大獨立集的方式，可得{{1'，3'}，{1”，3”}，{2'，4'}，{2”，4”}}。

　　通過調(diào)度節(jié)點和1-跳干擾模型，得出的合理調(diào)度方案之一為{{1，3}，{2，4}}。在特定情況下，調(diào)度問題可以轉(zhuǎn)化為其他種類的問題。例如，如果將節(jié)點作為調(diào)度對象，模型是1-跳干擾模型的情況下，調(diào)度問題就可轉(zhuǎn)化成兩種問題，第一是圖的最大化集成問題，第二是圖的點染色問題，而如果將鏈路作為相應(yīng)的調(diào)度對象，也可將調(diào)度問題轉(zhuǎn)化為兩種問題，一是圖的匹配問題，二是圖的邊染色問題。圖的點染色和邊染色問題分別對應(yīng)NP問題和NPC問題。調(diào)度算法的性能指標有多種，其中，算法的計算復(fù)雜度是比較重要的一個。

　　（2）極大獨立集算法分析

　　極大獨立集問題屬于NPC問題，研究該問題可以實現(xiàn)分布式調(diào)度算法。以下是Schneider算法的狀態(tài)轉(zhuǎn)化圖：

　　平衡節(jié)點；②competitor表示競爭節(jié)點；③ruled表示平衡節(jié)點的鄰居節(jié)點；④dominator表示加入MIS的節(jié)點；⑤dominated表示dominator的鄰居節(jié)點。

　　在算法的運算過程中，開始時，節(jié)點都處于competitor狀態(tài)；結(jié)束時，存在兩種情況：非極大集中的節(jié)點處于dominated狀態(tài)，極大集中的節(jié)點則處于dominator狀態(tài)。

　　網(wǎng)絡(luò)中的節(jié)點會在不同的狀態(tài)進行不同的工作，當節(jié)點處于competitor狀態(tài)時，會與r值進行相關(guān)比較，然后才自動更新；當節(jié)點處于ruler狀態(tài)，節(jié)點地址發(fā)生轉(zhuǎn)移，重新進入competitor狀態(tài)。最終的結(jié)果是所有節(jié)點的最終狀態(tài)不是處于dominator狀態(tài)，就是處于dominated狀態(tài)。

　　算法執(zhí)行時，整個過程分成三個層級，第一層級由若干個stage組成，第二層級由每個stage下包含的若干個phase組成，第三層級的每個phase由幾個domination組成。在domination階段，競爭節(jié)點會與相鄰節(jié)點比較r值，之后進行自我更新。若一個phase階段中對應(yīng)的所有domination階段結(jié)束，則該phase階段結(jié)束；若每個sage對應(yīng)的所有phae階段結(jié)束，則該stage階段結(jié)束；當所有的stage階段結(jié)束時，在MIS中的節(jié)點會處于dominator狀態(tài)，不在MIS中的節(jié)點會處于dominated狀態(tài)，最后，算法結(jié)束。