周志誠，李翠靜

(北京郵電大學，北京 海淀 100876)

無向圓盤圖中最大r跳獨立鄰居數(shù)的估計

周志誠1，李翠靜1

(北京郵電大學，北京 海淀 100876)

本文考慮無向圓盤圖中的最大r-跳獨立鄰居數(shù)(2)r≥。給定一個圓盤圖G=(V,E)，對任意vV∈，用()r NV

最大r跳；無向圓盤圖；極大獨立集；連通控制集

本文著錄格式：周志誠，李翠靜. 無向圓盤圖中最大r跳獨立鄰居數(shù)的估計[J]. 軟件，2016，37（11）：23-29

0 引言

在無線網(wǎng)絡(luò)中，節(jié)點為了與其它節(jié)點進行通信，需要滿足一定的連通性[1-3]，這種任務(wù)被稱之為網(wǎng)絡(luò)的拓撲控制[4]。受傳統(tǒng)的有線網(wǎng)絡(luò)物理骨干結(jié)構(gòu)的啟發(fā)，在無線網(wǎng)絡(luò)中，引入虛擬骨干網(wǎng)絡(luò)這一概念作為網(wǎng)絡(luò)拓撲控制的手段來有效利用網(wǎng)絡(luò)資源。于是，無線網(wǎng)絡(luò)中如何構(gòu)建虛擬骨干網(wǎng)成為關(guān)鍵。特別的，在無線傳感器網(wǎng)絡(luò)中，虛擬骨干網(wǎng)構(gòu)造一般以連通控制集的思想來構(gòu)造，隨著研究的進一步深入，人們在此基礎(chǔ)上考慮更一般的k連通r-跳控制集來作為虛擬骨干網(wǎng)。由此，如何構(gòu)建規(guī)模小的k連通r-跳控制集就成為關(guān)鍵，近幾年來受到很多學者的研究。

結(jié)合有向圖強連通相關(guān)知識[5-6]，我們知道在現(xiàn)有的關(guān)于連通控制集和k連通r-跳控制集的構(gòu)造算

法中一般都是先構(gòu)造控制集滿足控制要求，然后加入節(jié)點滿足連通性要求，或者反其道而行之，先連通再控制[7-8]。在這些構(gòu)建算法中，均以極大獨立集的構(gòu)造為基礎(chǔ)。在分析算法的性能，即近似比時，需要用到每個節(jié)點的獨立鄰居數(shù)的最大值作為算法的近似比度量的重要部分。

在以往研究文獻中，文獻[9]給出了單位圓盤圖上任何一個節(jié)點最多與5個相互獨立的節(jié)點相鄰，而后，文獻[10-11]將其推廣到一般圓盤圖中，此時每一個節(jié)點最多與β個相互獨立的節(jié)點相鄰，其中K=1時，β=5；K取其它值時，K為圓盤圖中最大圓的半徑與最小圓的半徑的比值。本文將上述結(jié)果推廣到r跳情形，即任何一個節(jié)點其r跳鄰居內(nèi)的兩兩r-跳獨立的節(jié)點的個數(shù)，得到一個最大r-跳獨立數(shù)的較好上界。

本文結(jié)構(gòu)如下，在第一節(jié)給出基本概念和介紹，在第二節(jié)給出主要結(jié)論及其證明，最后進行總結(jié)。

1 基本概念

定義1.2 極大獨立集(maximal independent set)：子集U?V稱為圖G的獨立集(independent set)，若U中任意兩點都是不相鄰的。若VU中任一點至少與U中一個點相鄰，則稱U為極大獨立集。

定義1.3 控制集：圖G=(V,E)的一個子集D?V稱為控制集，若VD中任一點至少與D中一個點相鄰，簡記為DS。D中的節(jié)點稱為控制節(jié)點（Dominator），VD的節(jié)點稱為被控制節(jié)點(Dominated)。

