圖的連通度、強(qiáng)定向及無(wú)線傳感器網(wǎng)絡(luò).pdf

1、圖論是一門(mén)富有趣味性和應(yīng)用極為廣泛的學(xué)科，它在化學(xué)、生物學(xué)、計(jì)算科學(xué)以及通信網(wǎng)絡(luò)等方面都有廣泛的應(yīng)用．本文主要研究圖的強(qiáng)定向和最優(yōu)強(qiáng)(κ，d)定向以及圖論在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用等課題。 無(wú)線傳感器網(wǎng)絡(luò)(WSN)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的微型傳感器節(jié)點(diǎn)通過(guò)無(wú)線電通信形成的一個(gè)網(wǎng)絡(luò)系統(tǒng)．傳感器節(jié)點(diǎn)由傳感單元、處理單元、無(wú)線收發(fā)單元和電源單元等幾部分組成。無(wú)線傳感器網(wǎng)絡(luò)的出現(xiàn)引起了全世界廣泛關(guān)注，其應(yīng)用已經(jīng)由軍事國(guó)防領(lǐng)域擴(kuò)展到環(huán)境監(jiān)

2、測(cè)、交通管理、醫(yī)療健康、工商服務(wù)和反恐抗災(zāi)等諸多領(lǐng)域． 在無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的能量通常是電池。由于網(wǎng)絡(luò)成本及環(huán)境因素，這些電池能量耗盡后，就無(wú)法再充電或更換電池而繼續(xù)使用。因此，在保證網(wǎng)絡(luò)覆蓋以及網(wǎng)絡(luò)暢通的基礎(chǔ)上，如何延長(zhǎng)網(wǎng)絡(luò)的工作時(shí)間，是目前無(wú)線傳感器網(wǎng)絡(luò)研究的一個(gè)重要方面。 在本文中，我們提出了一種新型的無(wú)線傳感器網(wǎng)絡(luò)。在此網(wǎng)絡(luò)中，假設(shè)已知所有監(jiān)控的離散目標(biāo)的具體位置，并在每個(gè)目標(biāo)周?chē)渴鸫罅康膫鞲衅鞴?jié)點(diǎn)，

3、而后將節(jié)點(diǎn)所監(jiān)測(cè)到的信息傳輸給一個(gè)或多個(gè)信息中心。將所有的傳感器節(jié)點(diǎn)分成最大數(shù)量的不相交的傳感器節(jié)點(diǎn)的集合，其中每個(gè)集合所包含的傳感器節(jié)點(diǎn)能完全覆蓋所有目標(biāo)，并且將監(jiān)測(cè)到的信息有效地傳輸給信息中心。然后將這些集合所包含的傳感器節(jié)點(diǎn)依次激活。使得在任何時(shí)刻，都恰好只有處于活躍狀態(tài)的節(jié)點(diǎn)負(fù)責(zé)監(jiān)控與信息傳輸，而其余節(jié)點(diǎn)能量耗盡或處于睡眠狀態(tài)。這種方法是延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)工作時(shí)間的一種較有效的方式．因此，我們的目標(biāo)就是找出最大數(shù)量的不相交的傳感

4、器節(jié)點(diǎn)集合． 將無(wú)線傳感器網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)看成圖G的一個(gè)頂點(diǎn)，并且uv∈E(G)當(dāng)且僅當(dāng)u和v對(duì)應(yīng)的傳感器節(jié)點(diǎn)在彼此的傳感范圍之內(nèi)．通常稱G為網(wǎng)絡(luò)圖．我們考慮此類(lèi)型無(wú)線傳感器網(wǎng)絡(luò)的三種不同的模型． 1．假設(shè)無(wú)線傳感器網(wǎng)絡(luò)的每個(gè)傳感器節(jié)點(diǎn)恰好只監(jiān)控一個(gè)目標(biāo)。設(shè) t1，t2，．．．，t1分別為l個(gè)需要監(jiān)控的目標(biāo)，A1，A2，．．．，Al為圖G的頂點(diǎn)子集，其中若頂點(diǎn)v所對(duì)應(yīng)的傳感器節(jié)點(diǎn)監(jiān)控目標(biāo)ti，則v∈Ai，從而Ai∩Aj=φ

5、，1≤i＜j≤l．在這個(gè)模型下，我們將無(wú)線傳感器網(wǎng)絡(luò)的覆蓋與能量有效性問(wèn)題歸結(jié)為圖的不交集合覆蓋與連通問(wèn)題(DSCC—problem)。 我們證明該問(wèn)題是NP完全的，進(jìn)而給出一個(gè)相關(guān)的近似算法。最后，我們給出該近似算法的理論分析及實(shí)驗(yàn)估計(jì)。 2．有時(shí)兩個(gè)需監(jiān)測(cè)的目標(biāo)之間或目標(biāo)與信息中心之間的距離較遠(yuǎn)，為了保證網(wǎng)絡(luò)的暢通，需要部署一些只負(fù)責(zé)信息傳輸?shù)膫鞲衅鞴?jié)點(diǎn)。在此模型中，假設(shè)無(wú)線傳感器網(wǎng)絡(luò)的某些傳感器節(jié)點(diǎn)同時(shí)負(fù)責(zé)監(jiān)控與信

