星期三, 11月 28, 2007

轉貼:設計師之歌 - 死了都要改

不知道怎麼弄過來, 貼個Link吧..

轉貼:設計師之歌 - 死了都要改

http://blog.xuite.net/ptsblog/news/14474884

星期五, 11月 23, 2007

Why does Pure Aloha perform worse than Slotted Aloha?

一. Why does Pure Aloha perform worse than Slotted Aloha?


  • 1.ALOHA協議(Pure ALOHA) 當傳輸點有資料需要傳送的時候,它會向立即向通訊頻道傳送。
    接收點在收到資料後,會ACK傳輸點。
    如果接收的資料有錯誤,接收點會向傳輸點發送NACK。
    當網路上的兩個傳輸點同時向頻道傳輸資料的時候,會發生衝突,這種情況下,兩個點都停止 一段時間後,再次嘗試傳送。
  • 2.分段ALOHA(Slotted ALOHA) 這是對純ALOHA協議的一個改進。改進之處在於,它把頻道在時間上分段,每個傳輸點只能在一個分段的開始處進行傳送。每次傳送的資料必須少於或者等於一個頻道的一個時間分段。這樣很大的減少了傳輸頻道的衝突。

    如果假設傳輸點對頻道的使用是符合Poisson分佈 的話,我們可以得以下公式:
    純ALOHA協議:
    S = Ge − 2G
    分段ALOHA協議:
    S = Ge − G

    S是通過量, G是提供的流量(每單位時間通過的資料包數量).
    從這個公式我們可以看出, 對純ALOHA來說,當G = 0.5 的時候, S 達到最大值 18.4%. 只有當 G<= 0.5 的時候, 純ALOHA系統才處於穩定狀態. 對分段ALOHA來說, 當G = 1 的時候, S 達到最大值 36%.只有當 G<= 1 的時候, 分段ALOHA系統才處於穩定狀態.
    2. According to Textbook pp. 2-48~2-51, why does 1-persistent CSMA have lower throughput than non-persistent CSMA when generated traffic rate is higher than 1 (G>1)? Why does 1-persistent CSMA have shorter latency than non-persistent CSMA?


  • 1. (1-persistent CSMA)原理
    若站點有資料發送,先監聽信道;
    若站點發現通道空閒,則發送;
    若通道忙,則繼續監聽直至發現通道空閒,然後完成發送;
    若產生衝突,等待一隨機時間,然後重新開始發送過程。
    優點:減少了通道空閒時間;
    缺點:增加了發生衝突的概率;
    廣播延遲對協定性能的影響:廣播延遲越大,發生衝突的可能性越大,協定性能越差;

  • 2. nonpersistent CSMA)原理
    若站點有資料發送,先監聽信道;
    若站點發現通道空閒,則發送;
    若通道忙,等待一隨機時間,然後重新開始發送過程;
    若產生衝突,等待一隨機時間,然後重新開始發送過程。
    優點:減少了衝突的概率;
    缺點:增加了通道空閒時間,資料發送延遲增大;
    通道效率比 1-persistent CSMA高,傳輸延遲比 1-persistent CSMA大。
  • REF:
    Poisson分佈 法國數學家西莫恩·德尼·蔔瓦松(Siméon-Denis Poisson)在1838年時發表。
    http://zh.wikipedia.org/w/index.php?title=%E6%B3%8A%E6%9D%BE%E5%88%86%E5%B8%83&variant=zh-tw
    ALOHA協議
    http://zh.wikipedia.org/wiki/ALOHA%E5%8D%8F%E8%AE%AE

星期一, 11月 05, 2007

ILS/HLS/GLS homework

繳交作業方式Nov-10-2007 11:59 a.m. Due

1. Read and then comment on the following papers.
Yao-Jen Chang, Shan-Yao Wu, Ting-Liang Shih,
Intersection Location Service and Performance Comparison of Three Location Service Algorithms for Vehicular Ad Hoc Networks in City Environments

這篇針對都會的街道特性, 提出位置資訊服務眼算法Intersection Location Service( ILS ), 並與 Hierarchical Location Service(HLS), Grid Location Service(GLS)演算法做比較。
透過實驗比較, ILS在街道上車間通訊的位置服務優於其它兩者.
A.車輛移動的方向對ILS, GLS, HLS 影響較大
B.區域面積的影響對 ILS影響小
C.車輛密度對GLS影響小
D.車速對GLS影響較大

車間通訊模式的優點:
1. 不需要龐大的基礎建設費用.
2. 提供更精確的交通資料.
3. 不需要額外的服務費用.
4. 較低的嚴遲時間.

ILS 是以 Chord Algorighm為基礎,具延展性的分散式位置資訊服務, 並以位置為基礎的路由演算法(Position-based routing) 代替傳統的以拓樸為基礎的路由演算法(Topology-based routing algorithm), 隨著GPS普及化, 在高速移動的無線網路環境下,利用節點位置資訊來決定封包傳送策略的演算法。

Yao-Jen Chang, Tseng-Yun Wang, Shi-Kai Tsai, Yu-Chia Chuang, "Action Science Approach to Experimenting Nonprofit Web 2.0 Services for Employment of Individuals with Mental Impairments" 2007 International Workshop on Social Media Analysis in conjunction with ACM/IEEE Web Intelligence 2007. (EI)

過去使用者對於自我的意見、照片甚至是影片皆不易於分享及互動,Web 2.0 讓使用者成為資訊的提供者, 使consumer 變成了contributor, Blog/ WIKI 都是代表性的產物,即使是小孩都能在幾分鐘內建立一個自己的Blog發表自己的意見,使用者不用去關心低層程式設計、資料庫等問題,而專注於”Contain”之上。利用這些優點,建立精障損傷者的分享報告,使每個使用者都能貢獻自己的知識。

2. Why is CSMA/CA instead of CSMA/CD used for 802.11?
CSMA/CD (Collision Detection)用於Ethernet , 在有線網路下利用backoff algorithm,
避免重送時再次發生資料碰狀。


CSMA/CA (Collision Avoidance) 應用於無線網路的protocal , 在資料傳送前,做出類似RTS/CTS的動作,雖然花費了較高的時間成本,但比整份資料重送來的划算。

“Hidden node”, 在有線網路下, 每個節點都可以知道其它節點的狀態, 但在無線網路, A知道B , B知道C, 但A不一定知道C , 因此用CSMA/CD不能得知collision 的問題, 因此使用CSMA/CA 來避免。