如下圖1中，黑色節(jié)點A，E，D表示控制節(jié)點，白色節(jié)點B，C，F(xiàn)表示被控制節(jié)點，從圖中很明顯可以看出，每一個白色節(jié)點都至少與一個黑色節(jié)點有邊相連，即被黑色節(jié)點所控制。

圖1 控制集

k-控制集dominating set) D定義為：D為V的子集，對任一點u∈(V/D)，u與D中至少有k個相鄰節(jié)點，子集DV?稱為k-控制集()kDS-。

若一個控制集D的導(dǎo)出子圖是連通的，則稱D為連通控制集 ()CDS；包含節(jié)點數(shù)最少的連通控制集稱為最小連通控制集；若k-控制集D的導(dǎo)出子圖是m-連通的，則子集D稱為m-連通k-控制集。而k全控制集（k-totally dominating set）是指子集SV?使得對任意一個節(jié)點uV∈，u與 S中至少k個節(jié)點相鄰。

定義1.4 r-鄰居：給定圖G=(V,E)，v∈V，u稱為v的一個r-鄰居，如果在G中存在一條長度至多為r的(v-u)路。記Nr(v)={u|u與v的距離最多為r}，稱為v的r-鄰域。

定義1.5 圓盤圖：單位圓盤是一個半徑為1的圓盤，用diskr(o)表示一個中心在o，半徑為r的圓盤。一個圖G=(V,E)稱為單位圓盤圖是指它可以嵌入到歐氏平面上，使得存在一條連接u與v的邊e=(u,v)，且僅當disk0.5(u)∩disk0.5(v)≠?，換言之，u與v的歐氏距離d(u,v)≤1。

圖G=(V,E)稱為圓盤圖是指它可以嵌入到歐氏平面上，使得存在一條連接u與v的邊e=(u,v)，當且僅當u與v的歐氏距離d(u,v)≤min{r,t} 。

圓盤圖是無線傳感器網(wǎng)絡(luò)的數(shù)學模型，每個傳感器節(jié)點都有一個通信范圍，以傳感器節(jié)點為中心，通信范圍為半徑作圓，即形成歐氏平面上的一個圓盤。每個圓盤與傳感器節(jié)點相對應(yīng)。于是一個無線傳感器網(wǎng)絡(luò)與一個圓盤圖對應(yīng)，兩個傳感器節(jié)點可以通信當且僅當它們在各自的通信范圍內(nèi)，即兩傳感器之間的距離小于等于它們的傳輸半徑。

下圖2是一個無向的圓盤圖實例。

圖2 無向圓盤圖

2 主要結(jié)論

引理2.1 在一個無向圓盤圖中，每一個節(jié)點最

多與β個獨立節(jié)點相鄰，其中K為最大圓盤的半徑與最小圓盤的半徑的比值，當1K=時，5β=；K取其它值時，

定理2.1 在無向圓盤圖G中，設(shè)rI是G的一個極大r跳獨立集，則對于任意的頂點uG∈，(u)r N包含有rI中最多β個節(jié)點，這里(u)r N為u的r跳鄰接集合，即為u，v之間的跳數(shù)，即連接u與v的最短路的邊數(shù)，下同)，β定義如下，

令

下面我們用歸納法來證明定理2.1的結(jié)論：

圖3為r=2時的一個實例，設(shè)最小圓盤的半徑為Rmin=1，另一(大)圓盤的半徑為R，且1＜R≤K。設(shè)x,y為點u的1-跳鄰居節(jié)點，wi,wj為點u的2-跳獨立節(jié)點，即vi,vj∈W。

圖3 無向圓盤圖

由引理2.1知到對于1()Nu，最多包含個獨立節(jié)點，若

離)，即h(x,y)=1，那么(wi,wj)-路徑表示jP的反方向）的長度至多為這與矛盾，故結(jié)論得證。

圖4 r=2時無向圓盤圖的示意圖

