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

周志誠，李翠靜

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

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

周志誠1，李翠靜1

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

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

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

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

0 引言

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

結合有向圖強連通相關知識[5-6]，我們知道在現有的關于連通控制集和k連通r-跳控制集的構造算

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

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

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

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中的節點稱為控制節點（Dominator），VD的節點稱為被控制節點(Dominated)。

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

圖1 控制集

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

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

定義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} 。

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

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

圖2 無向圓盤圖

2 主要結論

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

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

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

令

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

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

圖3 無向圓盤圖

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

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

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

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

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

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

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

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

圖6 極限情況下構成的三角形

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

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

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

解KKT方程組（2.5）：

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

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

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

下面來討論最大值。

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

當22K＜≤時有（4.5）的最優值為maxf=

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

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

綜上知

于是

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

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

圖7 r=3時無向圓盤圖

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

從而

由上面的結論，我們有

圖8 r=3時的圓盤圖

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

故

綜上，

3 結論

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

致謝

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

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

[2] 張朋, 周公博, 蔡志雄, 等. 雙射頻無線傳感器網絡節點硬件設計[J]. 新型工業化, 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] 吳金全. 有向圖的強連通分量及應用[J]. 軟件, 2014, 35(3)∶ 72-75.

[6] 郭衍奎, 胡俊, 徐晨光, 等. 一種基于極大連通子圖的相關度屬性選擇算法[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-)，男，碩士研究生，主要研究方向：組合優化。李翠娟(1989-)，女，碩士研究生，主要研究方向：組合優化。

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

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