Leach代碼分析

1、目錄一、Leach協(xié)議與NS的關(guān)系2二、 算法設(shè)計思想4三、簇頭建立算法流程圖5四、難點解決7五、 算法運行結(jié)果分析10參考文獻(xiàn)19一、Leach協(xié)議與NS的關(guān)系 為了實現(xiàn)leach 協(xié)議，對ns進(jìn)行擴展。在ns中增加了一個事件驅(qū)動模擬器支持模擬無線傳感器網(wǎng)絡(luò)協(xié)議。這些擴展包括MAC協(xié)議，用于計算和交互的能量分配模型和leach協(xié)議的體系結(jié)構(gòu)。 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以通過簡單的Nodes, Links, Agents和Applications 描述。Nodes相當(dāng)于網(wǎng)絡(luò)中的終端主機， Links 是用于Nodes交互的連接器, Agent用來實現(xiàn)不同網(wǎng)絡(luò)協(xié)議，是支持分組產(chǎn)生和丟棄的節(jié)點。Applic

2、ations用來產(chǎn)生數(shù)據(jù)和實現(xiàn)不同的應(yīng)用函數(shù)。一旦網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立起來后，模擬通過啟動節(jié)點上的Applications運行。 為了在ns中支持無線傳感器網(wǎng)絡(luò)，在ns中增加了 mobile nodes, MAC協(xié)議和信道傳播模型Channel 。 Applications類的頭文件用Tcl語言寫的，節(jié)點中的其他函數(shù)功能用C+語言寫成的。數(shù)據(jù)包的發(fā)送過程：Applications創(chuàng)建數(shù)據(jù)包（data packets）,然后發(fā)送給Agent. Agent執(zhí)行協(xié)議棧中運輸層和網(wǎng)絡(luò)層的功能，將數(shù)據(jù)包發(fā)送給CMUTrace,。 CMUTrace將packets的統(tǒng)計數(shù)據(jù)寫到trace 文件，然后將pack

3、ets發(fā)至Connector。Connector將數(shù)據(jù)包傳送給用于數(shù)據(jù)鏈路處理的鏈路層(LL).經(jīng)過一小段時間的延遲后，數(shù)據(jù)包由LL發(fā)送給Queue緩沖隊列。如果是還沒有傳送過的數(shù)據(jù)包，Queue將以隊列進(jìn)行存儲。然后Queue將數(shù)據(jù)包出隊列，發(fā)送到MAC層。然后開始運行MAC（媒體訪問控制）協(xié)議。最終，packets被發(fā)送到網(wǎng)絡(luò)接口層(Network Interface),網(wǎng)絡(luò)接口層將packets加上正確的傳輸能量，然后將packets發(fā)送到Channel. Channel將packets進(jìn)行拷貝，并發(fā)往連接信道的每一個節(jié)點。發(fā)送過程可參考如下圖1數(shù)據(jù)包的接收過程：數(shù)據(jù)包被節(jié)點的網(wǎng)絡(luò)接口接

4、收，并被向上傳送至MAC層，Link-Layer, Connector, CMUTrace, 和Agent 函數(shù). Agent 對數(shù)據(jù)包進(jìn)行判定，并將數(shù)據(jù)包到達(dá)的信息通知給Application. 接收過程與發(fā)送過程傳輸?shù)穆窂较喾础?二、 算法設(shè)計思想Leach協(xié)議跨越幾個層次實現(xiàn)的協(xié)議，Leachapp應(yīng)用在最高層Application。它是自適應(yīng)分簇拓?fù)渌惴?。周期?zhí)行，每輪循環(huán)分為簇頭的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。（1）簇頭建立階段：初始階段，每個節(jié)點從0和1中隨機產(chǎn)生一個數(shù)，如果這個數(shù)小于閥值T（n），該節(jié)點就成為當(dāng)前輪的簇頭。 其中，P是期望的簇頭數(shù)在所有節(jié)點中占的百分比，r是選舉輪

5、數(shù)，r mod (1/p)代表這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點個數(shù)，G是這一輪循環(huán)中未當(dāng)選過簇頭的節(jié)點集合。 每個節(jié)點自主選擇是否成為當(dāng)前輪的簇頭并通過廣播的形式報告給其他節(jié)點。簇頭通過CSMA MAC協(xié)議進(jìn)行廣播，所有的簇頭以相同的傳輸能量進(jìn)行廣播。 簇頭建立起來之后，每個非簇頭節(jié)點要決定在當(dāng)前輪中自己屬于哪個簇頭。非簇頭節(jié)點根據(jù)收到的廣播信號強度決定加入哪個簇頭。非簇頭節(jié)點決定了自己屬于哪個簇頭后，必須通知簇頭節(jié)點它是該簇的成員。非簇頭節(jié)點同樣通過CSMA MAC協(xié)議將自己加入該簇的信息報告給簇頭節(jié)點。簇頭節(jié)點收到所有的非簇頭節(jié)點加入的信息后，基于本簇內(nèi)加入的節(jié)點數(shù)目創(chuàng)建TDMA調(diào)度，通知每個

