支持實(shí)時(shí)業(yè)務(wù)的同步接入FPRP及其改進(jìn)的E-TDMA----郭巖

1、支持實(shí)時(shí)業(yè)務(wù)的同步接入FPRP及其改進(jìn)的E-TDMA 姓名： 郭 巖 學(xué)號(hào)：Z201517221 工作單位：中國(guó)電信洛陽(yáng)分公司 聯(lián)系電話州大學(xué)2015級(jí)電子與通信工程一、FPRP協(xié)議1.FPRP協(xié)議介紹2.FPRP協(xié)議的關(guān)鍵問(wèn)題3.FPRP的信道劃分與幀結(jié)構(gòu)4.FPRP的五握手競(jìng)爭(zhēng)機(jī)制5.貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6.FPRP死鎖現(xiàn)象的消除7.小結(jié)二、E-TDMA協(xié)議1.E-TDMA協(xié)議介紹及幀結(jié)構(gòu)2.E-TDMA節(jié)點(diǎn)時(shí)隙狀態(tài)3.E-TDMA協(xié)議中的資源預(yù)約過(guò)程4.E-TDMA協(xié)議中的資源釋放過(guò)程1partFPRP協(xié)議1. FPRP協(xié)議介紹2.FPRP協(xié)議的關(guān)鍵

2、問(wèn)題3.FPRP的信道劃分與幀結(jié)構(gòu)4.FPRP的五握手競(jìng)爭(zhēng)機(jī)制5.貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6.FPRP死鎖現(xiàn)象的消除7.小結(jié)FPRP協(xié)議介紹 FPRP(Five一Phase Reservation Protocol)：五步預(yù)留協(xié)議u 工作在半雙工的同步網(wǎng)絡(luò)中,又稱為五握手預(yù)約協(xié)議。u FPRP在控制信道內(nèi)，通過(guò)競(jìng)爭(zhēng)的方式完成無(wú)沖突的廣播信息資源的預(yù)約。該協(xié)議實(shí)現(xiàn)了全分布式的無(wú)線媒質(zhì)接入控制,具有對(duì)網(wǎng)絡(luò)規(guī)模的變化不敏感,有較高的靈活性、適應(yīng)性、可靠性等優(yōu)點(diǎn)。u FPRP不僅可以完成可靠的廣播信息資源的預(yù)約,而且控制部分開(kāi)銷相對(duì)較小。u FPRP通過(guò)五次握手機(jī)制可以為廣播業(yè)務(wù)預(yù)約無(wú)沖突的廣

3、播信息時(shí)隙，節(jié)點(diǎn)一旦預(yù)約成功，廣播業(yè)務(wù)的傳送具有較高的可靠性。1partFPRP協(xié)議1. FPRP協(xié)議介紹2. FPRP協(xié)議的關(guān)鍵問(wèn)題3.FPRP的信道劃分與幀結(jié)構(gòu)4.FPRP的五握手競(jìng)爭(zhēng)機(jī)制5.貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6.FPRP死鎖現(xiàn)象的消除7.小結(jié)FPRP協(xié)議的關(guān)鍵問(wèn)題-對(duì)可靠廣播的支持 FPRP把信道分為預(yù)約信道和信息信道，有業(yè)務(wù)要傳送的節(jié)點(diǎn)在預(yù)約信道以概率p發(fā)起預(yù)約過(guò)程,通過(guò)控制分組的廣播式的交互競(jìng)爭(zhēng)信道資源。節(jié)點(diǎn)一旦競(jìng)爭(zhēng)成功,就預(yù)約到與預(yù)約時(shí)隙相對(duì)應(yīng)的廣播信息時(shí)隙，節(jié)點(diǎn)自動(dòng)占用該時(shí)隙進(jìn)行數(shù)據(jù)傳遞直到下一次預(yù)約信道到來(lái)時(shí)自動(dòng)釋放該信息時(shí)隙，如果節(jié)點(diǎn)仍然需要信息時(shí)隙，就在下一個(gè)

