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

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


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

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

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


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

　?。?）圖算法調(diào)度技術(shù)

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

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

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

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

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

　?。?）極大獨(dú)立集算法分析

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

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

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

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

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