《广告传媒广播通讯模式的阶层概念与碰撞》由会员分享，可在线阅读，更多相关《广告传媒广播通讯模式的阶层概念与碰撞（9页珍藏版）》请在金锄头文库上搜索。
1、廣播通訊模式的階層概念與碰撞蕭學宏 長榮管理學院圖書館資訊組組長兼資管系講師 楊昌彪 中山大學應用數學系副教授兼電子計算機中心資料組組長 shiaushmail.cju.edu.tw cbyangmath.nsysu.edu.tw中文摘要現今最常用的乙太網路(Ethernet)其通訊模式就是一種廣播通訊模式。在此種廣播通訊模式下的演算法如能運用階層觀念(layer concept)將可減少碰撞有效加快演算速度。本文中我們以廣播通訊模式下搜尋最大值的問題為例子提出未加入此種觀念的演算法並分析其平均時間複雜度為Q(ln2 n)。而有運用此觀念的演算法其平均時間複雜度為Q(ln n)。因此在廣播通訊
2、模式下的演算法若能運用階層的觀念對於加快演算速度將有所幫助。關鍵詞平行演算法廣播通訊模式階層觀念搜尋最大值碰撞一研究背景與目的在眾多平行計算模式(parallel computation models)中有多種簡單的模式而廣播通訊模式(broadcast communication mode)就是其中的一種1-12。在此模式下全部的機器共享唯一的通道並藉由此一通道進行訊號的連通(如圖1所示)。當有一部機器廣播(Broadcast)訊號時其他的機器可藉此通道接收訊號。當有二部以上的機器同時想要傳送消息時就會發生廣播碰撞(broadcast conflict)此時就有一個機制(resolution
3、 scheme)來解決碰撞使得只有一部機器可以傳播資料。12345768圖1此種模式不僅是較簡單的模式而且是較切合實際。現今最普遍的網路架構以乙太網路(Ethernet)為主其通訊模式就是一種廣播通訊模式。此種模式最大的特徵就是必須解決碰撞問題。如果碰撞是無可避免的那如何減少碰撞次數將是關鍵性的問題。在此種模式下架構演算法所需花費的時間共分三部分。第一部份是解決碰撞所需的時間第二部分是資料傳輸所需的時間最後一部份是進行運算所需的時間。若能減少此三部分時間之總和就能增進此演算法的執行效率。而其最具關鍵性的步驟是減少第一部份的時間換言之就是減少碰撞次數。目前所知大概有二種概念可以減少碰撞次數。第一
4、種是調整廣播機率的大小如此可期待大約有一個資料可廣播成功。第二種是逐一建立邏輯性的階層在建立階層的過程將資料分佈在每一個邏輯性的階層之中達到分散資料以減少參加碰撞的資料個數。不論是第一或第二種概念皆能有效減少碰撞次數。第一種概念是由Martel所提出的6雖然此概念應用在尋找最大值的問題上能證出具有O(ln n)的效果但是缺乏更嚴謹的上下界限以供參考比較。第二種概念是由作者之一楊昌彪教授所提出的10。在廣播通訊模式下將此概念運用在尋找最大值的問題上我們已證出12平均所需的時間槽縫(time slots)以 Tn 表示則4*ln n Tn 5*ln n。而Grabner和Prodinger14則利
5、用艱深的數學精準地證出 Tn /ln n p2/(3*ln 2) = 4.746276。不論是何者皆證明我們運用階層概念的演算法其平均時間複雜度為Q(ln n)。現在我們不僅試圖將此概念推廣至其他的應用也有興趣探討在尋找最大值的問題上如沒有運用階層概念或其他概念而改以直覺方式進行將會有何結果兩者之間的差距會有多大經我們證明其結果是Q(ln2 n) 確實比運用階層概念的演算法差上一個級數。此一結果證實運用階層概念有其效果因此在廣播通訊模式下想要發展有效的演算法階層概念是可考慮的方向。而直覺方式的結果可為其他新的概念提供一個比較的基石。以下我們將先介紹在廣播通訊模式下如何以扔銅板的方式解決碰撞問題
6、並說明其時間複雜度為Q(ln n)。然後再介紹在廣播通訊模式下如何以直覺方式尋找最大值並分析其時間複雜度為Q(ln2 n)。 最後則介紹階層概念如何應用在找尋最大值的問題上。我們已證出12其時間複雜度為Q(ln n)至於詳細的說明及證明在此省略。二扔擲銅板解決廣播碰撞之時間複雜度在廣播通訊模式下通道的狀況僅有三種。第一種是僅有一部機器想要在通道廣播當然資料廣播成功。第二種是有二部以上的機器皆想在通道廣播結果產生碰撞。第三種是沒有機器想要在通道廣播結果通道是安靜無聲。不論是哪一種狀況都會花費一個時間槽縫(time slot)。以下我們將詳細解說以扔擲銅板方式作為為解決碰撞的機制。假設有n個資料均
7、分在n部機器換言之每部機器各自擁有一個資料。每部機器皆想要利用唯一的通道傳送資料。當然會在第一個時間槽縫到達時產生碰撞現象。在下一個時間槽縫未到前每一部機器各自扔一次銅板。銅板有二面其一為人頭另一為數字。扔出人頭的機器在下一個時間槽縫到時參與對通道的廣播將資料傳送到唯一的通道。而扔出數字的人則放棄對通道廣播即被淘汰出局。此時通道會出現三種狀況。第一種是安靜無聲代表無任何機器扔得人頭剛才那批機器必須再各自扔銅板以決定在下一個時間槽縫到達時是否參與對通道的廣播。第二種是碰撞表示有二部機器以上扔得人頭此時只有扔得人頭的機器繼續再各自扔銅板以決定再下一個時間槽縫到達時的動作是廣播或是放棄。第三種是廣播
8、成功很明顯地代表僅有一部機器扔得人頭可對通道成功地廣播資料。令Dn代表平均花費的時間槽縫次數利用類似我們在12所提的證法可得到ln n Dn 2*ln n。而Prodinger13運用艱深的數學準確地證明Dn log2 n+ 1/2 - d2(log2 n)其中d2(x) = ; 是Riemanns -function; 是-function。此分析結果說明以扔銅板方式解決碰撞平均大約需要花費log2 n次的時間槽縫。以上所提ln n與log2 n的基底互換會造成以後分析式子的無謂膨脹混淆證明的主線發展又因為log2 n = ln n*log2 e = ln n*1.442695兩者之間僅差一
9、個常數值因此我們將用ln n作為以後表達式的主體以簡化我們的證明及說明。這樣的替換不會影響最後的結論。三以直覺方式尋找最大值在廣播通訊模式下尋找最大值的問題就如同在乙太網路(Ethernet)上有n部機器各自擁有一個資料要從中得知那部機器擁有最大值。若n = 8則如圖1所示。基本上以直覺方式進行尋找最大值的方法5就是利用在解決碰撞而最後有機器廣播資料成功時將小於此資料的機器淘汰出局而其他的機器則再進行下一回合。其進行的方式可視為有n個人在扔擲銅板扔出人頭的人他們再繼續扔銅板而扔出數字的人則暫時無權再扔銅板如此重複進行一直到最後只有一人扔出人頭。此人將其手中的資料公佈後所有小於此資料的人則淘汰出
10、局而所有大於此資料的人可再進行扔銅板直到最大的資料出現。經過一連串的扔銅板經過一連串的扔銅板經過一連串的扔銅板1, 2, 3, 4, 5, 6, 7, 84, 5, 6, 7, 88廣播成功7, 86廣播成功3廣播成功以圖2為例一開始有8個資料碰撞然後經過一連串的扔銅板(平均大約經過3=log2 8次的時間槽縫)排除碰撞後假設最後資料3成功地廣播。3廣播後僅剩資料4567及8當然還是會發生碰撞此時4567及8再度經過一連串的扔銅板以排除碰撞假設資料6成功地廣播。廣播後僅剩資料7及8還是會發生碰撞此時7及8再度經過一連串的扔銅板假設資料8是成功者。廣播後就沒有任何資料可以出來廣播。此時就可得知8
11、是最大的資料。圖2四以直覺方式尋找最大值的時間複雜度分析Levitan和Foster曾證明此演算法所需的成功廣播次數平均約為ln n次5。以下則探討此演算法加入排除碰撞後所需的時間槽縫次數。以直覺方式尋找最大值的問題其平均花費的時間槽縫次數以Tn代表則 。第一式若以n=8為例其中ln 8代表經過一連串的扔銅板。換言之平均經過ln 8次扔銅板後1,2,3,7,8中會有一個廣播成功且每一個的機會均等。所以代表T0,T1,T6,T7每一種狀況均有機會出現。T0表示在最大值8廣播成功的狀況下接下來將沒有任何資料可以再進行扔銅板換言之所有資料皆因小於最大值8而被淘汰出局。相反地T7表示在最小值1廣播成功
12、的狀況下任何資料都可以再進行扔銅板。T5表示在第三小的資料3廣播成功的狀況下尚有比它大的5個資料(4,5,6,7,8)有權再進行扔銅板換言之只淘汰了最小及第二小等二個資料(1,2)。n-1代入第一式可得將上式代入第一式再整理得到將上式由n逐一擴張至3可列出以下各式子將以上各列式子累加整理得到將上式整理可得若要分析Tn則需要分析Tn式子中及的上下界如此才能知道Tn的全貌。以下我們將先證明它們二者的上下界限然後再綜合討論Tn的上下界限最後導出時間複雜度Tn = Q(ln2 n)。Lemma 1. Proof.利用積分試驗法(Integral Test)之類似觀念可得運用部分積分法可導出 得證Lem
13、ma 2. Proof.因為是遞減函數且所以 第二式利用積分試驗法(Integral Test)之類似觀念可得 及 將上式代入第二式得 第三式運用部分積分法可導出將上列二結果代入第三式得到 得證Lemma 3.Proof.將Lemma 2代入上式可得到所以 得證Lemma 4.其中Proof.將Lemma 1及Lemma 3代入上式再整理出C1及C2即可得證。Theorem 5.在廣播通訊模式下以直覺方式找尋最大值之時間複雜度為Tn = Q(ln2 n)Proof.在Lemma 4證出 其中C1及C2在某定值之內且 。所以時間複雜度Tn = Q(ln2 n) 得證五運用階層概念尋找最大值在我們
14、尋找最大值的演算法中一開始時有n部機器各自擁有一個資料並想要利用唯一的通道傳送資料。此演算法最關鍵的地方是利用碰撞逐一建立邏輯性的階層。在建立階層的過程將資料分佈在每一個邏輯性的階層之中達到分散資料的效果自然可以減少參加碰撞的機器個數。以下階層一詞即代表邏輯性階層。當有廣播碰撞時就有一個新的階層被建立。然後參加此次碰撞的機器就扔銅板。扔到數字的機器放棄下一次的廣播留在目前的階層。而扔到人頭的機器可參加下一個時間槽縫的廣播並利用碰撞將它們自己往上提升至一個新的階層。此新的階層就變為正在活動中的階層簡稱為工作階層。任何時段僅有在工作階層且尚存活的機器有資格決定是否參加廣播。 6 3 83 56 81 2 4 75655 5 56 3 56 812345678階層1階層4
