WSN協議matlab編程教程-無線傳感器網絡路由協議

ID:288219 · 發表于 2018-3-6 15:16

一、Leach協議與NS的關系

二、算法設計思想

三、簇頭建立算法流程圖

四、難點解決

五、算法運行結果分析

參考文獻

一、Leach協議與NS的關系

為了實現leach 協議，對ns進行擴展。在ns中增加了一個事件驅動模擬器支持模擬無線傳感器網絡協議。這些擴展包括MAC協議，用于計算和交互的能量分配模型和leach協議的體系結構。

網絡拓撲結構可以通過簡單的Nodes, Links, Agents和Applications 描述。Nodes相當于網絡中的終端主機， Links 是用于Nodes交互的連接器, Agent用來實現不同網絡協議，是支持分組產生和丟棄的節點。Applications用來產生數據和實現不同的應用函數。一旦網絡拓撲結構建立起來后，模擬通過啟動節點上的Applications運行。

為了在ns中支持無線傳感器網絡，在ns中增加了 mobile nodes, MAC協議和信道傳播模型Channel 。

Applications類的頭文件用Tcl語言寫的，節點中的其他函數功能用C++語言寫成的。

數據包的發送過程：

Applications創建數據包（data packets）,然后發送給Agent. Agent執行協議棧中運輸層和網絡層的功能，將數據包發送給CMUTrace,。CMUTrace將packets的統計數據寫到trace 文件，然后將packets發至Connector。Connector將數據包傳送給用于數據鏈路處理的鏈路層(LL).經過一小段時間的延遲后，數據包由LL發送給Queue緩沖隊列。如果是還沒有傳送過的數據包，Queue將以隊列進行存儲。然后Queue將數據包出隊列，發送到MAC層。然后開始運行MAC（媒體訪問控制）協議。最終，packets被發送到網絡接口層(Network Interface),網絡接口層將packets加上正確的傳輸能量，然后將packets發送到Channel. Channel將packets進行拷貝，并發往連接信道的每一個節點。

發送過程可參考如下圖1

數據包的接收過程：

數據包被節點的網絡接口接收，并被向上傳送至MAC層，Link-Layer, Connector, CMUTrace, 和Agent 函數. Agent 對數據包進行判定，并將數據包到達的信息通知給Application.

接收過程與發送過程傳輸的路徑相反。

二、算法設計思想

Leach協議跨越幾個層次實現的協議，Leachapp應用在最高層Application。它是自適應分簇拓撲算法。周期執行，每輪循環分為簇頭的建立階段和穩定的數據通信階段。

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

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

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

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

簇頭節點收到所有的非簇頭節點加入的信息后，基于本簇內加入的節點數目創建TDMA調度，通知每個節點什么時間可以傳輸數據。

在leach協議中，具體通過calculatePi()函數計算門限值thresh.

double LeachApp::calculatePi()

{

register int n = config_.numberNodes_; //節點個數

register int k = config_.desiredClusters_; //期望簇頭數

double thresh; //閥值

if (hasBeenClusterHead())

thresh = 0; //已經是簇頭，本輪中不再成為簇頭

else if (n - k * round_ < 1)

thresh = 1; //將節點設置為簇頭

else

thresh = (double) k / (n - k * round_);

return thresh;

}

（2）數據傳輸階段：

一個簇內的信息傳輸會影響相鄰簇。為了減少這種信號干擾，各個簇內的信息交互通過不同的CDMA編碼。簇頭可以決定本簇中節點所用的CDMA編碼。這個用于當前階段的CDMA編碼在廣播簇頭的時候發送給簇內節點。具體在advertiseClusterHead()中實現。

此外，簇頭根據本簇內的節點個數創建TDMA調度。具體的，簇頭在findBestCluster()函數中調用createSchedule()，而由createSchedule()函數具體創建TDMA調度。

當簇內節點收到這個消息后，它們會在各自的時間槽內發送數據。簇頭節點收到所有的數據后執行信號處理函數壓縮數據為一個信號，并將這個合成的信號發給基站。

三、簇頭建立算法流程圖

簇頭的建立是在decideClusterHead()函數實現。具體流程圖如圖1

圖1 簇頭建立算法流程圖

四、難點解決

1. CDMA編碼問題

Leach協議中不同簇內用不同的CDMA編碼，同一個簇內采用同一個CDMA編碼進行數據傳輸。如果以各個簇頭為結點，建立完全圖。為了使各個簇采用不同的編碼，利用PCA邊著色。

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

以下，圖2是PCA著色問題的一個示例。

圖2 PCA邊著色示意圖