6、節(jié)點什么時間可以傳輸數(shù)據(jù)。在leach協(xié)議中，具體通過calculatePi()函數(shù)計算門限值thresh.double LeachApp:calculatePi()register int n = config_.numberNodes_; /節(jié)點個數(shù)register int k = config_.desiredClusters_; /期望簇頭數(shù)double thresh; /閥值if (hasBeenClusterHead()thresh = 0; /已經(jīng)是簇頭，本輪中不再成為簇頭else if (n - k * round_ 1)thresh = 1; /將節(jié)點設(shè)置為簇頭elsethr

7、esh = (double) k / (n - k * round_);return thresh;（2）數(shù)據(jù)傳輸階段：一個簇內(nèi)的信息傳輸會影響相鄰簇。為了減少這種信號干擾，各個簇內(nèi)的信息交互通過不同的CDMA編碼。簇頭可以決定本簇中節(jié)點所用的CDMA編碼。這個用于當(dāng)前階段的CDMA編碼在廣播簇頭的時候發(fā)送給簇內(nèi)節(jié)點。具體在advertiseClusterHead()中實現(xiàn)。此外，簇頭根據(jù)本簇內(nèi)的節(jié)點個數(shù)創(chuàng)建TDMA調(diào)度。具體的，簇頭在findBestCluster()函數(shù)中調(diào)用createSchedule()，而由createSchedule()函數(shù)具體創(chuàng)建TDMA調(diào)度。當(dāng)簇內(nèi)節(jié)點收到這個消

8、息后，它們會在各自的時間槽內(nèi)發(fā)送數(shù)據(jù)。簇頭節(jié)點收到所有的數(shù)據(jù)后執(zhí)行信號處理函數(shù)壓縮數(shù)據(jù)為一個信號，并將這個合成的信號發(fā)給基站。三、簇頭建立算法流程圖 簇頭的建立是在decideClusterHead()函數(shù)實現(xiàn)。具體流程圖如 圖1 圖1 簇頭建立算法流程圖四、難點解決 1. CDMA編碼問題 Leach協(xié)議中不同簇內(nèi)用不同的CDMA編碼，同一個簇內(nèi)采用同一個CDMA編碼進(jìn)行數(shù)據(jù)傳輸。如果以各個簇頭為結(jié)點，建立完全圖。為了使各個簇采用不同的編碼，利用PCA邊著色。 所謂PCA邊著色問題，指在完全圖中給節(jié)點的每條鄰接邊分配不同的碼。每個節(jié)點用一個碼在其鄰接邊（即鏈路）上進(jìn)行發(fā)送或接收數(shù)據(jù)。 以下，

9、圖2是PCA著色問題的一個示例。 圖2 PCA邊著色示意圖如果記PCA需要的最大可用碼數(shù)為：（PCA）根據(jù)圖論知識：（PCA）=2-1 ，其中指圖中節(jié)點的最大度數(shù)例如：在圖2中，節(jié)點的最大度數(shù)為6，故為6在leach協(xié)議中，假定期望的簇頭數(shù)為n， 再加上匯聚節(jié)點，所以，節(jié)點的最大度數(shù)為（n1）。因此， （PCA）myADVnum() % numCodesAvail) + 1; /設(shè)置CDMA編碼在leachApp.cc程序中，struct leachConfig中對desiredClusters_（期望的簇頭數(shù)）和config_.spreading進(jìn)行了定義。在initializeConfig

10、()函數(shù)中語句： config_.spreading_ = config_.desiredClusters_ + 1 在LeachApp的構(gòu)造函數(shù)LeachApp(int nNodes, int nClusters, double maxDist) 中語句：config_.desiredClusters_ = nClusters 在TCL腳本中 set val(n_common) 10 /普通節(jié)點個數(shù)可任意設(shè)置，此處設(shè)為10set val(n_ch) 0 /簇頭數(shù)初始值為0 set val(n_ch) expr int($val(n_common) * 2 / 10) /對期望的簇頭數(shù)進(jìn)行了設(shè)

