WSN中基于帆布協(xié)議的覆蓋問(wèn)題與路由算法研究.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量低成本的受資源約束的傳感器節(jié)點(diǎn)所構(gòu)成的網(wǎng)絡(luò)，這些節(jié)點(diǎn)間相互協(xié)作，從而實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)覆蓋區(qū)域的監(jiān)控。各個(gè)節(jié)點(diǎn)所感知到的信息會(huì)被傳回基站以供進(jìn)一步的分析。然而，如果網(wǎng)絡(luò)中存在故障節(jié)點(diǎn)，那么整個(gè)網(wǎng)絡(luò)的性能都會(huì)受到影響；如果敵方捕獲了網(wǎng)絡(luò)中的節(jié)點(diǎn)或者在網(wǎng)絡(luò)中部署惡意的節(jié)點(diǎn)使其轉(zhuǎn)發(fā)偽造的信息，那么這種情況將會(huì)造成更為嚴(yán)重的后果。因?yàn)橄鄬?duì)故障節(jié)點(diǎn)來(lái)說(shuō)，這些惡意偽裝的節(jié)點(diǎn)將會(huì)

2、更難被識(shí)別出來(lái)。
　　對(duì)安全協(xié)議的設(shè)計(jì)被認(rèn)為是WSN研究領(lǐng)域中的一個(gè)難點(diǎn)，近些年，學(xué)者們圍繞這一課題展開(kāi)了深入的研究。其中，Vogt等人基于多重相交認(rèn)證鏈的思想提出了帆布協(xié)議以及對(duì)它的改進(jìn)協(xié)議——k-廣義帆布協(xié)議。在k-廣義帆布協(xié)議中，只要傳輸路徑的任意k個(gè)連續(xù)節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)沒(méi)有被捕獲，就能保證該路徑上數(shù)據(jù)傳輸?shù)陌踩浴?br>　　考慮到k-廣義帆布協(xié)議的應(yīng)用前提，我們可以在初始化網(wǎng)絡(luò)時(shí)就找出一些傳感器節(jié)點(diǎn)使之成為受保護(hù)節(jié)點(diǎn)

3、，以保證網(wǎng)絡(luò)中每條長(zhǎng)度為k-1的傳輸路徑上至少有一個(gè)節(jié)點(diǎn)受到保護(hù)。針對(duì)這個(gè)問(wèn)題，本文提出了最小k-路徑連通頂點(diǎn)覆蓋的近似構(gòu)造算法。通過(guò)該算法，我們可以找出已知網(wǎng)絡(luò)中的受保護(hù)節(jié)點(diǎn)的集合，而且可以盡可能地減小集合以節(jié)省成本。
　　然而，一方面，WSN通常是一個(gè)較為稠密的無(wú)線網(wǎng)絡(luò)，其k-路徑連通頂點(diǎn)覆蓋往往很大，使得這個(gè)集合中的所有節(jié)點(diǎn)均受到保護(hù)的成本很高；另一方面，WSN是一個(gè)動(dòng)態(tài)的網(wǎng)絡(luò)，事先知道網(wǎng)絡(luò)的全局信息并在已知網(wǎng)絡(luò)中找出節(jié)點(diǎn)集