Advisor : Prof. Frank Y.S. Lin Presented by Yen-Yi, Hsu An Efficient Algorithm for Constructing Object Tracking Tree in Wireless Sensor Networks Advisor : Prof. Frank Y.S. Lin Presented by Yen-Yi, Hsu

Contents 1 2 3 4 Introduction Preliminary Problem Formulation Lagrange Relaxation 4

Introduction Object tracking is key application issue of WSNs How to construct the object tracking tree efficiently Total cost = Update cost + Query Cost 我的研究方向是延續政達學長之前發表過的paper，希望能夠發展一個演算法，以最小的成本來建立object tracking tree，在學長的model與其他的PAPER中，在建立時的成本，都只有考量update cost，在老師上次的建議之後，我們試著把query cost 加入考量。Object tracking tree是透過一連串的update來維持object的最新位置，然後透過查詢來取得object的資訊。

Preliminary Update and query mechanism Every communication nodes maintain a detected list Assume object is identified For example: p sink p q x y ∞ 8 6 10 7 4 這邊我們以一個例子來說明update和query 的運作方式，假設現在有一個object進入到sensor node x的sensing range，node x就會開始傳送update message，沿著選定的path傳送到sink端，在這path上的communication node，接收到update message之後，就會去更新自己的detected list，這個detected list記錄的是各個object的資訊，是由哪一個children傳送過來的。當object從node x移動到node y 時，node y一樣會將update message往sink端傳送，communication node p接收到node y傳送過來的訊息之後，發現object傳送過來的位置與原本不同，就會進行更新detected list的動作。透過即時的update可以保持這個網路能夠掌握object的最新位置。這時候在node q上擁有的資訊是有錯誤的，但是由於query message 從sink端開始傳送，到了node p時，就能夠知道要尋找該object需要從node y而不是從node q，因此node q的錯誤訊息並不會影響查詢結果的正確性。 y q x

Preliminary Update Cost If object move from x to y update cost: 4 * 10 = 40 If object move from y to x update cost: 7 * (8+6) = 98 sink p q x y ∞ 8 6 10 7 4 瞭解了update與query的運作方式後，所以在update cost的計算上，當object在兩個sensor中移動時，update的訊息只需要傳送到兩個sensor最低的共同祖先，不需要傳送到sink，這樣的做法可以降低update cost。所以在右邊這個圖中，如果object 從sensor x移動到sensor y，update cost就是x移動到y的event rate，就是單位時間內移動的次數，乘以sensor y到node p之間的communication cost。

Preliminary Query cost = query rate * communication cost 再來就是Query Cost的計算，某一個node的query cost，就是該node的query rate乘上需要花費的communication cost。下面這個圖記錄著，object 在各node之間移動的event rate，且每個node都遵守著流量守衡的規則。我們取中的一小部份，來利用Markov chain來計算在steady-state的狀態下，object分別會位於各node的機率。

Preliminary 1 2 3 4 5 1 2 3 4 5 destination 1 2 3 4 5 source 10 40 44 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 40 38 44 10 11 8 source 將原始的圖，以一個P矩陣來表示，每個source移動到各個destination的機率，就是移動到該node的次數除以total的移出量。

Preliminary 在steady-state之下，就是在n-1這個時間下的狀態，會等於下一個單位時間的狀態，以拍來表示steady-state下，object位於各sensor下的機率。 所以拍P=P，加上object位於各sensor下的機率加總要等於1。

Preliminary : the probability of the object which is in sensor x’s sensing range Query rate = * T (total number of queries) I 可以導出拍的計算方式，會以Qx，來表示object位於sensor node x的機率，將算出來的機率成以一個T，就是各node的query rate，其中T就是總共的查詢次數。最後我們希望可以針對T來做分析，在T的值不同的狀況，對於整個cost會有什麼樣的影響。