4、控制信道中重新競(jìng)爭(zhēng)資源。FPRP協(xié)議的關(guān)鍵問(wèn)題-對(duì)可靠廣播的支持排除節(jié)點(diǎn)的移動(dòng)造成的沖突：u 在沒(méi)有非孤立死鎖(兩個(gè)鄰節(jié)點(diǎn)由于沒(méi)有公共鄰節(jié)點(diǎn)可能會(huì)共同預(yù)約到相同的信息時(shí)隙)的情況下，F(xiàn)PRP保證了預(yù)約到的資源在兩跳范圍內(nèi)是無(wú)沖突的廣播信道，源節(jié)點(diǎn)的廣播業(yè)務(wù)可以被所有的一跳鄰節(jié)點(diǎn)正確接收。u 在有非孤立死鎖的情況下,FPRP通過(guò)發(fā)送EP分組將非孤立死鎖現(xiàn)象發(fā)生的概率減小到極小。因此,稱FPRP可為節(jié)點(diǎn)預(yù)約到無(wú)沖突的廣播信息資源。FPRP協(xié)議的關(guān)鍵問(wèn)題-接收節(jié)點(diǎn)沖突檢測(cè)機(jī)制 無(wú)線通信的特點(diǎn)使得發(fā)送節(jié)點(diǎn)無(wú)法直接探測(cè)到接收節(jié)點(diǎn)處的沖突,但是,多個(gè)分組同時(shí)到達(dá)接收節(jié)點(diǎn)時(shí),接收節(jié)點(diǎn)可以探測(cè)到分組的沖突。因

5、此,FPRP通過(guò)接收節(jié)點(diǎn)發(fā)送沖突報(bào)告來(lái)通知發(fā)送節(jié)點(diǎn)有沖突發(fā)生。FPRP協(xié)議的關(guān)鍵問(wèn)題-隱藏終端問(wèn)題u 隱藏終端問(wèn)題是移動(dòng)自組織網(wǎng)絡(luò)MAC層協(xié)議必須解決的問(wèn)題，也是影響廣播業(yè)務(wù)的可靠性的重要因素。u 隱藏終端是指在接收終端的通信范圍內(nèi)而在發(fā)送終端的通信范圍外的終端，隱藏終端因偵聽(tīng)不到發(fā)送終端的發(fā)送而可能向接收終端發(fā)送數(shù)據(jù),造成數(shù)據(jù)在接收終端處發(fā)生碰撞。u FPRP通過(guò)控制分組的交互解決隱藏終端問(wèn)題。FPRP的預(yù)約節(jié)點(diǎn)向鄰節(jié)點(diǎn)廣播一個(gè)很小的預(yù)約分組,鄰節(jié)點(diǎn)偵聽(tīng)到多個(gè)預(yù)約分組時(shí)就知道有多個(gè)預(yù)約節(jié)點(diǎn)的預(yù)約分組在該鄰節(jié)點(diǎn)處發(fā)生沖突,該鄰節(jié)點(diǎn)發(fā)送一個(gè)沖突報(bào)告分組通知預(yù)約節(jié)點(diǎn)有沖突發(fā)生,從而通過(guò)控制分組的交

6、互解決了隱藏終端問(wèn)題。1partFPRP協(xié)議1. FPRP協(xié)議介紹2. FPRP協(xié)議的關(guān)鍵問(wèn)題3. FPRP的信道劃分與幀結(jié)構(gòu)4.FPRP的五握手競(jìng)爭(zhēng)機(jī)制5.貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6.FPRP死鎖現(xiàn)象的消除7.小結(jié)FPRP的信道劃分與幀結(jié)構(gòu) FPRP信道被分為控制時(shí)期和信息時(shí)期，相應(yīng)的,幀結(jié)構(gòu)被分為預(yù)約幀和信息幀。幀結(jié)構(gòu)的具體劃分情況如圖所示，RF為預(yù)約幀,在每個(gè)RF后根據(jù)不同的應(yīng)用場(chǎng)合跟有不同數(shù)目的信息幀(IF),但是在同一網(wǎng)絡(luò)環(huán)境下,信息幀的數(shù)目是確定的。RF和IF中包含的時(shí)隙數(shù)目相同(這里假設(shè)包含有N個(gè)時(shí)隙),RF中的時(shí)隙稱為預(yù)約時(shí)隙(RS)，IF中的稱為信息時(shí)隙(IS)。FP

7、RP的幀結(jié)構(gòu)FPRP的信道劃分與幀結(jié)構(gòu) RF中的預(yù)約時(shí)隙與IF中的信息時(shí)隙一一對(duì)應(yīng),也就是說(shuō),節(jié)點(diǎn)一旦在RF的某個(gè)RS中競(jìng)爭(zhēng)成功,它將占用緊隨在RF之后的IF中相應(yīng)位置的信息時(shí)隙(IS),直到下一個(gè)RF到來(lái)為止。每一個(gè)RS劃分為M個(gè)預(yù)約周期(RC),每個(gè)RC是一個(gè)五握手預(yù)約過(guò)程。在RC中,節(jié)點(diǎn)通過(guò)五握手機(jī)制完成資源預(yù)約。FPRP的幀結(jié)構(gòu)1partFPRP協(xié)議1. FPRP協(xié)議介紹2. FPRP協(xié)議的關(guān)鍵問(wèn)題3. FPRP的信道劃分與幀結(jié)構(gòu)4. FPRP的五握手競(jìng)爭(zhēng)機(jī)制5.貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6.FPRP死鎖現(xiàn)象的消除7.小結(jié)FPRP的五握手競(jìng)爭(zhēng)機(jī)制 所謂五握手競(jìng)爭(zhēng)機(jī)制,指的是節(jié)點(diǎn)在

