Two-Way Beacon Scheduling in ZigBee Tree-Based Wireless Sensor Networks

主旨：
broadcast和multicast是反向的運作，在ZigBee Tree-Based Wireless Sensor Networks中資料的上傳或是下載並定會受到原設計的影響造成通訊的延遲，因此此篇paper修改original superframe structure及Two-Way Beacon Scheduling的模式可大幅改善通訊延遲並降低網路中的干擾。

------------------------------------------------------------

解法：
將superframe分為多個active portions證明這是一個著色問題。

提出3點觀察：
1.Assigning upstream and downstream slots simultaneously can achieve lower delay than assigning upstream and downstream slots separately.
2.Suppose that routers Ri and Rj have indirect interference because they have some common end devices.If some end devices can be reconnected, then the indirect interference relation between Ri and Rj may be removed.
3.When selecting slots, a router with more interference neighbors should select its slots earlier.

演算法部分：
首先提出2種貪婪排程模擬比較。
上傳下載分別執行不同演算:FindUpSlot(v)和FindDnSlot(v)

FindUpSlot(v):

1.leaf node tu(v) = 0；non-leaf node tu(v) = max child+1
2.Let N(v) be the set of nodes that have direct or indirect interference with v and have received slots.
3.temp = tu(v) mod k is a feasible slot for v by examining the slots used by nodes in N(v).
(a)If there exists a v'∈N(v) such that v' and v have direct interference and su(v) = temp or sd(v) = temp, then the slot temp is not feasible for v.
(b)If there exists a v'∈N(v) such that v' and v have indirect interference and su(v) = temp or sd(v) = temp, then we will call procedure RemoveIndInt(v',v) to see if such interference can be removed.

FindDnSlot(v) :

1.leaf node td(v) = k - 1；non-leaf node td(v) = min child − 1
2和3同上

RemoveIndInt(v',v):

step 1:
Indirect interference appears when there is a common neighbor x of v’ and v.
If x is a router : ignored.
If x is an end device : try to associated x with another router
say w, other than v’ and v.
slots su(w) and sd(w):have to make sure this does not cause new interference
Otherwise: step 2

step 2:
step 1 allows us to reassociate x to another router to remove the interference
a positive response will be replied by this procedure
otherwise: a negative response will be replied

------------------------------------------------------------

結論：
modify the original superframe structure
define a two-way beacon scheduling (TBS) problem
propose a centralized algorithm to solve the TBS problem
the algorithm can effectively reduce the number of interference neighbors and thus decrease the network latency