設(shè)A1，B1是屬于1()Nu中的元素，A1，B1與點u之間的歐氏距離為1(,)duA，1(,)duB，且有設(shè)A2，B2是屬于N2(u)中的元素，A2，B2與點u之間的歐氏距離表示為2(,)duA，

1）如果A2，B2為中的元素，那么根據(jù)的定義，A2，B2之間是3跳可達的，如下圖5所示，設(shè)滿足情況1）的中獨立節(jié)點的個數(shù)為n1，下面估計1n的大小。

圖5 r=2時無向圓盤圖的示意圖

假設(shè)d(u,A1)，d(u,B1)已經(jīng)確定，A2，B2之間連邊構(gòu)成一個三角形，考慮臨界情況，設(shè)角u大小為α，則只要比臨界角小一點，A2，B2就不再獨立的。顯然，α越小，在圓盤圖中就能夠獲得越多的這種獨立節(jié)點，用αmin表示角度最小的情況，那么在圓盤圖中最多有2παmin個2-跳獨立節(jié)點，從而有：

下面來求最小的這種角minα。

圖6 極限情況下構(gòu)成的三角形

令d2=d(u,B2)，d3=d(u,A2)，則有2≤d2≤K+d1，2≤d3≤K+d1，由余弦公式可得：

注意到cosα在[0,]π中是單調(diào)遞減的，要獲得αmin，即要使得等式（2.3）的右邊值最大。為此考慮如下規(guī)劃

求minα的問題轉(zhuǎn)化成求函數(shù)f在上面條件的限制下的極大值問題，我們利用KKT方程來求解，即拉格朗日函數(shù)。

解KKT方程組（2.5）：

因為三角形還要滿足其任意兩條邊之和大于第三條邊，式（2.5）的解還必須滿足條件（2.6），

通過計算求得滿足（2.5-2.6）的所有點為：

將上述8個點依次代入（2.4）的目標函數(shù)中，其中最大的即為（2.4）的最優(yōu)值，代入后可得目標值為如下三種情形：

下面來討論最大值。

（i）當12K＜≤時，①，②，③三個式子都成立，利用微積分判別法知，

當22K＜≤時有（4.5）的最優(yōu)值為maxf=

（ii）當24K＜≤時，此時②，③兩式可以成立，采用相減法判別②，③的大小，可知maxf=

（iii）當4K≥時，只有式②成立。

綜上知

于是

2）假如A1，B2（或者A2，B1）為32T中的元素，如上圖4為r=2時的無線圓盤圖的示意圖，那么根據(jù)的定義，A1，B2之間是3跳可達的，那么必然有A1，B1是相互獨立的節(jié)點，設(shè)滿足情況2）的獨立節(jié)點的個數(shù)為2n.

