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

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


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

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

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


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

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

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

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

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

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

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

　　（2）極大獨(dú)立集算法分析

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

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

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