完全二分圖的符號星控制數與符號星劃分數以及一個改進的網路平面化演算法

Abstract

本篇論文分成兩個部分。第一部分考慮完全二分圖K_(m,n)的符號星控制數γ_SS (K_(m,n) )與符號星劃分數d_SS (K_(m,n) )。雖然γ_SS (K_(m,n) )與d_SS (K_(m,n) )在本篇論文之前就已經被討論過，但是都需要再釐清一些證明的推導。在本篇論文中，我們將對γ_SS (K_(m,n) )與d_SS (K_(m,n) )給出一個新的推導。本篇論文的第二部分則是考慮在許多感測網路協定中的一個重要的技術，也就是網路平面化。網路平面化的目的在對於一個給定的無線感測網路，得到一個連通的平面生成子圖，使得該平面子圖能被使用在各種不同的應用上（例如：地理路由、拓樸發現）。然而，網路平面化是一個困難的問題，目前知名又有效率的平面化演算法都只適用在單位圓盤圖並且已知位置資訊。在論文[20]中，Zhang等三位學者發表了一個適用於更一般化的網路模型的平面化演算法，該模型中無線感測器的傳輸半徑不需要一致，甚至連位置資訊都不需要。在本篇論文的第二部分，我們將會改進Zhang等人的平面化演算法，並且利用模擬來證明我們的演算法有更好的表現。