Khóa luận Tối ưu hóa Topology trong mạng AD-HOC

c khi kết thúc chương này, chúng ta cần lưu ý rằng tỉ lệ 1.Y được sử dụng liên quan tới sự tiêu thụ năng lương của card khi nó ở trạng thái truyền với sức mạnh tối đa.Mặt khác chúng ta sẽ thấy rằng giao thức kiểm soát Topology được dựa trên nền tảng đó là khả năng điều chỉnh khả năng truyền của các node không dây. Tính năng này được cung cấp trên một vài sản card theo chuẩn 802.11, như là các sản phẩm của CISSCO chẳng hạn.Ví dụ như card CISCO Aironet IEEE 802, 11 a / b / g có thể truyền với sức mạnh vào khoảng từ 1 MW đến 100 MW. Trong thực tế các card không dây có thể tiêu thụ năng lượng như là một hệ thống mạch tương tự hay kỹ thuật số. Như vậy, làm thế nào để xây dựng mô hình thiêu thụ năng lượng sao cho hợp lý và hiệu quả, trong khi khả năng hoạt động với tối đa sức mạnh của card không dây là chưa thực sự rõ ràng. Hầu hết các phương pháp tiếp cận trong các tài liệu đều có liên quan đến sức mạnh truyền, nó thường được mô hình hóa bằng các công thức được sử dụng trong chương 2, trừ khi có một số các quy định khác được xác định, trong bài viết này chúng ta sẽ đơn giản hóa mô hình tiêu thụ năng lương, cụ thể chúng ta sẽ sử dụng các định nghĩa về chi phí năng lượng sau: Định nghĩa 2.3.1(Chi phí năng lượng) Cho một vùng ảnh hưởng RA của một mạng Md=(N, L) chi phí năng lượng cho RA được tính theo công thức sau: trong đó là hệ số suy giảm năng lượng theo khoảng cách. Lưu ý rằng định nghĩa của chi phí năng lượng được nêu ở phía trên là gắn liền với giả thiết hoạt động của chúng ta, đó là những tín hiệu không dây lan truyền theo mô hình log-distance path. 2.4. Mô hình hóa tính di động Tính di động của những node là một trong những tính năng nổi bật trong mạng ad-hoc. Như là một hệ quả tất yếu trong việc thiết kế các giao thức cho mạng ad-hoc, tính di động là một phần quan trọng của việc thiết kế này.Từ thực tế là việc triển khai mạng ad-hoc là khá khó, việc mô hình sự chuyển động thực là một công việc khá khó khăn, các phương pháp tiếp cận phổ biến là sử dụng các mô hình tổng hợp và sự mô phỏng. Mô hình hóa tính di động của mạng ad-hoc thường là: Mô phỏng sự chuyển động: dành cho những ứng dụng của mạng ad-hoc trong một diện rộng, mô hình phải mô hình được những sự chuyển động trong một khu vực rộng lớn với nhiều thành phần tham gia: từ sự chuyển động của những sinh viên trong khuôn viên trường tới những chiếc xe đang lưu thông trên đường cao tốc hay từ sự di chuyển của các nhóm du lịch trên các vùng núi hay là những đội cứu hộ đang hoạt động trên những khu vực thiên tai. Cung cấp một mô hình di động phù hợp với tất cả các loại hình di động gần như là một công việc không thể thực hiện.Tuy nhiên một mô hình di động ít nhất phải mô tả được tính chất của một ứng dụng nào đó. Đơn giản hóa việc mô phỏng/ phân tích: cho đến khi việc mô hình hóa tính di động được sử dụng trong mạng ad-hoc, thì mô việc mô hình hóa này nên được đơn giản hóa bằng cách tích hợp thêm các sự mô phỏng theo một khoảng thời gian hợp lý. Hơn nữa bằng cách sử dụng những mô hình tương đối đơn giản sẽ làm cho việc phân tích các thông số của mạng ad-hoc trở nên dễ dàng hơn. Lần lượt các kết quả này có thể được sử dụng để tối ưu hóa hiệu suất thực thi của các giao thức mạng ad-hoc. Rõ ràng hai tiêu chí trên là mâu thuẫn: Mô hình thực tiễn thường có rất nhiều chi tiết phải được bao gồm trong mô hình này và mô hình này sẽ ngày càng trở nên phức tạp. Mặt khác việc mô phỏng, phân tích thì phải đơn giản để việc thiết kế các giao thức thực thi cho mạng ad-hoc trở nên dễ dàng hơn. Như vây việc mô hình hóa tính di dộng phải cân bằng được giữa tính chi tiết và việc đơn giản hóa, đó là chỉ xem xét đến các tính năng nổi trội của mô hình chuyển động, trong khi chúng ta sẽ bỏ qua các chi tiết ít được để ý hơn. Và trong chương này chúng ta sẽ mô tả ngắn gọn những mô hình di động quan trong được sử dụng trong việc mô phỏng mạng ad-hoc Mô hình Random waypoint (RWP): Đây là mô hình thông dụng nhất được sử dụng trong mạng ad-hoc. Mô hình Random waypoint đã được giới thiệu trong một số tài liệu và đã được thực thi trong giao thức đinh tuyến DSR ( Dynamic Source Routing). Trong mô hình này mỗi node sẽ thống nhất chọn một điểm đích ngẫu nhiên (‘way point’) trong một vùng R và di chuyển tới điểm đã chọn theo một đường thẳng. Tốc độ dịch chuyển của node nằm được thống nhất chọn ngẫu nhiên trong khoảng [vmin, vmax] với vmin và vmax là tốc độ dịch chuyển nhỏ nhất và lớn nhất của các node. Khi node di chuyển đến điểm đến, sau đó nó sẽ dừng lại với một khoảng thời gian được xác định từ ban đầu. Sau đó nó sẽ đi chuyển trở lại theo cùng một khuôn mẫu. Mô hình RWP biểu diễn những sự di chuyển cá thể của node. Mỗi node di chuyển độc lập với nhau và chúng có thể di chuyển bất kỳ trong khu vực R. Ví dụ như những chuyển động tương tự được sinh ra khi những người dùng di chuyển trong một phòng lớn hay trên một môi trường bằng phẳng. Do tính phổ biến mô hình RWP đã được ngiên cứu nhiều hơn trong các tài liệu Mặc dù mô hình này còn tương đối đơn giản nhưng trong tương lai những mô hình RWP sẽ được khái quát hóa để ngày càng phù hợp với thực tế, Ví dụ mô hình RWP sẽ cho phép một node bất kỳ dừng lại trong quá trình chuyển động tới đích theo một xác suất ngẫu nhiên nào đó. Mô hình hướng ngẫu nhiên (Random direction model (RDM)). Tương tự như mô hình RWP, mô hình RDM cũng hướng theo việc mô hình hóa sự di chuyển cá nhân và có xu hướng tự do.Mô hình này sẽ được tạo ra với một vùng tròn có bán kính R, với node là trung tâm. Trong mô hình này các node sẽ chọn ngẫu nhiên một hướng trong khoảng từ [0,2π] và tốc độ ngẫu nhiên trong khoảng [vmin,vmax]. Và sau đó node sẽ di chuyển theo hướng đã được chọn và với tốc độ cũng đã được chọn. Khi nó đạt tới ranh giới R, nó sẽ chọn một hướng mới và tốc độ mới Brownian-like motion: ngược với mô hình di động RWP và RDM , những mô hình này chuyển động có sự định hướng trước (điểm đích hoặc theo hướng ), mô hình Brownian-like motion sẽ mô tả sự di chuyển một cách tự do, thi thoảng mô hình này còn được gọi là mô hình drunkardlike Trong mô hình Brownian-like motion, vị trí của một node tại một bước thời gian phụ thuộc vào vị trí của node tại thời điểm trước đó.Cụ thể, tính chất di chuyển có đinh hướng hay vận tốc di chuyển đều không được sử dụng tại mô hình này. Tính di động được mô hình hóa bằng 3 tham số sau đây: pstart, pmove, và m, Tham số đầu tiên thể hiện xác suất node ở trạng thái dừng trong toàn bộ thời gian mô phỏng, pmove thể hiện xác suất, xác suất node sẽ di chuyển trong một bước thời gian., m là tham số mô hình, tại một số mức, tốc đô: nếu một node đang di chuyển ở bước i,vị trí của nó ở bước tiếp theo i+1 là một vị trí được chọn ngẫu nhiên trong vòng bán kính là 2m với tâm là vị trí hiện thời của node. Map-based mobility: Trong tất cả các mô hình đã giới thiệu từ trước đến giờ các node được tự do di chuyển trong khu vực triển khai R. Tuy nhiên trong nhiều tình huống thực tế, các node thường bị bắt buộc di chuyển theo một đường đặc biệt nào đó. Đây là một trường hợp, chẳng hạn những chiếc xe di chuyển trên một xa lộ hay mọi người đi bộ đều di chuyển trên vỉa hè, vv. Mô hình Map based sẽ được sử dụng để mô phỏng các tình huống trên. Bước đầu tiên trong việc tạo nên mô hình Map based là thiết lập một bản đồ, đó là định nghĩa những đường di chuyển trong đó các node sẽ được phép di chuyển trên đó. Sau đó một số node có vị trí ngẫu nhiên nằm trên những con đường này và chúng sẽ di chuyển theo lộ trình đã được quy định cụ thể. Một ví dụ của mô hình map based mobilily là mô hình Freeway Mobiliy, chúng được sử dụng để mô phỏng sự di chuyển của những chiếc xe trên xa lộ, trong mô hình này một số xa lộ sẽ được xác định trong khu vực triển khai. Mỗi xa lộ sẽ bao gồm 1 con đường và có 2 hướng. Node sẽ có vị trí ngẫu nhiên trên xa lộ, và chúng sẽ di chuyển với vận tốc ngẫu nhiên, vận tốc này sẽ phụ thuộc theo thời gian vao vận tốc trước đó của nó. Nếu 2 node mà trong cùng một làn xe với một khoảng cách tối thiểu (khoảng cách an toàn) thì tốc độ của nó sẽ không được vượt quá tốc độ của node bên trên nó. Một mô hình khác của map based mobilily là mô hình Manhattan mobility, chúng được sử dụng để mô phỏng sự di chuyển … Đầu tiên Manhatta như là một bản đồ bao gồm chiều dọc và chiều ngang của những con đường sẽ được tạo ra. Các node sẽ di chuyển dọc theo những con đường theo hai hướng. Khi node di chuyển đến một chỗ cắt, nó sẽ chọn ngẫu nhiên một con đường, có thể là đi thẳng theo hướng như ban đầu hoặc có thể rẽ phải hoặc rẽ trái. Tương tự như mô hình FreeWay tốc đô hiện thời của node phụ thuộc vào tốc độ trước đó của node theo bước thời gian. Ví dụ thứ 3 của mô hình Map- based là mô hình the Obstacle mobility, trong mô hình này bản đồ được tạo ra đầu tiên là thêm các vật cản (những tòa nhà chẳng hạn) những trở ngại được thêm vào có thể được lấy một cách ngẫu nhiên hoặc dựa trên bản đồ thực tế. Một khi các công trình xây dựng được triển khai những con đường nối những công trình này sẽ được tạo ra và những node sẽ được giả định di chuyển theo những con đường này. Một tính năng thú vị của mô hình này đó là những vật cản cũng được tính toán cho việc mô phỏng tín hiệu được lan truyền trong môi trường. Nói cách khác mô hình này còn giả định được những tín hiệu sẽ bị cản bởi các vật cản trong môi trường Group-based mobility: Tất cả những mô hình được giới thiệu từ trước đều mô phỏng sự di chuyển của từng cá thể. Tuy nhiên trong nhiều tình huống các node có thể di chuyển theo một nhóm (ví dụ như một nhóm du lịch di chuyển trong thành phố) Group-based Mobility được tạo ra để mô hình những tình huống như trên.Trong mô hình Group-based Mobility một nhóm nhỏ các node mạng được coi như là những trưởng nhóm (group leaders). Những node còn lại sẽ được gán ngẫu nhiên với những trưởng nhóm tạo thàn một nhóm.Đầu tiên các nhóm trưởng sẽ ngẫu nhiên phân phối vùng triển khai R và các thành viên trong nhóm sẽ có vị trí ngẫu nhiên trong vùng R và là ‘hàng xóm’ của trưởng nhóm.Sau đó các trưởng nhóm sẽ di chuyển theo một mô hình đã được giới thiệu ở phía trên, Chẳng hạn như là RWP hay RDM. Các thành viên trong nhóm sẽ làm theo người đứng đầu, các thành viên này sẽ có hướng và tốc độ theo hướng và tốc độ của trưởng nhóm. Khi hai nhóm giao nhau, một thành viên bất kỳ có thể rời nhóm của nó và gia nhập vào một nhóm khác theo một xác suất đã biết. Chi tiết về mô hình Group-based Mobility có thể tham khảo ở một số tài liệu khác như Hong et al. 1999; Wang and Li 2002 Chương 3. Tối ưu hóa Topology 3.1. Vấn đề về vùng ảnh hưởng Trong chương này chúng ta sẽ xem xét các vấn đề để phân bố được một cấp độ truyền để tạo ra một đồ thị truyền thông với một khoảng thời gian trong khi sẽ giảm thiểu được sự tiêu thụ năng lượng. Vấn đề này được hiệu như là một vấn đề của vùng ảnh hưởng 3.1.1. Định nghĩa vấn đề Chúng ta nhắc lại rằng, thiết lập cho tập hợp những node N trên mạng, một vùng ảnh hưởng cho N là một hàm RA, hàm này sẽ gán cho mỗi node thuộc N một vùng ảnh hưởng RA(u) với 0 < RA(u) ≤ rmax với rmax là vùng ảnh hưởng lớn nhất. Chú ý rằng, dưới giả thuyết là mô hình Path Loss được sử dụng cho mọi Node, và hiệu ứng Shadowing/fading không được xem xét, và vùng truyền (Transmitting Range) và cấp độ truyền (transmit power level) là những khái niệm tương đương. Hàm RA trước đây được định nghĩa như là các quy tắc về phạm vi thay vi sức mạnh và chúng ta vẫn giữ những quy ước này. Những vấn đề về Range Assigment được định nghĩa như sau: Định nghĩa 3.1.1(Vấn đề RA): Cho N là tập hợp những node trong không gian d chiều (d= 1, 2, 3) Một hàm range assigment được xác định tương đương như là một đồ thị truyền thông với những kết nối mạnh, và là hàm kết nối tất cả các RA với một khoảng cách nhỏ nhất, với là độ suy giảm cường độ theo khoảng cách. Chi phí đo c() được sử dụng trong định nghĩa vấn đề RA là tổng cấp độ truyền( Transmit Power levels) được sử dụng tại các node trong mạng. Vì vậy một vấn đề của RA có thể thực sự được bắt đầu với việc tìm một RA ‘minimal’ với những node, với RA này các node sẽ kết nối với nhau để tạo thành một đồ thị truyền thông, và minimal ở đây có thể được hiểu là ‘chi phí năng lượng nhỏ nhất’. Bên cạnh việc giảm thiểu sự tiêu thụ năng lượng việc kết nối RA với sự tiêu thụ năng lượng nhỏ này sẽ giúp phần tăng thêm khả năng của mạng 3.1.2. Vấn đề RA trong những mạng một chiều (One-Dimensional Networks). Trong phần này chúng ta sẽ giới thiệu một số thuật toán cho việc tìm kiếm những giải pháp cho vấn đề RA.Trước khi trình bày thuật toán chúng ta cần định nghĩa một cách sơ bộ Cho N là một tập hợp những điểm (Node) nằm trên một đường thẳng.Không mất tính tổng quát, chúng ta giả sử rằng các node được sắp xếp tăng dần tùy thuộc theo tọa độ trong không gian, chẳng hạn như u1 là node bên trái nhất và un là node bên phải nhất. Cho một bộ những node và một RA, chúng ta gọi những cạnh (ui, uj) trong đồ thị truyền thông thu được là một backward nếu mà i > j, có nghĩa là cạnh đi từ phải sang trái. Với bất kỳ i, j nào (1 i < j n) chúng ta định nghĩa tập hợp Ei,j gồm tất cả các cạnh backward có điểm đầu cuối thuộc {ui , uj}, Ei,j = {(us, ur) : i r < s j} Một số cạnh backward được giới thiệu trong hình bên dưới. (Những cạnh bôi đen là những cạnh backward) Hình 4: Các cạnh backward Thuật toán cho việc tìm kiếm một giải pháp tối ưu dựa trên nền tảng là những phép đệ quy. Cho một RA tối ưu kết nối cho các node (u1, uk) với 1 k <n , sau đó chúng ta sẽ xây dựng được một RA tối ưu kết nối cho (u1, uk+1). Tư tưởng chính của thuật toán này là khi chúng ta đã có một RA tối ưu với k node là RAk thì RA tiếp theo có thể được xác định. Giả sử chi phí của RAk là 0 (giả thiết, nghĩa là c(RAk) cũng bằng 0) và khi có thêm một node gia nhập thêm vào thì chi phí của RAk+1 sẽ được tăng lên một giá trị đã được xác định điều này được thể hiện trong định nghĩa sau: Định nghĩa 3.2.1 (RA increamental cost) Cho N = {u1, . . . , un} là một tập hợp các node và E là bộ những cạnh giữa những node trong N. RA được sinh ra bởi E được gọi là RAE , RAE là “minimal assignment” khi RAE(ui)với bất kỳ một cạnh có hướng (ui, uj) E.Chi phí tăng thêm của range assignment liên quan tới E được gọi là cE(RA), được xác định như sau: cE(RA) = . Chúng ta gọi những cạnh trong E là ‘free of cost ’ đối với range assignment RA. Những giả thiết dựa trên nền tảng của thuật toán quay lui, với bất kỳ j k và bất kỳ l k, tồn tại một Range assigment RA với một chi phí nhỏ nhất trong số các đồ thị truyền thông sẽ có các thuộc tính sau đây: - Giữa một cặp node bất kỳ đều có đường tồn tại - Có một cạnh nối trực tiếp giữa ui và ul, l<=i <=k - Với bất kỳ một cạnh (backward) trong E thì đều free of cost với RA Cho (N’, E) là một đồ thị kết nối tất cả các node N’ và có các cạnh là E, và N’ ⊂ N, và khi đồ thị này nhận thêm một node v trong N chúng ta gọi là reciever node. Một Range assigment được gọi là total cho ((N’ , E), v) khi và chỉ khi: - Đồ thị được tạo ra bởi N’ node thu được bằng cách thêm vào các cạnh của E tạo nên một kết nối mạnh nghĩa là (RA(ui) ≥ δ(ui, uj )) - Đều tồn tại cạnh giữa (u,v ) với ui∈ N và kết nối giữa v và ui là mạnh nghĩa là (RA(ui) ≥ δ(ui, v )) Chi phí của cho tổng Range assigment của ((N’ , E), v) là chi phí được tăng thêm liên quan đến RAE, hay như định nghĩa về RA increamental cost là cE(RA). Như vậy tổng cộng range assigment cho ((N’ , E), v) với một chi phí nhỏ nhất được gọi là tối ưu . Trong phần sau đây chúng ta gọi Feas((N’ , E), v) là tập hợp những range assigment Feas((N’ , E), v) và Opt ((N’ , E), v) là tập hợp những optimal range assigment. Cuối cùng, cho u ∈ N và một đại lượng xác thực là r, chúng ta coi rằng Opt((N’, E), v, (u, r))) là tập hợp những range assigment với chi phí nhỏ nhất và RA(u) = r. Thuật toán Optimal1dRA để tìm ra giải pháp tối ưu cho vấn đề RA được trình bày sau đây: 1. Khởi tạo 1.1 Cho RAi có Range assigment là RAi (u1) = δ(u1, ui), và RAi(u1) = 0 nếu i =0 1.2 Nếu không for i = 2 … n khởi tạo Opt(({u1}, ∅), ui) = RAi 2. Bước k 2.1 Giả sử chúng ta biết Opt(({u1, . . . , uk}, Ei,k), ul) ,với bất kỳ 1 i < k và k l n. 2.2 Với j, m bất kỳ , 1 ≤ j ≤ k + 1 ≤ m ≤ n 2.3. Xét tất cả các giá trị có thể của RA(uk+1) (tương tự với k+2 ) 2.4 for với mỗi giá trị của r, tìm một range assignment trong Opt(({u1, . . . , uk}, Ej,k+1), uk+1, (uk+1, r)) 2.5. Nếu có chi phí nhỏ hơn so với hiện thời cho j , m thì lưu RA 2.6. Kết thúc bước k, chúng ta biết một range assignment Opt(({u1, . . . , uk+1}, Ei,k+1), ul), với bất kỳ 1 ≤ i ≤ k + 1 ≤ l ≤ n 3. ở bước n Một Range assignment tối ưu chính là một trong Opt(({u1, . . . , un}, ∅), un) Tư tưởng chính của thuật toán này là: đầu tiên khởi tạo một RAi(u1) nếu i là 1 thì RA1(u1) = 0 Nếu i khác 1 thì tìm các RA tối ưu của u1 với bất kỳ 1 node khác. Trong bước đệ quy giả sử chúng ta đã biết Opt(({u1, . . . , uk}, Ei,k), ul) với bất kỳ 1 i k và k l n. với mỗi node thêm vào chúng ta tìm được một RA tối ưu khi thêm vào mỗi node đó Tại bước cuối cùng khi thêm một node cuối cùng chúng ta sẽ tìm được một RA tối ưu nhất cho toàn bộ node N. Các nhà nghiên cứu đã chứng minh được độ phức tạp của thuật toán này là O(n4). So sánh thuật toán Optimal1dRA khi tìm kiếm một RA tối ưu với giả thiết là các Transmitting Range là bằng nhau thì thuật toán sẽ đơn giản hơn rất nhiều . 3.1.3. Vấn đề RA trong mạng 2 và 3 chiều Trong phần trước, chúng ta đã phân tích được vấn đề RA trong mạng 1 chiều. So với vấn đề trong mạng 1 chiều thì vấn đề tính toán trở nên phức tạp hơn nhiều, sự tính toán này cũng là một vấn đề lớn trong mạng 2 và 3 chiều này. Mặc dù giải pháp cho mạng 2 và 3 chiều là một công việc khó khăn, nhưng một giải pháp tối ưu xấp xỉ có thể dễ dàng được tính toán bằng cách xây dựng một Minimum Spaining Tree (MST) trên các node. Sự xây dựng một RA được tiến hành như sau: 1. Cho N= {u1, . . . , un} là một tập hợp những điểm (Node) trong không gian mạng 2 hoặc 3 chiều 2. Xây dựng một đồ thị vô hướng G = (N, E), với các cạnh là (ui, uj) ∈ E 3. Tìm một MST của G 4. Xác đinh một RAT với RAT(ui) = MAXj|(ui,uj)∈Tδ(ui, uj). Một ví dụ về cây MST và tương ứng với những RAT được miêu tả trong hình bên dưới Hình 5: Minimum Spanning Tree Thời gian xây dựng RAT là O(n2) (Độ phức tạp của thuật toán khi xây dựng MST với n node) Định lý 3.2.3: (Kirousis et al. 2000) Cho một tập hợp những điểm (nodes) trong không gian 2 hoặc 3 chiều, và cho RAT được định nghĩa như trên, cho là một optimal range assignment với vấn đề RA thì c(RAT) < 2c(). Chứng minh: Việc chứng minh được thực hiện qua hai bước. Trước tiên chúng ta chứng minh c() lớn c(T) nghĩa là chi phí của RA lớn hơn chi phí cả MST. Và sau đó chúng ta sẽ chứng minh c(RAT) < 2c(). 3.1.4. Vấn đề về tính đối xứng Trong vấn đề về RA chúng ta đã quan tâm đến việc thiết lập một đồ thị giao tiếp với những kết nối mạnh. Từ việc những node có những vùng ảnh hưởng khác nhau, những liên kết vô hướng xuất hiện, và chúng có thể đảm bảo cho sự kết nối mạnh. Mặc dù việc triển khai việc liên kết không dây vô hướng là một công việc có thể thực thi được nhưng lợi ích mang lại của nó đang là một vấn đề phải nghi ngờ. Những vấn đề của liên kết không dây vô hướng được đề cập trong tài liệu Marina and Das 2002 Hầu hết các giao thức định tuyến cho mạng ad-hoc ( DSC, AODV) đều dựa trên nền tảng là sự ngầm định của liên kết không dây đều có tính 2 chiều. Điều này cũng đang được áp dụng tương tự với sự thực thi của tầng MAC trong chuẩn IEEE 802.11 nó chính là cơ sở của việc trao đổi các thông điệp RequestToSend/ClearToSend: Khi một node u muốn send một bản tin tới v trong transmitting range nó sẽ gửi một RTS tới v và sẽ đợi CTS từ v gửi lại. Nếu u không nhận được CTS trong một khoảng thời gian giới hạn nào đó, thì bản tin được gửi sẽ bị ngắt và sau đó nó sẽ cố gắng gửi lại sau một khoảng thời gian nào đó. Nếu liên kết gữa node u và node v là vô hướng, một trong hai bản tin RTS hoặc CTS là không nhận được và sự liên kết ở đây cũng là không có. Việc hỗ trợ liên kết vô hướng ngầm định rằng có những node trung gian sẽ đại diện cho u hoặc v nhận và gửi các bản tin RTS và CTS. Ngoài ra một cơ chế truy cập khác( ví dụ như cơ chế phát hiện xung đột thay vì tránh xung đột) cũng nên được sử dụng. Dù sao thì việc hỗ trợ liên kết không dây vô hướng sẽ tạo ra một cuộc cách mạng thay đổi những giao thức đang được thực thi hiện thời trong chuẩn IEEE 802.11 Những lý do trên đây là động cơ thúc đẩy các nhà khoa học nghiên cứu những hạn chế trong vấn đề RA, và điều chắc chắn rằng tính đối xứng bắt buộc phải được thêm vào trong đồ thị truyền thông tạo ra. Chi tiết hơn, hai vấn đề sau đây đã được định nghĩa và đã được nghiên cứu. 3.4.1 (Vấn về WSRA): Cho N là một tập hợp những node trong không gian d chiều, với d = 1, 2, 3. Cho RA là một vùng ảnh hưởng cho N và G là là một đồ thị liên thông có hướng. Đồ thị con đối xứng của G được xác định là GS, thu được bằng cách bỏ đi các liên kết có hướng, vấn đề WRSA là xác định một hàm Range assigment RA khi mà GS được kết nối và là nhỏ nhất với α là độ suy giảm cường độ theo khoảng cách. 3.4.2 Vấn đề SRA: Cho N là một tập hợp những node trong không gian d chiều, với d = 1, 2, 3. Một range assignmnet RA cho N được gọi là đối xứng nếu nó sinh ra một đồ thị liên thông trong đó đồ thị này chỉ bao gồm những liên kết 2 chiều. Đó là RA(ui) ≥ δ(ui, uj) ⇔RA(uj) ≥ δ(ui, uj). Vấn đề Symmetric Range Assignment (RSA) là xác định một hàm RA khi có một đồ thị liên thông có hướng được kết nối và là nhỏ nhất với α là độ suy giảm cường độ theo khoảng cách. Hình 6: SRA và WSRA Hình trên thể hiện sự khác nhau trong việc yêu cầu tính đối xứng trong vấn đề WSRA và SRA. Trong WSRA những liên kết vô hướng là được cho phép nhưng chúng không đại diện cho việc kết nối . Trong RSA tất cả những liên kết trong đồ thị liên thông phải có 2 hướng: node u , v và w phải tăng transmitting range để thỏa mãn những yêu cầu về tính đối xứng. Chú ý rằng những yêu cầu về tính đối xứng 2 phiên bản này của vấn đề: trong vấn đề WSRA(Weakly Symmetric Range Assignment) trong đồ thị liên thông có thể bao gồm những liên kết vô hướng tuy nhiên chúng không đại diện cho tính kết nối. Còn đối với vấn đề RSA đồ thị liên thông chỉ bao gồm các liên kết 2 chiều. Đây là một yêu cầu chính tron đồ thị liên thông.Các bạn có thể xem hình bên trên để có thể hiêu hơn. Động cơ thúc đẩy cho việc nghiên cứu WSRA bắt nguồn từ việc quan sát những gì thực sự quan trong trong việc thiết kế mạng ad-hoc đó là tạo nên một khung của mạng. Hay nói cách khác trong một mạng có thể có các liên kết tồn tại mà tính 2 chiều không được đảm bảo, những liên kết này có thể được bỏ qua khi mạng không có các kết nối này. 3.1.4.1. Vấn đề SRA trong mạng 1 chiều Trong trường hợp các node nằm trong cùng một đường thẳng, một SRA cho tập hợp các node đó có thể được xây dựng như sau: Sắp xếp các node theo tọa độ không gian của chúng, cho {u1, . . . , un} là kết quả của sự sắp xếp này. Gán cho node u1 một transmitting range δ(u1, u2) node un một transmitting range δ(un−1, un), và node ui một transmitting range bằng Max{δ(ui−1, ui),δ(ui, ui+1)} Bổ sung transmitting range vào một số node để đảm bảo tính đối xứng: với mỗi cạnh vô hướng(ui, uj) trong đồ thị liên thông được tạo ra bởi bước trước đó bằng cách thêm transmitting range vào node uj sao cho nó có thể tiếp cận được với ui, quá trình này được lặp lại cho đến khi tất cả các cạnh trong đồ thị đều có tính thuận nghịch. Chúng ta có thể nhìn thấy ngay được là, Range assignment RA được xây dựng tùy theo chiến lược mô tả ở phía trên, để tạo ra một đồ thị liên thông kết nối trong đó tất cả các liên kết đều có tính 2 chiều. Để chứng minh rằng RA này là tối ưu, thì trong khi quan sát rằng để đạt được kết nối thì node phải được kết nối với node bên phải và bên trái của node hàng xóm gần nó nhất. Hơn nữa các thủ tục tăng ở bước 3 sẽ tăng một transmitting range lên một giá trị nhỏ nhất để có thể thỏa mãn tính đối xứng của transmitting range. Độ phức tạp tính toán của thuật toán cho vấn đề được nêu ở phía trên là O(n log n),so sánh với độ phức tạp của thuật toán cho vấn đề về phiên bản không giới hạn là O(n4) thì độ phức tạp của thuật toán này là thấp hơn rất nhiều. Như vậy chúng ta có thể kết thúc vấn đề tính đối xứng trong range assignment với mạng 1 chiều. 3.1.4.2. Vấn đề SRA trong mạng 2 và 3 chiều Trong chương này, chúng ta sẽ cho thấy rằng, trái ngược với trường hợp trong mạng 1 chiều, trong mạng 2 và 3 chiều những điều kiện về tính đối xứng sẽ không làm ảnh hưởng tới độ phức tạp của việc tính toán những vấn đề. Người đọc sẽ thấy rằng sự chứng minh là khá dài dòng và phức tạp. Những khó khăn của việc chứng minh bắt đầu từ thực tế là khi nghiên cứu về tính phức tạp của các vấn đề mạng ad-hoc thì thì hình dạng của mạng là không thể được bỏ qua. Chúng ta đã chứng minh rằng những node có thể thực sự được đặt trong không gian 2 hay 3 chiều trong đó bất kỳ những trường hợp đặc biệt nào cũng có thể được chuyển thành vấn đề kiểm soát đặc biệt SRA. Việc này thường được thực hiện bằng cách sử dụng một geometric hay thuật ngữ