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

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


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

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

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


　　該公式中，hs表示發射端的電線高度，hr表示接收端的電線高度。一般來說，這兩種電線高度與信號的耗損也有關系，在一定范圍內，電線越高，信號耗損越小，當電線高度是平時的一倍時，能夠減少信號耗損6dB?，F階段，由于傳輸數據的量越來越大，基于無線傳輸的調度算法開始無法滿足當前需要，越來越多的大規模無線傳輸網絡開始使用分布式調度算法，因此，分布式算法的設計受到很多通信企業的重視。

　?。?）圖算法調度技術

　　網絡連接關系可以用一個有向或無向圖來表示，這樣就能以建立圖像模型的方式來解決MAC層的調度問題。如下圖所示：

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

　　既表示了鏈路的連接關系，又表示了形成的鏈路沖撞關系。

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

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

　?。?）極大獨立集算法分析

　　極大獨立集問題屬于NPC問題，研究該問題可以實現分布式調度算法。以下是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狀態，最后，算法結束。