8、競(jìng)爭(zhēng)周期經(jīng)過(guò)五次信息交互完成信息時(shí)隙的預(yù)約。FPRP中的五次握手運(yùn)行的基本過(guò)程如下:(1)預(yù)約請(qǐng)求階段(RR，Reservation Request Phase) 在該階段中,需要預(yù)約資源的節(jié)點(diǎn)以概率p向一跳鄰節(jié)點(diǎn)廣播一個(gè)預(yù)約請(qǐng)求(RR)分組。發(fā)送RR分組的節(jié)點(diǎn)在協(xié)議中稱為預(yù)約節(jié)點(diǎn)(RN)。不需要進(jìn)行資源預(yù)約的節(jié)點(diǎn)在該階段進(jìn)行監(jiān)聽(tīng),這些節(jié)點(diǎn)可能從鄰節(jié)點(diǎn)那里收不到RR分組,也可能會(huì)收到一個(gè)或多個(gè)RR分組。有多個(gè)RR分組到達(dá)時(shí),節(jié)點(diǎn)將在信道上監(jiān)聽(tīng)到一次碰撞。FPRP的五握手競(jìng)爭(zhēng)機(jī)制(2)沖突報(bào)告階段(CR，Collision Report Phase) 如果節(jié)點(diǎn)在RR階段偵聽(tīng)到兩個(gè)或兩個(gè)以上的預(yù)約

9、請(qǐng)求分組,該節(jié)點(diǎn)就知道在該預(yù)約周期中有多個(gè)預(yù)約節(jié)點(diǎn)同時(shí)發(fā)起競(jìng)爭(zhēng),則該節(jié)點(diǎn)在CR階段廣播一個(gè)沖突報(bào)告(CR)分組，否則它保持沉默。通過(guò)在該階段對(duì)CR的監(jiān)聽(tīng),RN判斷它的RR是否和別人發(fā)生碰撞。如果未接收到CR,RN認(rèn)為它所發(fā)送的RR被每個(gè)鄰節(jié)點(diǎn)正確接收。這樣,一個(gè)RN節(jié)點(diǎn)就變成了一個(gè)發(fā)送節(jié)點(diǎn)(TN)，在下面的預(yù)約證實(shí)階段就可以預(yù)約時(shí)隙。很明顯,RR/CR交互消除了隱藏終端問(wèn)題。FPRP的五握手競(jìng)爭(zhēng)機(jī)制(3)預(yù)約證實(shí)階段(RC，Reservation Confirmation Phase) 在這個(gè)階段里,預(yù)約被建立。TN在這個(gè)狀態(tài)里廣播一個(gè)預(yù)約證實(shí)(RC)分組通知一跳鄰節(jié)點(diǎn)相應(yīng)的時(shí)隙被預(yù)約,每一個(gè)

10、正確接收到這個(gè)RC的一跳鄰節(jié)點(diǎn)都知道了該時(shí)隙己被預(yù)約,它們將在信息期的相應(yīng)時(shí)隙里從TN接收信息,并且不再競(jìng)爭(zhēng)該時(shí)隙。FPRP的五握手競(jìng)爭(zhēng)機(jī)制(4)預(yù)約確認(rèn)階段(RA，Reservation Acknowledgement Phase) 收到預(yù)約證實(shí)(RC)分組的節(jié)點(diǎn)發(fā)送預(yù)約確認(rèn)(RA)分組通知TN及TN的兩跳鄰節(jié)點(diǎn)，從而兩跳鄰節(jié)點(diǎn)知道兩跳遠(yuǎn)處有節(jié)點(diǎn)預(yù)約資源成功。如果TN沒(méi)有相連節(jié)點(diǎn),它就收不到預(yù)約確認(rèn)(RA)分組,由此就可以知道TN是一孤立節(jié)點(diǎn)，TN就沒(méi)必要進(jìn)行信息的發(fā)送。如果沒(méi)有該階段,孤立RN就會(huì)因?yàn)闆](méi)有鄰節(jié)點(diǎn)為其發(fā)送CR而總成為TN,從而產(chǎn)生死鎖。FPRP的五握手競(jìng)爭(zhēng)機(jī)制(5)填充/消除

