Abstract
隨著科技的發展，內嵌無線通訊、精密感測、計算等功能之感測器裝置的使用已日漸地成熟與普及。具通訊與計算能力的智慧型感測器裝置，提供了一個全新的資料收集模式，也創造出多元化的應用。在可想見的未來，無線感測器系統將大規模地融入人們的生活環境，提供大量、即時、且各式各樣的感測器資料，因此如何駕馭、管理與應用智慧型感測器系統所蒐集的資料，即成為一個極具挑戰性的研究課題。由於感測器裝置的硬體設計以成本為考量，因此感測器裝置本身所配備資源，諸如能源供應等，均受限制。因此，如何在資源受限的條件下，設計高效率的資料收集與傳輸技術，成為相關研究的焦點所在。在無線感測器網路應用中，除了單一節點資料的收集外，針對一群感測器節點資料之聚合查詢，如平均、總和、最大值等聚合值，也廣為使用。常見的感測器資料聚合查詢應用諸如，平均雨量的回報、最大濕度節點的尋找等。 現有最常見的感測器資料聚合方式為樹狀式聚合計算。樹狀式聚合計算，首先對感測器網路，建構一支以主機為根節點的擴張樹，連接網路節點。而後資料聚合計算則由葉節點開始層層地進行:各節點接收其子節點所傳送至之部份聚合值，並依本身資料與所接收之聚合值，計算出新的部份聚合值，往其母節點傳送；層層進行，最終於根節點計算出最終聚合值。然而，樹狀式聚合計算其缺點為通訊容錯能力不佳。現有感測器節點採用的通訊協定主要著眼點為低功耗的無線通訊。該協定確實提升能源的利用率，但代價為約百分之三十之封包流失率。也因此，樹狀式聚合計算被採用時，許多部份聚合值將因感測器節點間通訊上的失敗而遺失。單一節點部份聚合值的傳遞失敗，將造成以該感測器為根節點之子樹資料遺失，使得最終計算出來的聚合值遠偏離實際值。 欲提升感測器資料聚合計算上的通訊容錯能力，最直接的方法為採用可靠率較高的協定。然而，相對地需付出高感測器能源消耗之代價，造成能源管理使用上的負擔。因此，在使用現階段通訊協定前提下，以多路徑式傳遞為基礎來提升通訊容錯力之多路徑式聚合計算，近來則廣為相關研究所注意。有別於樹狀式聚合計算，在多路徑式聚合計算中，感測器節點廣播其部分聚合值至其上一層的節點。由於一筆部分聚合值有多筆複本在網路中傳遞與計算，唯有在所有複本皆遺失的狀況下，才會造成該部分聚合值的遺失，也因此在原本的協定下，大幅提升了聚合計算之容錯能力。 但也由於一筆部分聚合值有多筆複本在網路中傳遞，相同的資料可能會被接收與計算多次，衍生出重複計數的問題。因此，多路徑式聚合計算多結合複本無影響性之速寫結構(duplicate-insensitive synopses)來避免重複記數的問題。現有許多技術可被引用來產生複本無影響性之速寫結構，然而現有技術的直接引用帶來不同的優缺點。分析、了解、設計複本無影響性之速寫結構為本博士論文之研究主軸。本論文提出一系列之技術來生成複本無影響性之速寫結構，且提供資料聚合計算誤差結果之保證。並於論文中透由複雜度理論分析論文中所提出之技術，也透過完整的實驗模擬驗證本論文所提出方法之優越性與正確性。