在未知結構的無線電網路上探討選擇群與廣播

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.