11、階段(P/E，Packing/Elimination Phase) 在該階段,網(wǎng)絡(luò)中有兩種類型的分組進(jìn)行傳送：u PP(Packing Packet) 該分組由TN的兩跳鄰節(jié)點(diǎn)發(fā)送,收到PP的節(jié)點(diǎn)因此知道三跳遠(yuǎn)的節(jié)點(diǎn)預(yù)約成功,相應(yīng)的,部分鄰節(jié)點(diǎn)將不能再競(jìng)爭(zhēng)同一個(gè)時(shí)隙。利用這一點(diǎn)可相應(yīng)提高三跳鄰節(jié)點(diǎn)的競(jìng)爭(zhēng)概率p,增加距TN三跳遠(yuǎn)的節(jié)點(diǎn)的預(yù)約成功率,加快預(yù)約收斂速度。FPRP的五握手競(jìng)爭(zhēng)機(jī)制u EP(Elimination packet) 該分組由TN節(jié)點(diǎn)以0.5的概率發(fā)送,用來(lái)消除相鄰節(jié)點(diǎn)之間可能存在的非孤立死鎖(DL),如果TN在這個(gè)狀態(tài)沒(méi)有發(fā)送但是收到了一個(gè)EP,說(shuō)明存在非孤立死鎖。這種情況

12、下,它重新標(biāo)明由發(fā)送EP的那個(gè)TN使用這個(gè)時(shí)隙,收到EP的節(jié)點(diǎn)在這個(gè)時(shí)隙里將只進(jìn)行接收而不傳送信息,它將重新競(jìng)爭(zhēng)另外的時(shí)隙。預(yù)約成功的節(jié)點(diǎn)在同一個(gè)預(yù)約時(shí)隙的后繼的預(yù)約周期的RR階段頻繁以0.5的概率廣播EP分組來(lái)消除可能存在的非孤立死鎖。在實(shí)際應(yīng)用中,可以根據(jù)網(wǎng)絡(luò)情況來(lái)決定是否需要第五次握手過(guò)程。FPRP的五握手競(jìng)爭(zhēng)機(jī)制 經(jīng)過(guò)上述的一個(gè)完整預(yù)約過(guò)程后,節(jié)點(diǎn)的可能狀態(tài)為:預(yù)約成功的節(jié)點(diǎn)為傳遞狀態(tài),其一跳鄰節(jié)點(diǎn)的狀態(tài)為接收狀態(tài),其兩跳鄰節(jié)點(diǎn)的狀態(tài)為鎖狀態(tài),處于這三種狀態(tài)的節(jié)點(diǎn)在同一個(gè)預(yù)約時(shí)隙里不允許再參與資源競(jìng)爭(zhēng),其余節(jié)點(diǎn)的狀態(tài)為空閑狀態(tài)。只有處于傳遞狀態(tài)的節(jié)點(diǎn)才能在相應(yīng)的信息時(shí)隙里進(jìn)行數(shù)據(jù)傳送。

13、FPRP的五握手競(jìng)爭(zhēng)機(jī)制協(xié)議預(yù)約過(guò)程圖 右圖是對(duì)FPRP預(yù)約過(guò)程的一個(gè)說(shuō)明。u 在RR階段,節(jié)點(diǎn)1、3、7發(fā)起預(yù)約過(guò)程，此時(shí)1、3、7的一跳鄰節(jié)點(diǎn)2、4、6、8將接收到RR分組。其中,節(jié)點(diǎn)2由于是1、3的公共鄰節(jié)點(diǎn),所以RR分組在2處發(fā)生碰撞。u 在階段2,節(jié)點(diǎn)2將發(fā)送CR分組報(bào)告沖突。節(jié)點(diǎn)1、3接收到CR后結(jié)束此次預(yù)約過(guò)程。FPRP的五握手競(jìng)爭(zhēng)機(jī)制協(xié)議預(yù)約過(guò)程圖u 與此同時(shí),節(jié)點(diǎn)7由于未接收到CR分組,將在階段3發(fā)送RC分組繼續(xù)完成預(yù)約過(guò)程。節(jié)點(diǎn)7的一跳鄰節(jié)點(diǎn)接收到RC分組后,在階段4發(fā)送RA分組,通知7的兩跳鄰節(jié)點(diǎn)，7己預(yù)約了IF中該時(shí)隙的資源,同時(shí)避免出現(xiàn)孤立死鎖問(wèn)題。FPRP的五握手競(jìng)

