WSN協(xié)議matlab編程教程-無線傳感器網(wǎng)絡(luò)路由協(xié)議

ID:288219 · 發(fā)表于 2018-3-6 15:16

一、Leach協(xié)議與NS的關(guān)系

二、算法設(shè)計思想

三、簇頭建立算法流程圖

四、難點解決

五、算法運行結(jié)果分析

參考文獻

一、Leach協(xié)議與NS的關(guān)系

為了實現(xiàn)leach 協(xié)議，對ns進行擴展。在ns中增加了一個事件驅(qū)動模擬器支持模擬無線傳感器網(wǎng)絡(luò)協(xié)議。這些擴展包括MAC協(xié)議，用于計算和交互的能量分配模型和leach協(xié)議的體系結(jié)構(gòu)。

網(wǎng)絡(luò)拓撲結(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é)點。Applications用來產(chǎn)生數(shù)據(jù)和實現(xiàn)不同的應(yīng)用函數(shù)。一旦網(wǎng)絡(luò)拓撲結(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 文件，然后將packets發(fā)至Connector。Connector將數(shù)據(jù)包傳送給用于數(shù)據(jù)鏈路處理的鏈路層(LL).經(jīng)過一小段時間的延遲后，數(shù)據(jù)包由LL發(fā)送給Queue緩沖隊列。如果是還沒有傳送過的數(shù)據(jù)包，Queue將以隊列進行存儲。然后Queue將數(shù)據(jù)包出隊列，發(fā)送到MAC層。然后開始運行MAC（媒體訪問控制）協(xié)議。最終，packets被發(fā)送到網(wǎng)絡(luò)接口層(Network Interface),網(wǎng)絡(luò)接口層將packets加上正確的傳輸能量，然后將packets發(fā)送到Channel. Channel將packets進行拷貝，并發(fā)往連接信道的每一個節(jié)點。

發(fā)送過程可參考如下圖1

數(shù)據(jù)包的接收過程：

數(shù)據(jù)包被節(jié)點的網(wǎng)絡(luò)接口接收，并被向上傳送至MAC層，Link-Layer, Connector, CMUTrace, 和Agent 函數(shù). Agent 對數(shù)據(jù)包進行判定，并將數(shù)據(jù)包到達的信息通知給Application.

接收過程與發(fā)送過程傳輸?shù)穆窂较喾础?/font>

二、算法設(shè)計思想

Leach協(xié)議跨越幾個層次實現(xiàn)的協(xié)議，Leachapp應(yīng)用在最高層Application。它是自適應(yīng)分簇拓撲算法。周期執(zhí)行，每輪循環(huán)分為簇頭的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。

（1）簇頭建立階段：初始階段，每個節(jié)點從0和1中隨機產(chǎn)生一個數(shù)，如果這個數(shù)小于閥值T（n），該節(jié)點就成為當(dāng)前輪的簇頭。

其中，P是期望的簇頭數(shù)在所有節(jié)點中占的百分比，r是選舉輪數(shù)，r mod (1/p)代表這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點個數(shù)，G是這一輪循環(huán)中未當(dāng)選過簇頭的節(jié)點集合。

每個節(jié)點自主選擇是否成為當(dāng)前輪的簇頭并通過廣播的形式報告給其他節(jié)點。簇頭通過CSMA MAC協(xié)議進行廣播，所有的簇頭以相同的傳輸能量進行廣播。

簇頭建立起來之后，每個非簇頭節(jié)點要決定在當(dāng)前輪中自己屬于哪個簇頭。非簇頭節(jié)點根據(jù)收到的廣播信號強度決定加入哪個簇頭。非簇頭節(jié)點決定了自己屬于哪個簇頭后，必須通知簇頭節(jié)點它是該簇的成員。非簇頭節(jié)點同樣通過CSMA MAC協(xié)議將自己加入該簇的信息報告給簇頭節(jié)點。

簇頭節(jié)點收到所有的非簇頭節(jié)點加入的信息后，基于本簇內(nèi)加入的節(jié)點數(shù)目創(chuàng)建TDMA調(diào)度，通知每個節(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è)置為簇頭

else

thresh = (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é)點收到這個消息后，它們會在各自的時間槽內(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編碼進行數(shù)據(jù)傳輸。如果以各個簇頭為結(jié)點，建立完全圖。為了使各個簇采用不同的編碼，利用PCA邊著色。

所謂PCA邊著色問題，指在完全圖中給節(jié)點的每條鄰接邊分配不同的碼。每個節(jié)點用一個碼在其鄰接邊（即鏈路）上進行發(fā)送或接收數(shù)據(jù)。

以下，圖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ù)⊿為（n＋1）。因此，

＃（PCA）<=2(n＋1)－1=2n+1

在leachApp.cc程序中，簇頭建立后，簇頭決定本簇內(nèi)的CDMA編碼。這是在廣播簇頭時確定的，即advertiseClusterHead()函數(shù)中。

numCodesAvail = 2 * config_.spreading_ - 1; //計算最大可用碼

clusterCode = (mac_->myADVnum() % numCodesAvail) + 1; //設(shè)置CDMA編碼

在leachApp.cc程序中，struct leachConfig中對desiredClusters_（期望的簇頭數(shù)）和config_.spreading進行了定義。

在initializeConfig()函數(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è)為10

set val(n_ch) 0 //簇頭數(shù)初始值為0

set val(n_ch) [expr int($val(n_common) * 2 / 10)] //對期望的簇頭數(shù)進行了設(shè)置，為普通節(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)建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_ = config_.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ù)包加入自己的一個接收隊列。對后來建立起來的簇頭來說，一旦自己成為簇頭，就會刪除其他簇頭發(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 (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é)議

bool listenADV_; // 是否收聽ADV

bool 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的功能是詳細記錄模擬的過程，可以根據(jù)用戶的需要記錄模擬過程中的任何一個細節(jié)。所有對模擬的分析是基于trace文件。截取一部分文件代碼如下：

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 1000000 -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ù)字代表節(jié)點能量

使用語言gwak, 繪圖工具gnuplot. 上述場景中生成的trace文件名為：trace.tr

去掉所有以N開頭的行數(shù)，該行為統(tǒng)計數(shù)據(jù)，得到文件trace1.tr

單個節(jié)點能量變化統(tǒng)計：

以節(jié)點1為例,提取所有Ni等于1的節(jié)點的時間和相應(yīng)能量，存入文件1.txt.

在gawk環(huán)境中，輸入代碼如下：

gawk ‘$9==/1/{print $3,$17}’trace1.tr >1.txt

得到統(tǒng)計數(shù)據(jù)如下：

0.007580973 10.000000

0.007605973 10.000000

2.461346376 9.963363

2.461371376 9.963363

3.536372973 9.945803

3.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列代表能量值

gawk ‘$2!=0 { print $1,$3}’n.txt >2.txt //去掉sink節(jié)點，sink節(jié)點ID為0

再從2.txt中進行能量統(tǒng)計，統(tǒng)計時間間隔為0.5秒

gawk ‘{ if($1<0.5) sum+=$2 };

END { print sum }’ 2.txt >3.txt

gawk ‘{ if($1<1.0) sum+=$2 };