賽題描述

Ad Hoc網(wǎng)絡(luò)是當(dāng)前網(wǎng)絡(luò)和通信技術(shù)研究的熱點之一，對于諸如軍隊和在野外作業(yè)的大型公司和集團來說，Ad Hoc網(wǎng)絡(luò)有著無需基站、無需特定交換和路由節(jié)點、隨機組建、靈活接入、移動方便等特點，因而具有極大的吸引力。

在Ad Hoc網(wǎng)絡(luò)中，節(jié)點之間的通信均通過無線傳輸來完成，由于發(fā)射功率以及信道（即頻率）的限制，節(jié)點的覆蓋范圍有限，當(dāng)它要與其覆蓋范圍之外的節(jié)點進行通信時，可以通過中間節(jié)點轉(zhuǎn)發(fā)，如右圖所示。

對一個指定區(qū)域，用一系列稱為一跳覆蓋區(qū)的小區(qū)域?qū)⑵溆兄丿B地完全覆蓋，對每個一跳覆蓋區(qū)分配一個信道，處于幾個一跳覆蓋區(qū)重疊部分的節(jié)點同時使用幾個信道工作。在同一個一跳覆蓋區(qū)內(nèi)的用戶使用同一個信道相互通信；不同一跳覆蓋區(qū)的用戶之間通過中間節(jié)點轉(zhuǎn)發(fā)。如圖中，節(jié)點A,B間的通信可由路由A-C-D-B或A-C-E-F-B實現(xiàn)。如果區(qū)域中任意兩個節(jié)點都能通信，則稱之為連通。

現(xiàn)在，需要在一個1000*1000(面積單位)的區(qū)域內(nèi)構(gòu)建一個Ad Hoc網(wǎng)絡(luò)，請你完成以下工作：

（1）   將此正方形區(qū)域用若干個半徑都是100的圓完全覆蓋，要求相鄰兩個圓的公共面積不小于一個圓面積的5%，最少需要多少個圓（如果一個圓只有部分在正方形區(qū)域中，也按一個計算）？若給每個圓分配一個信道，使得有公共部分的圓擁有不同的信道，最少需要幾個信道？怎樣分配（用示意圖標出）？如果將上面的5%改為18%?