14、爭(zhēng)機(jī)制協(xié)議預(yù)約過(guò)程圖u 在階段5，7發(fā)送EP,消除非孤立死鎖。同時(shí),7的兩跳鄰節(jié)點(diǎn)發(fā)送PP,通知三跳鄰節(jié)點(diǎn)提高接入概率p,加快節(jié)點(diǎn)預(yù)約資源的收斂速度。u 節(jié)點(diǎn)7預(yù)約成功后,將在當(dāng)前RS隨后的每個(gè)RC的階段1以0.5的概率發(fā)送EP,盡可能地消除非孤立死鎖。 五次信息交互后,各個(gè)節(jié)點(diǎn)的狀態(tài)如圖中結(jié)果所示。1partFPRP協(xié)議1. FPRP協(xié)議介紹2. FPRP協(xié)議的關(guān)鍵問(wèn)題3. FPRP的信道劃分與幀結(jié)構(gòu)4. FPRP的五握手競(jìng)爭(zhēng)機(jī)制5. 貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6.FPRP死鎖現(xiàn)象的消除7.小結(jié)pseudo一Baysian算法描述及競(jìng)爭(zhēng)概率p的確定 在 FPRP 協(xié)議中，節(jié)點(diǎn)如果需要預(yù)

15、約資源，將在預(yù)約周期中以概率p發(fā)起時(shí)隙競(jìng)爭(zhēng)過(guò)程。其中概率p 采用pseudo-Baysian 算法獲得。 pseudo-Baysian 算法基本思想 pseudo-Baysian 算法中，每一個(gè)節(jié)點(diǎn)要估計(jì)其周圍資源競(jìng)爭(zhēng)者的數(shù)量n，調(diào)整其競(jìng)爭(zhēng)概率p（p1/n）。每次競(jìng)爭(zhēng)結(jié)束后，節(jié)點(diǎn)更新其估計(jì)值n： 如果競(jìng)爭(zhēng)成功或競(jìng)爭(zhēng)期空閑，nn1； 如果出現(xiàn)沖突，nn（e-2）-1。 該算法非常適合單跳 ALOHA 網(wǎng)絡(luò)，但是在移動(dòng)自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)必須考慮兩跳以內(nèi)的競(jìng)爭(zhēng)者，以及網(wǎng)絡(luò)拓?fù)涞碾S機(jī)變化和鄰節(jié)點(diǎn)數(shù)量的改變。 根據(jù)這些特點(diǎn)， 將pseudo-Baysian 算法應(yīng)用于移動(dòng)自組織網(wǎng)絡(luò)時(shí)，必須對(duì)其進(jìn)行改進(jìn)。

16、pseudo一Byasina算法描述及競(jìng)爭(zhēng)概率p的確定 多跳pseudo-Baysian 算法 在多跳 pseudo-Baysian 算法中，競(jìng)爭(zhēng)概率p 仍等于1/n。但是，n 表示的是兩跳之內(nèi)競(jìng)爭(zhēng)者的數(shù)量，它們稱為鄰居競(jìng)爭(zhēng)者。 一個(gè)節(jié)點(diǎn)需要保持兩個(gè)估計(jì)值：兩跳以內(nèi)競(jìng)爭(zhēng)節(jié)點(diǎn)的數(shù)量nc；需要競(jìng)爭(zhēng)資源，但是由于兩跳之內(nèi)鄰節(jié)點(diǎn)已預(yù)約了資源，而不能進(jìn)行資源競(jìng)爭(zhēng)的節(jié)點(diǎn)數(shù)量nb。當(dāng)一個(gè)節(jié)點(diǎn)預(yù)約成功后，認(rèn)為在它的一跳鄰節(jié)點(diǎn)中有比率為R1 的競(jìng)爭(zhēng)節(jié)點(diǎn)停止了在當(dāng)前時(shí)隙中的競(jìng)爭(zhēng)，在兩跳鄰節(jié)點(diǎn)中該比率為R2，對(duì)于三跳鄰節(jié)點(diǎn)來(lái)說(shuō)比率為R3。多跳pseudo-Baysian 算法表示為：（1）在預(yù)約時(shí)隙的開(kāi)始，節(jié)點(diǎn)將設(shè)

17、置nc 和nb 為ncnb；nb0（在預(yù)約信道的第1 個(gè)預(yù)約時(shí)隙，設(shè)ncNC0，其中NC0 為預(yù)先確定的常量）pseudo一Byasina算法描述及競(jìng)爭(zhēng)概率p的確定（2）節(jié)點(diǎn)根據(jù)監(jiān)聽(tīng)的預(yù)約情況對(duì)nc、nb 進(jìn)行更新： 空閑 ：ncnc1 沖突 ：ncnc（e2）1 成功：設(shè)成功完成預(yù)約過(guò)程的節(jié)點(diǎn)在 x 跳以外。p 當(dāng) x1 時(shí)（節(jié)點(diǎn)不能在當(dāng)前時(shí)隙競(jìng)爭(zhēng)資源）ncnc（1R1）1 nbnbncR1p 當(dāng) x2 時(shí)（節(jié)點(diǎn)不能在當(dāng)前時(shí)隙競(jìng)爭(zhēng)資源）ncnc（1R2）1 nbnbncR2p 當(dāng) x3 時(shí)ncnc（1R3）1 nbnbncR3；（3）節(jié)點(diǎn)調(diào)整競(jìng)爭(zhēng)概率p 為：p1/nc1partFPRP協(xié)議1