Preliminary Query Cost Ex: The object o is in z’s sensing range * T * communication cost of sink to node r sink p q x y p 有了query rate，就可以計算query cost。這邊在query cost的計算，假設object位於sensor z的sensing range，query message只要傳送到node r，就可以知道object一定位於sensor z，所以不必在往下傳；因此可以看出，對於每個sensor node而言，query所花費的communication cost都只需要計算到上一個communication node，也就是每一條path最後的一段link都可以不必加入計算。所以這個例子而言，query cost就是object位於sensor z的probability * total query數 * sink到r的communication cost。 r r z z o

Problem Formulation S:所有sensor node所成的集合 C:所有communication node包括sink node所成的集合 R: L:所有link(i,j)所成的集合，其中i不等於j A:所有transmission cost a(i,j)所成的集合，a(i,j)就是link (i,j)的transmission cost Ps:所有sensor node到sink的candidate path所成的集合 Qs: object位於sensor node s的機率 T: 單位時間內總共的查詢次數

Problem Formulation x y ∞ 8 6 10 7 4 sink p q 如果link (i,j)是位於在path p上的話，就是1，否則就是0 (i,j)都屬於communication node，就是1，否則就是0 C-C =1 C-S=0就表示是剛剛提到不必計算的部份

Problem Formulation x y ∞ 8 6 10 7 4 sink p q Xp:如果sensor node s使用path p將資料傳輸到sink，則Xp為1，否則為0 Z:如果sensor node s 使用link(i,j)將資料傳輸到sink，則為1，否則為0 t:如果Zx=0 and Zy =1 則為1，否則為0 以剛的x移動到y的圖為例，紅色的是x傳送資料到sink會使用的link，綠色則是y使用的link，在update cost部份我們僅需要計算紫色的這一條link，轉換成以真值表的方式來表示，當t=1的link，才是在計算update cost時，需要被計算的link

Problem Formulation Objective function: (ip1) routing constraint:每個sensor node與sink node之間只會選擇一條path做為傳輸路徑 (ip2) tree-constraint:除了sink node以外，每個node的outgoing link 都要=1，避免產生cycle (ip3)如果Xp被選擇，而且link(i,j)在這條path上，則Z就必須要=1 (ip4)(ip5)就是以這個真值表來看，只有在Zx=0，Zy=1時，t(i,j)=1

Problem Formulation (ip6)redundant constraint:當object 移動時，一定要有一個sensor能夠偵測到object (ip7)(8)(9)都是限制decision variable為一個0.1變數

Variety of the Model If we let all communication nodes maintain the correct information, the update cost must be modified. sink p q x y ∞ 8 6 10 7 4 另外在老師的建議之後，我們考量了一些不同的情境；首先是在剛剛的例子中，雖然communication node中部份錯誤的訊息，不會影響到query 的正確性，但我們可以試著將考慮將所有node的detected list都維持著正確的資訊，這樣一來，update cost的計算方式就必須要有所更改。以這張圖來看，本來計算的update cost只需要計算p-y的communication cost，情境更改後，我們就必需要多考量x-q-p的這一段成本。以真值表來看，我們改用一個gxy來表示兩者共用的link，這是在計算update cost時需要被扣除的。因此我們可以將update cost更改為Zx+Zy-2g。在(IP4)、(IP5)這兩條限制是，也需要修改已符合真值表的結果。

Variety of the Model If communication node doesn't have detected list, the query message must be sent to the leaf node.  Query cost: We extend it to send message to the object Query cost: : the cost that the sensor node s send message to the object 第二種情況是，如果communication cost中並沒有detected list，也可以視為所有節點都是sensor node，這樣一來，在查詢的時候，query message就必須要一路往下傳，一直傳到leaf node為止，或者是傳到object 所在的sensor node，才能得到object的information。在計算query cost時，就可以不必考慮V(i,j)。第三種情況，原本的object tracking tree的主要目的都是為了監控object的位置，或許我們可以延伸成，將資訊傳送給object，所以在查詢到object的位置之後，就必需要多一段成本，Ws，就是sensor node s 傳送訊息給object所需花費的成本。

Lagrangean Relaxation

Lagrangean Relaxation

Lagrangean Relaxation

Lagrangean Relaxation

Lagrangean Relaxation

Lagrangean Relaxation

Thanks for you listening