6、息傳輸，其余的傳感器節(jié)點(diǎn)只負(fù)責(zé)信息傳輸． 在網(wǎng)絡(luò)圖G中，稱信息中心節(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)為中心頂點(diǎn)。假定無(wú)線傳感器網(wǎng)絡(luò)有l(wèi)個(gè)離散的監(jiān)控目標(biāo)，每個(gè)目標(biāo)可同時(shí)處于k個(gè)傳感器節(jié)點(diǎn)的監(jiān)控范圍之內(nèi)。設(shè)Ai為G中對(duì)應(yīng)于監(jiān)控第i個(gè)目標(biāo)的傳感器節(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)的集合，其中1≤i≤l；設(shè)S為G的中心頂點(diǎn)集合，那么Ai∩S=φ和Ai∩Aj=φ，其中1≤i≠j≤l．G的包含S的一個(gè)頂點(diǎn)以及每個(gè)Ai的一個(gè)頂點(diǎn)的連通子圖，對(duì)應(yīng)于無(wú)線傳感器網(wǎng)絡(luò)中監(jiān)控所有目標(biāo)，并

7、且將監(jiān)測(cè)到的信息傳輸給至少一個(gè)信息中心的節(jié)點(diǎn)的集合。因此，無(wú)線傳感器網(wǎng)絡(luò)的最大數(shù)量的不相交的傳感器節(jié)點(diǎn)集合的數(shù)目，就是G中最大數(shù)量的這樣的連通子圖的數(shù)目。進(jìn)一步地，包含多個(gè)信息中心節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)的覆蓋與能量有效性問(wèn)題可歸化為只包含一個(gè)信息中心節(jié)點(diǎn)的覆蓋與能量有效性問(wèn)題。因此，我們假設(shè)網(wǎng)絡(luò)圖G只有一個(gè)中心頂點(diǎn)s。我們找到圖的一個(gè)參數(shù)—連通度來(lái)達(dá)到無(wú)線傳感器網(wǎng)絡(luò)的覆蓋與能量有效性． 由定理1，如果k=2，并且無(wú)線傳感器網(wǎng)絡(luò)所對(duì)

8、應(yīng)的網(wǎng)絡(luò)圖G是l+max{1，l—4}連通的，或者k≥3和G是l(k—1)+1連通的，那么可以找到k個(gè)(最大數(shù)量)傳感器節(jié)點(diǎn)的不相交的集合，其中每個(gè)集合所包含的傳感器節(jié)點(diǎn)完全覆蓋所有目標(biāo)，并且將監(jiān)測(cè)到的信息有效地傳輸給信息中心，也就是可使無(wú)線傳感器網(wǎng)絡(luò)的工作時(shí)間提高k倍。同時(shí)，我們還證明了連通度條件l(k—1)+1連通是緊的，并且我們猜想當(dāng)k=2時(shí)，l+1連通是足夠的。 最后，我們也給出了相應(yīng)的算法來(lái)找出這k個(gè)傳感器節(jié)點(diǎn)的集合．

9、 3．通常情況下，同時(shí)負(fù)責(zé)信息傳輸與監(jiān)控的傳感器節(jié)點(diǎn)的能量消耗比只負(fù)責(zé)信息傳輸?shù)膫鞲衅鞴?jié)點(diǎn)的能量消耗來(lái)得快些．在模型2的基礎(chǔ)上，假設(shè)那些只負(fù)責(zé)信息傳輸?shù)膫鞲衅鞴?jié)點(diǎn)的工作時(shí)間，是那些同時(shí)負(fù)責(zé)監(jiān)控與信息傳輸?shù)墓?jié)點(diǎn)的工作時(shí)間的d倍。設(shè)同時(shí)負(fù)責(zé)信息傳輸與監(jiān)控的傳感器節(jié)點(diǎn)的工作時(shí)間為一單位時(shí)間。 同模型1與2一樣的考慮，我們將全部傳感器節(jié)點(diǎn)劃分為多個(gè)集合，使得每個(gè)節(jié)點(diǎn)的集合既能監(jiān)控所有目標(biāo)，又能保證將監(jiān)測(cè)到的全部信息傳輸給信息中心

10、。但是，某個(gè)只負(fù)責(zé)信息傳輸?shù)膫鞲衅鞴?jié)點(diǎn)可能會(huì)同屬于兩個(gè)或多個(gè)不同的傳感器節(jié)點(diǎn)的集合。而且由于環(huán)境因素及成本考慮，在每個(gè)傳感器節(jié)點(diǎn)上安裝開(kāi)關(guān)是不太可能實(shí)現(xiàn)的。因此，我們假設(shè)每個(gè)傳感器節(jié)點(diǎn)一旦被激活就不能被關(guān)閉，直到能量耗盡。從而，那些含有共同傳感器節(jié)點(diǎn)的任意兩個(gè)集合，它們所含的傳感器節(jié)點(diǎn)被激活的時(shí)間間隔不能超過(guò)d個(gè)單位時(shí)間。特別的，如果一個(gè)節(jié)點(diǎn)已被激活，若它還屬于另一個(gè)即將被激活的節(jié)點(diǎn)集合，則該傳感器節(jié)點(diǎn)無(wú)需再次激活。我們的目標(biāo)就是尋找最