18、. FPRP協(xié)議介紹2. FPRP協(xié)議的關(guān)鍵問(wèn)題3. FPRP的信道劃分與幀結(jié)構(gòu)4. FPRP的五握手競(jìng)爭(zhēng)機(jī)制5. 貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6. FPRP死鎖現(xiàn)象的消除7.小結(jié)FPRP死鎖現(xiàn)象的消除(1)孤立死鎖 孤立死鎖在RR階段開(kāi)始形成。孤立節(jié)點(diǎn)（如右圖節(jié)點(diǎn)4）由于沒(méi)有相連的一跳鄰節(jié)點(diǎn)存在，在階段2接收不到CR而成為TN，節(jié)點(diǎn)將在階段3繼續(xù)發(fā)送預(yù)約證實(shí)(RC)分組通知一跳鄰節(jié)點(diǎn)己預(yù)約到資源，從而形成孤立死鎖。該死鎖現(xiàn)象在階段4可以得到解除。在階段4,由于孤立節(jié)點(diǎn)收不到RA,從而該TN明確知道自己為孤立節(jié)點(diǎn),停止向外傳遞信息。 FPRP中存在的死鎖現(xiàn)象可分為孤立死鎖和非孤立死鎖兩種。

19、4321孤立節(jié)點(diǎn)FPRP死鎖現(xiàn)象的消除(2)非孤立死鎖 非孤立死鎖是由于同時(shí)進(jìn)行預(yù)約的節(jié)點(diǎn)無(wú)公共一跳鄰節(jié)點(diǎn)造成的，兩個(gè)相鄰的節(jié)點(diǎn)有多個(gè)共享鄰節(jié)點(diǎn)時(shí)不會(huì)發(fā)生死鎖。然而，這種共享鄰節(jié)點(diǎn)并不總是存在的。如圖所示,發(fā)送RR分組的節(jié)點(diǎn)4和節(jié)點(diǎn)5之間沒(méi)有公共的一跳鄰節(jié)點(diǎn),節(jié)點(diǎn)在發(fā)送RR分組的同時(shí)不能接收,無(wú)法感知RR分組有沖突,并且在階段2中,沒(méi)有公共鄰節(jié)點(diǎn)發(fā)送CR分組。由于兩節(jié)點(diǎn)都不能接收到CR而同時(shí)成為TN,因此形成非孤立死鎖。2765431TNTNFPRP死鎖現(xiàn)象的消除 非孤立死鎖的解決是在階段5通過(guò)發(fā)送EP完成的。在階段5中,假設(shè)TN4以0.5的概率發(fā)送了EP,而TN5同時(shí)以0.5的概率未發(fā)送EP

20、。此時(shí),TN5將接收到TN4發(fā)送的EP,從而知道有非孤立死鎖存在。這種情況下,TN5將放棄該時(shí)隙的使用權(quán),將自己的節(jié)點(diǎn)狀態(tài)標(biāo)為接收狀態(tài),在這個(gè)時(shí)隙里它將接收而不發(fā)送。TN5將重新競(jìng)爭(zhēng)另外的時(shí)隙用于業(yè)務(wù)傳送。 節(jié)點(diǎn)預(yù)約成功以后,將在同一個(gè)預(yù)約時(shí)隙隨后的每一個(gè)預(yù)約周期的階段1中以0.5的概率發(fā)送EP,從而進(jìn)一步降低非孤立死鎖概率。這個(gè)EP不會(huì)干擾到任何一個(gè)RR分組的發(fā)送,因?yàn)轭A(yù)約成功以后,在同一個(gè)預(yù)約時(shí)隙里,兩跳范圍內(nèi)不會(huì)有節(jié)點(diǎn)再進(jìn)行預(yù)約競(jìng)爭(zhēng)。在階段1里，EP的工作方式和階段5的方式相同。通過(guò)EP的頻繁發(fā)送,雖然不能保證完全消除非孤立死鎖問(wèn)題,但可將其發(fā)生概率降到非常低的水平。1partFPRP協(xié)