如果記PCA需要的最大可用碼數為：＃（PCA）

根據圖論知識：

＃（PCA）<=2⊿-1 ，其中⊿指圖中節點的最大度數

例如：在圖2中，節點的最大度數為6，故⊿為6

在leach協議中，假定期望的簇頭數為n，再加上匯聚節點，所以，節點的最大度數⊿為（n＋1）。因此，

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

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

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

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

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

在initializeConfig()函數中語句：

config_.spreading_ = config_.desiredClusters_ + 1

在LeachApp的構造函數LeachApp(int nNodes, int nClusters, double maxDist) 中語句：config_.desiredClusters_ = nClusters

在TCL腳本中

set val(n_common) 10 //普通節點個數可任意設置，此處設為10

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

set val(n_ch) [expr int($val(n_common) * 2 / 10)] //對期望的簇頭數進行了設置，為普通節點個數的20％（即上式中的 2/10）

因此，可以計算得出numCodesAvail

在mac-sensor.h中，

int myADVnum_; // 收到的廣播消息，即鄰近的簇頭節點的個數

inline int & myADVnum() { return myADVnum_; }

myADVnum()是在MAC層中計算求得。啟動運行后，計算每個簇頭的鄰近簇頭發來的ADV。

因此，可求得clusterCode

2. TDMA調度

在findBestCluster()函數中，當判定節點是簇頭節點時需要createScheduler。在createScheduler函數中，如果簇內節點不空，就需要創建TDMA時分復用幀。

frameTime 表示該簇頭節點分配的一個時間幀；

clusterNodes_.size() 表示一個簇內的節點個數

config_.ssSlotTime_ 表示一個時間幀內的小的時隙

lstRndDelay 表示緩沖時間

xmitTime_ 表示簇內所有節點的數據發送時間

createScheduler函數主要語句如下：

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, 通知其他節點加入。簇頭廣播的ADV會被網絡中的所有節點接收到，即簇頭和普通節點都能收到先建立起來的簇頭發來的ADV。普通節點收到簇頭發來的通知包后都會將該數據包加入自己的一個接收隊列。對后來建立起來的簇頭來說，一旦自己成為簇頭，就會刪除其他簇頭發來的廣播包；對沒有成為簇頭的普通節點來說，需要出接收的簇頭隊列中選出一個距離最近的簇頭加入，然后刪除接收隊列中的廣播包。

在decideClusterHead()函數中，當節點成為簇頭后，需要執行clearClusterChoices(), 函數clearClusterChoices()主要語句如下：

for (CHs::iterator it = clusterChoices_.begin(); it != clusterChoices_.end(); it++)

{

chadv element = (chadv) *it;

if (element.object != NULL)

delete element.object;

}

而普通節點則需要在findBestCluster()中找到最優簇頭（即距離最近的簇頭）后，執行clearClusterChoices()

4. 一些定義

（1）virtual double TxTime(int n) { return n * 8.0 / 1000000.0; }

TxTime指以1 Mbps的速度傳輸n bit數據所需要的時間

（2） double lstRndDelay_; // 上次隨機延遲時間

int currentCH_; //當前簇頭

int currentCHMAC_; //當前簇頭所用的MAC協議

bool listenADV_; // 是否收聽ADV

bool listenJOINREQ_; // 是否監聽加入請求

五、算法運行結果分析

1．場景介紹

用ns模擬每個節點向基站傳輸數據

Basic Configuration:

圖3 Basic Configuration配置圖

Access Point:

圖4 Access Point配置圖

Common Node:

圖5 Common Node配置圖

輸出得到TCL文件。在ns環境下運行該TCL文件，得到trace文件。

2. trace 文件分析

trace的功能是詳細記錄模擬的過程，可以根據用戶的需要記錄模擬過程中的任何一個細節。所有對模擬的分析是基于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這幾個數據。其中，t 后面的數字代表時間，Ni后面的數字代表節點ID，Ne后面的數字代表節點能量

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

去掉所有以N開頭的行數，該行為統計數據，得到文件trace1.tr

單個節點能量變化統計：

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

在gawk環境中，輸入代碼如下：

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

得到統計數據如下：

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環境中輸入：

gnuplot ‘1.txt’ using 1:2

得到的能量變化圖如下圖所示：

圖6 節點1能量變化圖

(2) 工作節點能量統計：

從trace.tr文件中提取普通節點的數據。

gawk ‘$1~/N/ { print $3,$5,&7 }’ trace.tr >n.txt //第3列代表時間，第5列代表節點ID，第7列代表能量值

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

再從2.txt中進行能量統計，統計時間間隔為0.5秒

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

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

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