计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2014年
11期
3409-3412,3416
,共5页
刘文彬%李香宝%杨波%志强
劉文彬%李香寶%楊波%誌彊
류문빈%리향보%양파%지강
数据聚集%最小延时%物理干扰模型%聚集调度算法%通信冲突%信干噪比
數據聚集%最小延時%物理榦擾模型%聚集調度算法%通信遲突%信榦譟比
수거취집%최소연시%물리간우모형%취집조도산법%통신충돌%신간조비
data aggregation%minimum-latency%physical interference model%aggregation scheduling algorithm%communica-tion collision%SINR
针对现有的基于物理干扰模型的数据聚集调度近似算法具有延时较高的问题，提出了一种改进的数据聚集调度近似算法。该算法首先构造一个连通支配集作为数据聚集树，使各节点根据数据聚集树分层进行数据调度；然后将整个网络划分为若干个边长相等的正方形区域，使每个区域中最多包含一个支配节点；最后对各个区域进行着色，并从颜色相同的每个正方形区域中任选一个普通节点，使它们能同时将数据汇聚到相应的支配节点。当数据从所有普通节点聚集到相应支配节点后，则将这些正方形区域构成一个大小相同的块，并采用四种颜色对这些块进行着色，使颜色相同的各个块中任选一条通信链路能够同时进行数据传输而不会发生通信冲突和干扰。理论分析表明，该算法的延时上界为K2Δ＋8K2R-3R；仿真模拟的结果表明，该算法产生的数据聚集延时低于现有算法。
針對現有的基于物理榦擾模型的數據聚集調度近似算法具有延時較高的問題，提齣瞭一種改進的數據聚集調度近似算法。該算法首先構造一箇連通支配集作為數據聚集樹，使各節點根據數據聚集樹分層進行數據調度；然後將整箇網絡劃分為若榦箇邊長相等的正方形區域，使每箇區域中最多包含一箇支配節點；最後對各箇區域進行著色，併從顏色相同的每箇正方形區域中任選一箇普通節點，使它們能同時將數據彙聚到相應的支配節點。噹數據從所有普通節點聚集到相應支配節點後，則將這些正方形區域構成一箇大小相同的塊，併採用四種顏色對這些塊進行著色，使顏色相同的各箇塊中任選一條通信鏈路能夠同時進行數據傳輸而不會髮生通信遲突和榦擾。理論分析錶明，該算法的延時上界為K2Δ＋8K2R-3R；倣真模擬的結果錶明，該算法產生的數據聚集延時低于現有算法。
침대현유적기우물리간우모형적수거취집조도근사산법구유연시교고적문제，제출료일충개진적수거취집조도근사산법。해산법수선구조일개련통지배집작위수거취집수，사각절점근거수거취집수분층진행수거조도；연후장정개망락화분위약간개변장상등적정방형구역，사매개구역중최다포함일개지배절점；최후대각개구역진행착색，병종안색상동적매개정방형구역중임선일개보통절점，사타문능동시장수거회취도상응적지배절점。당수거종소유보통절점취집도상응지배절점후，칙장저사정방형구역구성일개대소상동적괴，병채용사충안색대저사괴진행착색，사안색상동적각개괴중임선일조통신련로능구동시진행수거전수이불회발생통신충돌화간우。이론분석표명，해산법적연시상계위K2Δ＋8K2R-3R；방진모의적결과표명，해산법산생적수거취집연시저우현유산법。
This paper presented an improved data aggregation scheduling approximation algorithm,due to the existing data ag-gregation scheduling algorithms under the physical interference model had high time latency in wireless sensor networks.First-ly,this algorithm constructed a connected dominating set as a data aggregation tree so that every node’s data in network could be scheduled layer by layer.Secondly,it divided the whole network into square cells with the same side length so that each cell contained one dominator at most.Finally,it colored every square cell by using different colors.Therefore,some nodes from the cells with same color could be selected randomly to be scheduled simultaneously.After all dominatees’s data were ag-gregated to their corresponding dominators,the whole network was divided into large-blocks consisting of same number of square cells,and the four colors were used to color these blocks so that the adjacent blocks had different colors.And then, some communication links were selected randomly from these blocks with same color,which could be scheduled simultaneously without any communication collision and transmission interference.The theoretical analysis shows that the algorithm has a la-tency bound with K2Δ+8K2R-3R.Simulation results show that this algorithm has lower average latency than previous works.