21、議1. FPRP協(xié)議介紹2. FPRP協(xié)議的關(guān)鍵問(wèn)題3. FPRP的信道劃分與幀結(jié)構(gòu)4. FPRP的五握手競(jìng)爭(zhēng)機(jī)制5. 貝葉斯算法描述及競(jìng)爭(zhēng)概率p的確定6. FPRP死鎖現(xiàn)象的消除7. 小結(jié)FPRP協(xié)議小結(jié)n FPRP在預(yù)約信道通過(guò)五次握手機(jī)制為節(jié)點(diǎn)預(yù)約無(wú)沖突的廣播信息時(shí)隙。n FPRP中每個(gè)預(yù)約節(jié)點(diǎn)以概率p發(fā)起競(jìng)爭(zhēng),節(jié)點(diǎn)根據(jù)控制分組的交互調(diào)整它的競(jìng)爭(zhēng)概率，提高它的競(jìng)爭(zhēng)成功率。n FPRP對(duì)于預(yù)約到的資源采用主動(dòng)釋放的方式,預(yù)約到時(shí)隙資源的節(jié)點(diǎn)在下一個(gè)預(yù)約幀到來(lái)時(shí)自動(dòng)釋放它占用的資源,如果節(jié)點(diǎn)仍然需要業(yè)務(wù)時(shí)隙,它必需在預(yù)約幀重新參與競(jìng)爭(zhēng)。n FPRP適合于拓?fù)渥兓斓木W(wǎng)絡(luò)。n FPRP中由要傳

22、遞業(yè)務(wù)的節(jié)點(diǎn)發(fā)起競(jìng)爭(zhēng)過(guò)程，因此，F(xiàn)PRP只受網(wǎng)絡(luò)中業(yè)務(wù)量的影響,對(duì)于網(wǎng)絡(luò)規(guī)模的變化不敏感。n FPRP雖然保證了廣播業(yè)務(wù)的可靠傳遞,但是沒(méi)有考慮對(duì)于點(diǎn)對(duì)點(diǎn)業(yè)務(wù)的支持。使用FPRP傳遞單播業(yè)務(wù)時(shí),會(huì)造成資源的極大浪費(fèi)。2partE-TDMA協(xié)議1. E-TDMA協(xié)議介紹及幀結(jié)構(gòu)2. E-TDMA節(jié)點(diǎn)時(shí)隙狀態(tài)3. E-TDMA協(xié)議中的資源預(yù)約過(guò)程4. E-TDMA協(xié)議中的資源釋放過(guò)程E-TDMA協(xié)議介紹及幀結(jié)構(gòu)E-TDMA(Evolutionary-TDMA)協(xié)議是在 FPRP 機(jī)制的基礎(chǔ)上，對(duì)節(jié)點(diǎn)的時(shí)隙預(yù)約的過(guò)程進(jìn)行改進(jìn)，改進(jìn)之后，可以實(shí)現(xiàn)一跳鄰居節(jié)點(diǎn)進(jìn)行無(wú)沖突的單播、多播以及廣播業(yè)務(wù)。因此，E

23、-TDMA 協(xié)議在繼承了 FPRP 協(xié)議優(yōu)點(diǎn)的基礎(chǔ)上，能夠更好的滿足網(wǎng)絡(luò)業(yè)務(wù)的需求。E-TDMA 協(xié)議分為兩種調(diào)度形式：p 控制調(diào)度：在控制調(diào)度期間，協(xié)議為每個(gè)節(jié)點(diǎn)分配一個(gè)廣播時(shí)序表，用來(lái)交互控制信息；p 信息調(diào)度：節(jié)點(diǎn)可以根據(jù)自身等需要預(yù)約相應(yīng)數(shù)量的時(shí)隙，用于數(shù)據(jù)傳輸。在采用 E-TDMA 協(xié)議時(shí)，網(wǎng)絡(luò)環(huán)境應(yīng)該滿足以下要求：（1）網(wǎng)絡(luò)中節(jié)點(diǎn)需要保持準(zhǔn)確的定時(shí)，使節(jié)點(diǎn)保持完全同步；（2）網(wǎng)絡(luò)中的信道為對(duì)稱信道（網(wǎng)絡(luò)拓?fù)淇梢杂脽o(wú)向圖表示）；（3）對(duì)于分組傳送速度來(lái)說(shuō)，網(wǎng)絡(luò)拓?fù)渥兓俣容^慢；（4）網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)可以運(yùn)行 FPRP；E-TDMA協(xié)議介紹及幀結(jié)構(gòu) E-TDMA 中，信道被分為控制時(shí)段和