若A1，B1是相互獨立的節(jié)點，則內(nèi)任意兩個分別位于由u指向A1，B1方向的兩條不同射線上A1及B1外的點g,h都是獨立的(g在上，h在若有A2，B2屬于則A1，A2不是2跳獨立的，故與中的點不能同時存在，且由上圖容易知道因此有，即n2=0，于是

圖7 r=3時無向圓盤圖

設(shè)iw,jw是iuf，juf路上位于if，jf緊前的節(jié)點，則u到iw,jw是2跳的，且h(iw,jw)=4，否則

從而

由上面的結(jié)論，我們有

圖8 r=3時的圓盤圖

假設(shè)A3，B3是中的節(jié)點，那么A3，B3之間恰好經(jīng)過4跳可相互到達，那么只可能是這樣一種情況A1，B2（或A2，B1）之間有邊相連，且A2，B2是兩個2跳獨立的節(jié)點，A1與B2獨立，于是由前述證明知中元素的個數(shù)一定不大于中元素的個數(shù)，即

故

綜上，

3 結(jié)論

本文主要是針對圓盤圖上的鄰居最大獨立數(shù)進行了研究，得出了一個上界，利用該上界可以得到k-連通r-跳控制集構(gòu)造算法的一個近似比。進一步的研究是改進此上界，另外，估計圖的r-跳獨立集大小和求解最大r-跳獨立集也是很有意義的工作，它能用來指導(dǎo)虛擬骨干網(wǎng)構(gòu)造算法的設(shè)計。

致謝

感謝編輯和審稿人的幫助和建議。

[1] 錢樂, 李文生. 基于S3C6410的多媒體傳感節(jié)點的研究與實踐[J]. 新型工業(yè)化, 2012, 2(8)∶ 33-40.

[2] 張朋, 周公博, 蔡志雄, 等. 雙射頻無線傳感器網(wǎng)絡(luò)節(jié)點硬件設(shè)計[J]. 新型工業(yè)化, 2013, 3(11)∶ 21-26.

[3] Zeng Jian, Jing Xiaojun, You Siqing.Research on Channel Modeling of Stratospheric Communication Systems[J]. The Journal of New Industrialization, 2011, 1(12)∶ 70-74.

[4] Xiuying Li, Zhao Zhang. 2010. Two algorithms for minimum 2-connected r-hop dominating set. Information Processing Letters 110∶ 22, 986-991.

[5] 吳金全. 有向圖的強連通分量及應(yīng)用[J]. 軟件, 2014, 35(3)∶ 72-75.

[6] 郭衍奎, 胡俊, 徐晨光, 等. 一種基于極大連通子圖的相關(guān)度屬性選擇算法[J]. 軟件, 2014, 35(5)∶ 69-72.

[7] W. L. Wu, H. W. Du, X. H. Jia,et al Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theor. Comput.Sci. 352 (2006) 1-7.

[8] D. Li, L. Liu and H. Yang, Minimum connected r-hop k- dominating set in wireless networks, Discrete Math. Algorithm. Appl. 1 (2009) 45-58.

[9] P. J. Wan, K. M. Alzoubi and O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, ACM/Springer Mobile Netw. Appl. 9 (2004) 141-149. A preliminary version of this paper appeared in IEEE INFOCOM, 2002.

[10] D.-Z. Du, P.-J. Wan, Connected Dominating Set∶ Theory and Applications, Springer, 2013U. Erez and S. ten Brink, “A close-to-capacity dirty paper coding scheme,” Information Theory, IEEE Transactions on, 2005 51(10)∶ 3417-3432.

[11] P. J. Wan, L. Wang and F. F. Yao, Minimum CDS in multihop wireless networks with dis[arate communication ranges, in WASA (2010).R. Muharar, R. Zakhour and J. Evans, “Optimal power allocation and user loading for multiuser MISO channels with regularized channel inversion,” Communications, IEEE Transactions on, 2013, 61(12)∶ 5030- 5041.

Approximate Number of Maximum r-hop Independent Neighborhood Vertex of Disk Graph

ZHOU Zhi-cheng, LI Cui-jing
(Beijing University of Posts and Telecommunications, Beijing, 100876, China)

In this paper, we consider the maximum r-hop (2)r≥ independent neighborhood vertex of disk graph. Given a disk graph G=(V,E), let （）r NV be the set of vertices which distance is at most r-hop from v. For any

Maximum r-hop; Undirected disk graph; Maximal independent set; Connected dominating set

TN925+.3

A

10.3969/j.issn.1003-6970.2016.11.006

中國國家自然科學基金(11571044, 11471052)。

周志誠(1990-)，男，碩士研究生，主要研究方向：組合優(yōu)化。李翠娟(1989-)，女，碩士研究生，主要研究方向：組合優(yōu)化。

表示所有距節(jié)點v跳數(shù)最多為r的節(jié)點集合，則對G中任何一個r-跳獨立集I，其在()r NV內(nèi)最多有β個節(jié)點，這里K是圓盤圖的最大圓盤半徑與最小圓盤半徑的比值.

independent set I of G, I have at mostvertices inHere K is a ratio between largest disk radius and smallest disk radius.