Selective Family and Broadcasting on Unknown Radio Networks
Date Issued
2005
Date
2005
Author(s)
Tien, Wen-Chin
DOI
en-US
Abstract
在無線電網路上，廣播是一個很基本的問題。為了應付訊息碰撞，我們常常用到選擇群的概念。所謂的(n,k)-選擇群((n,k)-selective family)是指﹕對於任何一個從{1,2,…,n}中取出來的子集合f ，只要f的大小在1到k之間，我們都可以在(n,k)-選擇群中找到至少一個子集合s，使得s跟f的交集大小為一。首先我們先證明一個大小為 的(n,k)-選擇群是存在的。然後我們設計一些多項式時間的演算法來求(n,k)-選擇群。
We study the problem of (n,k)-selective family: Let [n] = {1,…,n} and let k < n. A family S of subsets of [n] is an (n,k)-selective family if, for every subset f of [n] such that 1 < | f | < k, there is a set s in S such that . The concept of selective family is a commonly used tool for coping with collision on radio networks. We first show that there exists a (n,k)-selective family with O(klog(n/k)) size, and then we design some polynomial time algorithms to find such selective family.
Subjects
廣播
無線電網路
selective family
broadcast
radio network
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92922063-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):f8c4c711fe791bf819b1396b89dc2c26