網(wǎng)絡(luò)相關(guān)數(shù)據(jù)收集算法.pdf

1、數(shù)據(jù)收集是指一個(gè)傳感器網(wǎng)絡(luò)中，傳感器采集環(huán)境中的相關(guān)數(shù)據(jù)，進(jìn)行簡單處理后，傳輸回網(wǎng)絡(luò)基站的過程。數(shù)據(jù)收集是傳感網(wǎng)絡(luò)的基礎(chǔ)功能。實(shí)際上，網(wǎng)絡(luò)的大多數(shù)應(yīng)用依賴于其數(shù)據(jù)收集的效率，所以數(shù)據(jù)收集的效率嚴(yán)重影響到整個(gè)傳感器網(wǎng)絡(luò)的運(yùn)行效率。
　　 本文在分析數(shù)據(jù)傳輸模型的基礎(chǔ)上，將原始問題簡化為圖的模型。我們用頂點(diǎn)來表示網(wǎng)絡(luò)中的傳感器和基站。兩個(gè)頂點(diǎn)用邊相連，表示兩個(gè)傳感器可以互相傳輸數(shù)據(jù)。結(jié)合通信模型，規(guī)定任意傳感器在一個(gè)時(shí)刻只能發(fā)送或者

2、接收一個(gè)數(shù)據(jù)。當(dāng)任意頂點(diǎn)處于發(fā)送（接收）數(shù)據(jù)狀態(tài)時(shí)，相鄰的頂點(diǎn)只有一個(gè)處于接收（發(fā)送）數(shù)據(jù)狀態(tài)。
　　 我們對圈和網(wǎng)格圖上的總傳輸時(shí)間和其傳感器數(shù)據(jù)的傳輸部署進(jìn)行了研究。通過斷點(diǎn)式部署的方式，把圈上的數(shù)據(jù)部署問題轉(zhuǎn)化為雙線性結(jié)構(gòu)的傳輸部署問題。給出了O(n2)時(shí)間內(nèi)得到偶圈上最優(yōu)部署的算法。在引入數(shù)據(jù)延遲傳輸?shù)南敕ê?，對只有一個(gè)傳感器有數(shù)據(jù)的奇圈問題給出了較優(yōu)的解決方案，并對一般的圈網(wǎng)絡(luò)的部署給出了一種較優(yōu)的算法。對網(wǎng)格網(wǎng)絡(luò)，我