周志誠(chéng)，李翠靜

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

無(wú)向圓盤(pán)圖中最大r跳獨(dú)立鄰居數(shù)的估計(jì)

周志誠(chéng)1，李翠靜1

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

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

最大r跳；無(wú)向圓盤(pán)圖；極大獨(dú)立集；連通控制集

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

0 引言

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

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

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

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

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

1 基本概念

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

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

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

圖1 控制集

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

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

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

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

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

圓盤(pán)圖是無(wú)線傳感器網(wǎng)絡(luò)的數(shù)學(xué)模型，每個(gè)傳感器節(jié)點(diǎn)都有一個(gè)通信范圍，以傳感器節(jié)點(diǎn)為中心，通信范圍為半徑作圓，即形成歐氏平面上的一個(gè)圓盤(pán)。每個(gè)圓盤(pán)與傳感器節(jié)點(diǎn)相對(duì)應(yīng)。于是一個(gè)無(wú)線傳感器網(wǎng)絡(luò)與一個(gè)圓盤(pán)圖對(duì)應(yīng)，兩個(gè)傳感器節(jié)點(diǎn)可以通信當(dāng)且僅當(dāng)它們?cè)诟髯缘耐ㄐ欧秶鷥?nèi)，即兩傳感器之間的距離小于等于它們的傳輸半徑。

下圖2是一個(gè)無(wú)向的圓盤(pán)圖實(shí)例。

圖2 無(wú)向圓盤(pán)圖

2 主要結(jié)論

引理2.1 在一個(gè)無(wú)向圓盤(pán)圖中，每一個(gè)節(jié)點(diǎn)最

多與β個(gè)獨(dú)立節(jié)點(diǎn)相鄰，其中K為最大圓盤(pán)的半徑與最小圓盤(pán)的半徑的比值，當(dāng)1K=時(shí)，5β=；K取其它值時(shí)，

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

令

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

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

圖3 無(wú)向圓盤(pán)圖

由引理2.1知到對(duì)于1()Nu，最多包含個(gè)獨(dú)立節(jié)點(diǎn)，若

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

圖4 r=2時(shí)無(wú)向圓盤(pán)圖的示意圖

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

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

圖5 r=2時(shí)無(wú)向圓盤(pán)圖的示意圖

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

下面來(lái)求最小的這種角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α的問(wèn)題轉(zhuǎn)化成求函數(shù)f在上面條件的限制下的極大值問(wèn)題，我們利用KKT方程來(lái)求解，即拉格朗日函數(shù)。

解KKT方程組（2.5）：

因?yàn)槿切芜€要滿足其任意兩條邊之和大于第三條邊，式（2.5）的解還必須滿足條件（2.6），

通過(guò)計(jì)算求得滿足（2.5-2.6）的所有點(diǎn)為：

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

下面來(lái)討論最大值。

（i）當(dāng)12K＜≤時(shí)，①，②，③三個(gè)式子都成立，利用微積分判別法知，

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

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

（iii）當(dāng)4K≥時(shí)，只有式②成立。

綜上知

于是

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

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

圖7 r=3時(shí)無(wú)向圓盤(pán)圖

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

從而

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

圖8 r=3時(shí)的圓盤(pán)圖

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

故

綜上，

3 結(jié)論

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

致謝

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

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

[2] 張朋, 周公博, 蔡志雄, 等. 雙射頻無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)硬件設(shè)計(jì)[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] 吳金全. 有向圖的強(qiáng)連通分量及應(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

中國(guó)國(guó)家自然科學(xué)基金(11571044, 11471052)。

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

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

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