11、大數(shù)量的有序的節(jié)點(diǎn)的集合，使得每個(gè)集合所含的傳感器節(jié)點(diǎn)的傳感范圍能完全覆蓋所有目標(biāo)，并保證將監(jiān)測(cè)到的全部信息傳輸給信息中心，而且對(duì)于任兩個(gè)含有共同傳感器節(jié)點(diǎn)的集合，它們的序號(hào)之差不能超過(guò)d。對(duì)應(yīng)于網(wǎng)絡(luò)圖G，我們的目標(biāo)就是尋找最大數(shù)量的包含點(diǎn)s且包含每個(gè)Ai的頂點(diǎn)的有序連通子圖G1，G2，…，Gp，使得任意兩個(gè)子圖Gi和Gj，如果它們包含除s外的共同頂點(diǎn)，那么｜i—j｜≤d-1．我們證明了，即使無(wú)線傳感器網(wǎng)絡(luò)所對(duì)應(yīng)的網(wǎng)絡(luò)圖滿足一定的連通度

12、的條件，要找出無(wú)線傳感器網(wǎng)絡(luò)的最優(yōu)工作時(shí)間仍是NP完全的。我們給出一個(gè)近似算法來(lái)提高無(wú)線傳感器網(wǎng)絡(luò)的工作時(shí)間，并且給出該算法的理論分析與實(shí)驗(yàn)估計(jì)．眾所周知，在交通系統(tǒng)中應(yīng)用單行道，不僅會(huì)減少交通事故，而且可以簡(jiǎn)化交通控制管理。單行道問(wèn)題的圖論模型最初是由Rabbins[51]引入的。單行道問(wèn)題是一個(gè)關(guān)于圖的定向的問(wèn)題。目前已有很多結(jié)果[2，14，24，34，52，53，54，55]基于不同的指標(biāo)來(lái)研究與單行道問(wèn)題相關(guān)的圖的定向．Char

13、trand等人[9]引入了強(qiáng)有向圖和強(qiáng)定向圖的強(qiáng)距離、強(qiáng)半(直)徑的新概念，它們成為圖的定向的新的重要指標(biāo)。設(shè)u和v是強(qiáng)定向圖D的兩個(gè)頂點(diǎn)，D中包含u和v的最小強(qiáng)有向子圖的弧數(shù)稱為u和v的強(qiáng)距離sdD(u，v)。D的任一頂點(diǎn)v的強(qiáng)離心率se(v)為v與D中其它所有頂點(diǎn)的強(qiáng)距離的最大值。D的強(qiáng)半徑srad(D)(強(qiáng)直徑sdiam(D))為D中所有頂點(diǎn)的強(qiáng)離心率的最小值(最大值)。對(duì)于無(wú)向圖，Lai等人[36]給出了圖的最小(大)強(qiáng)半徑及最

14、小(大)強(qiáng)直徑的定義。設(shè)G是一個(gè)連通圖。G的最小強(qiáng)半徑srad(G)(最大強(qiáng)半徑SRAD(G))為G的所有強(qiáng)定向圖的強(qiáng)半徑的最小值(最大值)。類(lèi)似地，G的最小強(qiáng)直徑sdiam(G)(最大強(qiáng)直徑SDIAM(G))為G的所有強(qiáng)定向圖的強(qiáng)直徑的最小值(最大值)。對(duì)于圖G的任一強(qiáng)定向圖D，都有k(D)≤[k(G)/2]和sdiam(D)≥sdiam(G)成立，其中k(D)(K(G))為D的強(qiáng)連通度(G的連通度)。通常，并不足所有的強(qiáng)定向圖能同時(shí)

15、滿足兩個(gè)等號(hào)。我們將同時(shí)使兩個(gè)等號(hào)成立的定向稱為圖G的一個(gè)最優(yōu)強(qiáng)(k，d)定向。 本文基于強(qiáng)距離、強(qiáng)半(直)徑、強(qiáng)連通度等指標(biāo)，研究特殊圖類(lèi)的強(qiáng)定向問(wèn)題，得到以下結(jié)果。 1．設(shè)K(m1，m2，．．．，mk)為完全k部圖，其中m1，m2，．．．，mk分別為其頂點(diǎn)集的k部劃分的子集的基數(shù)．我們研究了完全k部圖的強(qiáng)定向圖的強(qiáng)半徑與強(qiáng)直徑的一些性質(zhì)． 2．我們研究了完全k部圖的最小(大)強(qiáng)半徑及最小(大)強(qiáng)直徑。給出了完