11、置，為普通節(jié)點個數(shù)的20（即 上式中的 2/10） 因此，可以計算得出numCodesAvail在mac-sensor.h中，int myADVnum_; / 收到的廣播消息，即鄰近的簇頭節(jié)點的個數(shù)inline int & myADVnum() return myADVnum_; myADVnum()是在MAC層中計算求得。啟動運行后，計算每個簇頭的鄰近簇頭發(fā)來的ADV。 因此，可求得clusterCode 2. TDMA調(diào)度 在findBestCluster()函數(shù)中，當(dāng)判定節(jié)點是簇頭節(jié)點時需要createScheduler。在createScheduler函數(shù)中，如果簇內(nèi)節(jié)點不空，就需要創(chuàng)

12、建TDMA時分復(fù)用幀。frameTime 表示該簇頭節(jié)點分配的一個時間幀；clusterNodes_.size() 表示一個簇內(nèi)的節(jié)點個數(shù)config_.ssSlotTime_ 表示一個時間幀內(nèi)的小的時隙lstRndDelay 表示緩沖時間xmitTime_ 表示簇內(nèi)所有節(jié)點的數(shù)據(jù)發(fā)送時間createScheduler函數(shù)主要語句如下：frameTime_ = (5 + clusterNodes_.size() * config_.ssSlotTime_; /計算時間幀lstRndDelay_ = Random:uniform(0, 0.01); /隨機選取緩沖時間xmitTime_ = co

13、nfig_.ssSlotTime_ * (clusterNodes_.size() + lstRndDelay_; Scheduler:instance().schedule(eventHandler_,new LeachEvent(&LeachApp:sendDataToBS),xmitTime_); 3. clearClusterChoices() 由于各個簇頭形成和建立起來的時間不同，而簇頭建立起來后需要廣播ADV, 通知其他節(jié)點加入。簇頭廣播的ADV會被網(wǎng)絡(luò)中的所有節(jié)點接收到，即簇頭和普通節(jié)點都能收到先建立起來的簇頭發(fā)來的ADV。普通節(jié)點收到簇頭發(fā)來的通知包后都會將該數(shù)據(jù)包加入自己的一

14、個接收隊列。對后來建立起來的簇頭來說，一旦自己成為簇頭，就會刪除其他簇頭發(fā)來的廣播包；對沒有成為簇頭的普通節(jié)點來說，需要出接收的簇頭隊列中選出一個距離最近的簇頭加入，然后刪除接收隊列中的廣播包。在decideClusterHead()函數(shù)中，當(dāng)節(jié)點成為簇頭后，需要執(zhí)行clearClusterChoices(), 函數(shù)clearClusterChoices()主要語句如下：for (CHs:iterator it = clusterChoices_.begin(); it != clusterChoices_.end(); it+)chadv element = (chadv) *it;if (

15、element.object != NULL)delete element.object;而普通節(jié)點則需要在findBestCluster()中找到最優(yōu)簇頭（即距離最近的簇頭）后，執(zhí)行clearClusterChoices()4. 一些定義 （1）virtual double TxTime(int n) return n * 8.0 / 1000000.0; TxTime指以1 Mbps的速度傳輸n bit數(shù)據(jù)所需要的時間（2） double lstRndDelay_; / 上次隨機延遲時間int currentCH_; /當(dāng)前簇頭int currentCHMAC_; /當(dāng)前簇頭所用的MAC協(xié)

16、議bool listenADV_;/ 是否收聽ADVbool listenJOINREQ_;/ 是否監(jiān)聽加入請求五、 算法運行結(jié)果分析1場景介紹 用ns模擬每個節(jié)點向基站傳輸數(shù)據(jù) Basic Configuration: 圖3 Basic Configuration配置圖Access Point: 圖4 Access Point配置圖Common Node: 圖5 Common Node配置圖輸出得到TCL文件。在ns環(huán)境下運行該TCL文件，得到trace文件。2. trace文件分析trace的功能是詳細(xì)記錄模擬的過程，可以根據(jù)用戶的需要記錄模擬過程中的任何一個細(xì)節(jié)。所有對模擬的分析是基于t

17、race文件。截取一部分文件代碼如下：s -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl AGT -Nw - -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32 r -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl RTR -Nw - -Ma 0 -Md 10000

18、00 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32 s -t 0.007580973 -Hs 1 -Hd -2 -Ni 1 -Nx 48.64 -Ny 86.26 -Nz 0.00 -Ne 10.000000 -Nl RTR -Nw - -Ma 0 -Md 1000000 -Ms 0 -Mt 0 -Is 1.0 -Id -1.0 -It rca -Il 4 -If 0 -Ii 0 -Iv 32在文件分析中主要用到t, Ni, Ne這幾個數(shù)據(jù)。其中，t 后面的數(shù)字代表時間，Ni后面的數(shù)字代表節(jié)點ID，Ne后面的數(shù)字代表

19、節(jié)點能量 使用語言gwak, 繪圖工具gnuplot. 上述場景中生成的trace文件名為：trace.tr去掉所有以N開頭的行數(shù)，該行為統(tǒng)計數(shù)據(jù)，得到文件trace1.tr (1) 單個節(jié)點能量變化統(tǒng)計：以節(jié)點1為例,提取所有Ni等于1的節(jié)點的時間和相應(yīng)能量，存入文件1.txt. 在gawk環(huán)境中，輸入代碼如下：gawk $9=/1/print $3,$17trace1.tr 1.txt得到統(tǒng)計數(shù)據(jù)如下：0.007580973 10.0000000.007580973 10.0000000.007580973 10.0000000.007605973 10.0000002.461346376

20、 9.9633632.461371376 9.9633632.461371376 9.9633633.536372973 9.9458033.536372973 9.9458033.536372973 9.9458033.536397973 9.945803在gnuplot環(huán)境中輸入：gnuplot 1.txt using 1:2得到的能量變化圖如下圖所示： 圖6 節(jié)點1能量變化圖(2) 工作節(jié)點能量統(tǒng)計： 從trace.tr文件中提取普通節(jié)點的數(shù)據(jù)。 gawk $1/N/ print $3,$5,&7 trace.tr n.txt /第3列代表時間，第5列代表節(jié)點ID，第7列代表能量值 ga

21、wk $2!=0 print $1,$3n.txt 2.txt /去掉sink節(jié)點，sink節(jié)點ID為0 再從2.txt中進(jìn)行能量統(tǒng)計，統(tǒng)計時間間隔為0.5秒 gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt gawk if($13.txt 得到 文件3.txt的統(tǒng)計數(shù)據(jù)如下： 0.5 3918.841.0 2937.012.5 1395.123.0 4700.223.5 5194.794.0 3271.124.5 1132.38 全網(wǎng)間隔時間為0.5秒

22、工作節(jié)點能量變化圖： 圖7 工作節(jié)點能量變化圖3全網(wǎng)所有節(jié)點能量和變化統(tǒng)計在gawk環(huán)境下輸入：gawk $9!=0 print $3,$9,$17trace1.tr 4.txt /提取普通節(jié)點的時間，ID，能量將以下程序?qū)懭胛募?.awkBEGIN FS= unit=0.5; ftime=0; time=0; for(i=1;i=50;i+) ei=10.0; sum+=ei; printf %f ,%fn,time,sum; time+=unit; if(ftime$1 &$1time ) k=$2; ek=$3; END sum=0 for(i=1;i5.txt 在5.txt文件中得到的

23、是0到0.5秒之間全網(wǎng)的總能量。 再不斷地將每個時間間隔為0.5秒的數(shù)據(jù)寫入文件5.txt（只需在文件5.txt 中不斷追加統(tǒng)計數(shù)據(jù)）。最后可以得到0到4.5秒之間全網(wǎng)在每0.5秒的時間間隔內(nèi)的總能量。 最后得到的5.txt統(tǒng)計數(shù)據(jù)如下： 0.000000 ,500.0000000.500000,499.7572171.000000,499.5048001.500000,499.5048002.000000,499.5048002.500000,499.1727333.000000,498.4367983.500000,497.8758164.000000,497.5257304.500000,496.948944在gnuplot環(huán)境下，輸入命令：gnuplot 5.txt using 1:2 with lp最后得到的全網(wǎng)能量變化情況如下圖所示： 圖8 全網(wǎng)能量統(tǒng)計圖4. 生成的簇頭和簇內(nèi)節(jié)點統(tǒng)計 設(shè)置普通節(jié)點個數(shù)50，AP節(jié)點1個，仿真時間10秒，普通節(jié)點位置隨機產(chǎn)生。生成TCL文件，運行該TCL文件將結(jié)果輸出到2.tr文件中。 在gawk環(huán)境中，輸入下列命令： gawk ($1=”O(jiān)n”)&($7=”at”)print $0 2.tr 3.tr gawk BEGIN FS=” “; print $10,$11,$12,