24、信息時(shí)段，這兩個(gè)時(shí)段存在周期性的間隔。E-TDMA 協(xié)議幀結(jié)構(gòu)如右圖所示。p 控制時(shí)段：用來(lái)更新節(jié)點(diǎn)的時(shí)序列表，該時(shí)序列表以廣播的形式發(fā)送，包括控制時(shí)序表和信息時(shí)序列表，控制時(shí)段再分為競(jìng)爭(zhēng)階段與分配階段，競(jìng)爭(zhēng)階段類似 FPRP，分配階段則是將之后的信息幀中的時(shí)隙分配給對(duì)應(yīng)的節(jié)點(diǎn)；p 信息時(shí)段：傳輸節(jié)點(diǎn)信息。E-TDMA協(xié)議介紹及幀結(jié)構(gòu)2partE-TDMA協(xié)議1. E-TDMA協(xié)議介紹及幀結(jié)構(gòu)2. E-TDMA節(jié)點(diǎn)時(shí)隙狀態(tài)3. E-TDMA協(xié)議中的資源預(yù)約過(guò)程4. E-TDMA協(xié)議中的資源釋放過(guò)程E-TDMA節(jié)點(diǎn)時(shí)隙狀態(tài) 在 E-TDMA 協(xié)議中，在每一個(gè)時(shí)隙中，節(jié)點(diǎn)的狀態(tài)用(狀態(tài)(state

25、)，目標(biāo)(target)表示，state 表示在時(shí)隙 s 中節(jié)點(diǎn)的狀態(tài)，target 表示在時(shí)隙 s 中節(jié)點(diǎn)要進(jìn)行發(fā)送或者接收數(shù)據(jù)分組的一跳鄰居節(jié)點(diǎn)。因此，在時(shí)隙 s 中，節(jié)點(diǎn)的狀態(tài)可以分為七種：u 傳輸狀態(tài)(Transport)：在時(shí)隙s ，節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組到鄰居節(jié)點(diǎn) a：( state = Transport， target = a )。如果節(jié)點(diǎn)傳送的分組是廣播分組，則 target = Broadcast。u 接收狀態(tài)(Receive)：在時(shí)隙 s ，從鄰居節(jié)點(diǎn) b 接收數(shù)據(jù)分組：(state=Receive，target = b)。 u 傳輸阻塞狀態(tài)(Block_t)： 在時(shí)隙 s ，

26、在鄰居節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)正從其他節(jié)點(diǎn)接收數(shù)據(jù)分組，而且沒(méi)有鄰居節(jié)點(diǎn)正在傳送分組，state= Block_tu 接收阻塞狀態(tài)(Block_r)：在時(shí)隙 s ，在鄰居節(jié)點(diǎn)中至少存在一個(gè)節(jié)點(diǎn)正向其 他節(jié)點(diǎn)發(fā)送分組，而且沒(méi)有鄰節(jié)點(diǎn)正在接收分組； state= Block_ru 傳輸接收阻塞狀態(tài)(Block_tr)：在時(shí)隙 s ，在鄰居節(jié)點(diǎn)中至少存在一個(gè)節(jié)點(diǎn)正在向其他節(jié)點(diǎn)發(fā)送分組，除此之外，至少存在一個(gè)鄰居節(jié)點(diǎn)正在從其他節(jié)點(diǎn)接收分組； state= Block_tru 碰撞(Collision)：節(jié)點(diǎn)在接收分組時(shí)檢測(cè)到一個(gè)碰撞； state= Collisionu 空閑狀態(tài)(Idle)：節(jié)點(diǎn)空閑，沒(méi)

27、有鄰居節(jié)點(diǎn)處于數(shù)據(jù)分組收發(fā)狀態(tài)。 特別說(shuō)明的是，目標(biāo)(target)僅在前兩個(gè)狀態(tài)有意義，即在傳輸狀態(tài)以及接收狀態(tài)，此外，這些節(jié)點(diǎn)狀態(tài)之間是相互獨(dú)立的，一個(gè)節(jié)點(diǎn)在一個(gè)時(shí)隙里只能處于其中某一種狀態(tài)，我們可以認(rèn)為，在節(jié)點(diǎn)不向外發(fā)送數(shù)據(jù)的時(shí)隙都可以稱為被動(dòng)時(shí)隙E-TDMA節(jié)點(diǎn)時(shí)隙狀態(tài)2partE-TDMA協(xié)議1. E-TDMA協(xié)議介紹及幀結(jié)構(gòu)2. E-TDMA節(jié)點(diǎn)時(shí)隙狀態(tài)3. E-TDMA協(xié)議中的資源預(yù)約過(guò)程4. E-TDMA協(xié)議中的資源釋放過(guò)程E-TDMA協(xié)議中的資源預(yù)約過(guò)程 由于新的預(yù)約可能會(huì)導(dǎo)致沖突，因此預(yù)約一個(gè)新的時(shí)隙要比釋放一個(gè)時(shí)隙更加小心。新的預(yù)約只有和已確定的預(yù)約無(wú)沖突時(shí)才可以完成。節(jié)點(diǎn)在控制期里周期性地交換時(shí)序表，并在一個(gè)鄰節(jié)點(diǎn)列表里保持它的鄰居節(jié)點(diǎn)信息。通過(guò)跟蹤?quán)従庸?jié)點(diǎn)以及它們的時(shí)序表，節(jié)點(diǎn)能夠準(zhǔn)確地