Luận văn thạc sĩ allocation de canaux dans les réseaux maillés sans fil conflits directionnels bidirectionnels et algorithmes luận văn ths công nghệ thông tin

Luận văn thạc sĩ: Nghiên cứu cấp phát kênh trong mạng lưới không dây, giải quyết xung đột hướng hai chiều. Thuật toán công nghệ thông tin.

• Tác giả: Assadillah Youssouf
• Người hướng dẫn: PTS. Anthony Busson
• Trường học: Université National De Hanoi (UNH)
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Allocation De Canaux Dans Les Réseaux Maillés Sans Fil : Conflits Directionnels-Bidirectionnels Et Algorithmes
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Tóm tắt

I. Khám phá luận văn thạc sĩ về cấp phát kênh mạng ma trận

Luận văn thạc sĩ với chủ đề "Allocation de canaux dans les réseaux maillés sans fil: Conflits Directionnels-Bidirectionnels et algorithmes" đi sâu vào một trong những thách thức cốt lõi của ngành Công nghệ Thông tin hiện đại. Nghiên cứu này tập trung vào bài toán cấp phát kênh (channel assignment) trong mạng ma trận không dây (Wireless Mesh Networks - WMN), một công nghệ nền tảng cho việc triển khai mạng nhanh chóng và chi phí thấp. Mục tiêu chính của luận văn là phân tích và đề xuất các giải pháp nhằm tối ưu hóa hiệu năng mạng thông qua việc quản lý kênh tần số hiệu quả. Cụ thể, nghiên cứu làm rõ tác động của hướng lưu lượng (traffic direction) – một yếu tố thường bị bỏ qua – lên sự xuất hiện của xung đột kênh. Bằng cách phân biệt rõ ràng giữa xung đột một chiều (directionnel) và xung đột hai chiều (bidirectionnel), luận văn mở ra một hướng tiếp cận mới để giảm thiểu nhiễu (interference mitigation). Nghiên cứu này không chỉ dừng lại ở việc tổng hợp lý thuyết mà còn tiến hành các thử nghiệm thực tế thông qua mô phỏng NS-2/NS-3, cung cấp những bằng chứng xác thực về hiệu quả của các thuật toán được đề xuất. Luận văn là một tài liệu tham khảo giá trị cho các nhà nghiên cứu, kỹ sư mạng và sinh viên cao học quan tâm đến việc cải thiện dung lượng và độ tin cậy của các mạng ad-hoc không dây.

1.1. Tổng quan về Wireless Mesh Networks WMN và vai trò

Wireless Mesh Networks (WMN) là một kiến trúc mạng không dây mà các nút mạng (nodes) kết nối trực tiếp, động và phi tập trung với nhau để định tuyến dữ liệu. Mỗi nút có thể hoạt động như một router, giúp chuyển tiếp dữ liệu cho các nút khác. Ưu điểm của WMN là khả năng tự cấu hình, tự phục hồi và dễ dàng mở rộng, khiến nó trở thành giải pháp lý tưởng cho các ứng dụng như mạng cộng đồng, giám sát môi trường, và kết nối internet ở các khu vực khó tiếp cận. Vai trò của WMN trong bối cảnh hiện tại là vô cùng quan trọng, đặc biệt trong các mạng cảm biến không dây và hạ tầng IoT.

1.2. Tầm quan trọng của bài toán channel assignment tối ưu

Bài toán channel assignment (cấp phát kênh) là quá trình gán các kênh tần số khác nhau cho các giao diện vô tuyến trên mỗi nút mạng. Một chiến lược cấp phát kênh tối ưu giúp giảm đáng kể nhiễu đồng kênh và nhiễu kênh lân cận. Điều này trực tiếp cải thiện hiệu quả sử dụng phổ tần (spectrum efficiency), tăng thông lượng (throughput) và giảm độ trễ (delay) của toàn mạng. Ngược lại, việc cấp phát kênh không hiệu quả sẽ gây ra xung đột, dẫn đến mất gói tin và suy giảm nghiêm trọng hiệu năng mạng. Do đó, tìm ra thuật toán cấp phát kênh hiệu quả là chìa khóa để khai thác tối đa tiềm năng của WMN.

1.3. Hướng nghiên cứu chính Xung đột một chiều và hai chiều

Điểm mới của luận văn là tập trung vào việc phân tích sự khác biệt giữa xung đột phát sinh từ luồng dữ liệu một chiều (directional) và hai chiều (bidirectional). Trong luồng một chiều, dữ liệu chỉ di chuyển theo một hướng trên một liên kết. Trong luồng hai chiều, dữ liệu di chuyển qua lại. Luận văn chỉ ra rằng luồng hai chiều có xu hướng tạo ra nhiều xung đột hơn. Việc hiểu rõ bản chất của hai loại xung đột này cho phép phát triển các thuật toán phân tán thông minh hơn để xử lý xung đột (conflict resolution), từ đó nâng cao hiệu suất tổng thể.

II. Thách thức trong allocation de canaux Xung đột và nhiễu

Việc thực hiện allocation de canaux trong thực tế phải đối mặt với nhiều thách thức phức tạp. Vấn đề lớn nhất là bài toán tìm ra phương án cấp phát kênh tối ưu đã được chứng minh là một bài toán NP-khó (NP-complete). Điều này có nghĩa là không tồn tại thuật toán nào có thể tìm ra lời giải hoàn hảo trong thời gian đa thức khi quy mô mạng tăng lên. Do đó, các nghiên cứu phải tập trung vào các thuật toán heuristic hoặc thuật toán tham lam để tìm ra lời giải gần tối ưu. Xung đột (conflict) là trở ngại chính, xảy ra khi các liên kết gần nhau sử dụng cùng một kênh tần số và truyền dữ liệu đồng thời. Luận văn đã phân tích kỹ các mô hình xung đột, bao gồm Protocol Model và Physical Model, nhưng tập trung chủ yếu vào Graph Model vì tính thực tiễn cao hơn. Mô hình này xác định xung đột dựa trên khoảng cách về số bước nhảy (hops) giữa các liên kết. Theo nghiên cứu, hai liên kết được coi là xung đột nếu chúng cách nhau dưới ba bước nhảy. Tuy nhiên, luận văn cũng chỉ ra rằng quy tắc này không phải lúc nào cũng đúng và phụ thuộc nhiều vào hướng lưu lượng. Việc không xử lý xung đột hiệu quả sẽ dẫn đến giảm thiểu nhiễu thất bại, làm giảm đáng kể throughput và delay, gây ảnh hưởng tiêu cực đến trải nghiệm người dùng cuối.

2.1. Phân tích bài toán NP khó trong cấp phát kênh động

Bài toán cấp phát kênh động tối ưu được xếp vào lớp NP-khó vì không gian tìm kiếm lời giải tăng theo hàm mũ với số lượng nút và kênh. Ví dụ, với N nút và K kênh, số lượng phương án cấp phát có thể trở nên khổng lồ, khiến việc duyệt toàn bộ để tìm ra phương án tốt nhất là bất khả thi. Các thuật toán như CLICA (Connected Low Interference Channel Assignment) và MESTIC được đề xuất để giải quyết vấn đề này bằng các phương pháp tiếp cận heuristic, ưu tiên các nút dựa trên tải lưu lượng hoặc khoảng cách đến gateway, nhưng vẫn chỉ mang lại kết quả gần tối ưu.

2.2. Các mô hình xung đột Graph Model và Physical Model

Luận văn đề cập hai mô hình chính để xác định xung đột. Physical Model là mô hình thực tế nhất, xác định xung đột dựa trên tỷ số tín hiệu trên nhiễu và tạp âm (SINR). Tuy nhiên, việc thu thập thông tin SINR theo thời gian thực rất phức tạp. Ngược lại, Graph Model, dựa trên lý thuyết đồ thị, đơn giản hơn và chỉ yêu cầu thông tin về topo mạng. Mô hình này định nghĩa xung đột khi khoảng cách (tính bằng số bước nhảy) giữa hai liên kết nhỏ hơn một ngưỡng nhất định (thường là 2 hoặc 3). Luận văn chọn Graph Model làm nền tảng cho các phân tích ban đầu vì tính khả thi trong triển khai.

2.3. Hậu quả của nhiễu đến hiệu quả sử dụng phổ tần

Nhiễu là hệ quả trực tiếp của việc cấp phát kênh không hợp lý. Khi hai luồng truyền trên cùng một kênh gây nhiễu lẫn nhau, các gói tin có thể bị hỏng, dẫn đến yêu cầu truyền lại. Quá trình này không chỉ làm tăng độ trễ mà còn lãng phí băng thông, làm giảm hiệu quả sử dụng phổ tần. Về lâu dài, tình trạng nhiễu cao có thể gây ra hiện tượng nghẽn mạng, làm sập đổ hiệu năng của toàn bộ mạng ad-hoc không dây. Do đó, việc giảm thiểu nhiễu là mục tiêu hàng đầu của bất kỳ thuật toán cấp phát kênh nào.

III. Phương pháp tiếp cận thực nghiệm Thuật toán Glouton Évolutif

Để đánh giá tác động của hướng lưu lượng, luận văn đã triển khai một phương pháp tiếp cận thực nghiệm dựa trên thuật toán "glouton évolutif" (tham lam tiến hóa). Thuật toán này được chọn vì khả năng tìm kiếm giải pháp tốt một cách nhanh chóng. Nguyên tắc hoạt động của nó là bắt đầu với một cấu hình mạng chưa được cấp phát kênh. Sau đó, thuật toán xác định các đường đi không giao nhau giữa nguồn và đích, sắp xếp chúng theo thứ tự ưu tiên dựa trên dung lượng tiềm năng. Quá trình channel assignment diễn ra tuần tự trên các liên kết của những đường đi này. Đối với mỗi liên kết, kênh được chọn là kênh tối đa hóa một hàm lợi ích, được định nghĩa dựa trên băng thông và số lượng xung đột tiềm tàng. Luận văn đã cải tiến thuật toán này để tích hợp yếu tố hướng lưu lượng, cho phép so sánh trực tiếp hiệu năng giữa hai kịch bản: chỉ có luồng một chiều và chỉ có luồng hai chiều. Các kịch bản này được tạo ra và sau đó được xuất thành tệp cấu hình để chạy mô phỏng trên NS3. Phương pháp này cung cấp một cơ sở định lượng để chứng minh rằng mạng với luồng một chiều gặp ít xung đột hơn và đạt được đánh giá hiệu năng tốt hơn về tỷ lệ mất gói.

3.1. Triển khai thuật toán glouton évolutif tối ưu

Thuật toán "glouton évolutif" được triển khai trong một trình giả lập viết bằng C. Trình giả lập này có khả năng tạo ra các topo mạng ngẫu nhiên, thực hiện cấp phát kênh theo logic của thuật toán, và thiết lập các luồng lưu lượng CBR (Constant Bit Rate) qua giao thức UDP. Điểm mấu chốt là hàm lợi ích, cân bằng giữa việc chọn kênh có băng thông cao và kênh ít gây xung đột nhất với các liên kết lân cận trong vòng 3 bước nhảy. Phiên bản tối ưu của thuật toán sẽ duyệt qua nhiều khả năng và chọn ra phương án tốt nhất.

3.2. Đánh giá hiệu năng dựa trên số bước nhảy hops

Trong các thí nghiệm ban đầu, xung đột được xác định dựa trên số bước nhảy theo Graph Model. Cụ thể, hai liên kết e1 và e2 được coi là xung đột nếu chúng dùng chung kênh và khoảng cách nhỏ nhất giữa các nút đầu cuối của chúng nhỏ hơn hoặc bằng 3. Mặc dù mô hình này đơn giản, nó đủ hiệu quả để cho thấy sự khác biệt rõ rệt về số lượng xung đột giữa hai loại lưu lượng. Kết quả đánh giá hiệu năng cho thấy luồng hai chiều tạo ra một mạng lưới xung đột dày đặc hơn đáng kể.

3.3. Kết quả ban đầu từ mô phỏng NS 3 với hai luồng traffic

Các kết quả từ mô phỏng NS-3 ban đầu rất đáng chú ý. Trong các mạng có quy mô nhỏ (dưới 6 nút), hiệu năng của cả hai loại lưu lượng gần như tương đương. Tuy nhiên, khi số nút tăng lên, hiệu năng của mạng hai chiều suy giảm nhanh chóng. Luồng hai chiều tuy có khả năng truyền gói tin cao hơn nhưng tỷ lệ nhận thành công (Packet Delivery Ratio - PDR) lại thấp hơn nhiều do xung đột và nhiễu. Ngược lại, luồng một chiều duy trì được PDR ổn định hơn, chứng tỏ khả năng giảm thiểu nhiễu tốt hơn.

IV. Bí quyết mô hình hóa toán học Xử lý xung đột hiệu quả

Một đóng góp quan trọng của luận văn là việc xây dựng một mô hình toán học mới để phân tích xung đột. Thay vì chỉ dựa vào số bước nhảy, mô hình này xem xét khoảng cách hình học thực tế giữa các nút, mang lại độ chính xác cao hơn. Mô hình giả định các nút được phân bố ngẫu nhiên trong không gian theo một quy trình điểm Poisson. Lý thuyết đồ thị và xác suất được sử dụng để tính toán số lượng xung đột trung bình và dung lượng mạng kỳ vọng. Trong mô hình này, một xung đột xảy ra nếu hai bộ phát (transmitter) nằm trong bán kính nhiễu của nhau. Luận văn đã xây dựng các công thức riêng để tính xác suất xung đột và dung lượng trung bình cho cả trường hợp luồng một chiều và hai chiều. Mô hình toán học này đã chứng minh một cách chặt chẽ rằng luồng hai chiều về bản chất tạo ra một "vùng xung đột" lớn hơn. Cụ thể, vùng xung đột trong trường hợp hai chiều là hợp của hai hình tròn bán kính nhiễu từ hai nút của liên kết, trong khi trường hợp một chiều chỉ xét một hình tròn. Kết quả từ mô hình này hoàn toàn tương thích với các kết quả mô phỏng mạng trước đó, củng cố thêm kết luận về lợi thế của luồng một chiều trong việc xử lý xung đột.

4.1. Ứng dụng lý thuyết đồ thị và quy trình điểm Poisson

Quy trình điểm Poisson được sử dụng để mô hình hóa vị trí ngẫu nhiên của các nút mạng trên một mặt phẳng. Ưu điểm của phương pháp này là nó cho phép tính toán xác suất có k nút trong một khu vực nhất định một cách dễ dàng. Kết hợp với lý thuyết đồ thị, mô hình có thể xác định các liên kết tiềm năng và các vùng nhiễu xung quanh chúng. Điều này tạo ra một nền tảng toán học vững chắc để phân tích hiệu quả sử dụng phổ tần một cách định lượng.

4.2. Tính toán xác suất và số xung đột trung bình

Dựa trên mô hình Poisson, luận văn đã suy ra các công thức tường minh để tính xác suất có k xung đột tại một bộ phát hoặc một bộ thu. Từ đó, số xung đột trung bình (E[K]) cũng được tính toán. Kết quả cho thấy số xung đột trung bình trong trường hợp luồng hai chiều luôn lớn hơn hoặc bằng trường hợp luồng một chiều. Cụ thể, tỷ lệ xung đột giữa hai trường hợp phụ thuộc vào diện tích vùng nhiễu, và vùng nhiễu của luồng hai chiều lớn gần gấp đôi.

4.3. Ước tính dung lượng mạng throughput cho mỗi trường hợp

Dung lượng của một liên kết được mô hình hóa bằng cách chia băng thông gốc cho tổng số các liên kết xung đột (bao gồm chính nó). Dung lượng trung bình của mạng (E[C]) được tính toán dựa trên phân phối xác suất của số xung đột. Các đường cong biểu diễn dung lượng trung bình cho thấy rằng với cùng một mật độ nút, mạng một chiều luôn đạt được dung lượng cao hơn mạng hai chiều. Điều này khẳng định rằng việc giảm xung đột có tác động trực tiếp đến việc tối ưu hóa hiệu năng mạng.

V. So sánh hiệu năng Luồng traffic một chiều và hai chiều

Phần đánh giá hiệu năng là trọng tâm của luận văn, nơi các kết quả lý thuyết và mô phỏng được tổng hợp để đưa ra kết luận cuối cùng. So sánh trực tiếp giữa luồng traffic một chiều và hai chiều được thực hiện trên nhiều phương diện: dung lượng truyền, dung lượng nhận, tỷ lệ giao nhận gói tin (PDR), và ảnh hưởng của các tham số như mật độ nút, khoảng cách và độ trễ. Các mô phỏng NS-2/NS-3 được thiết kế cẩn thận để cô lập ảnh hưởng của hướng lưu lượng. Kết quả nhất quán cho thấy: luồng hai chiều cho phép tổng dung lượng truyền (số gói tin gửi đi) cao hơn do cả hai nút trên một liên kết đều có thể gửi dữ liệu. Tuy nhiên, đây là một lợi thế không bền vững. Do số lượng xung đột cao hơn, tỷ lệ gói tin bị mất trên đường truyền cũng cao hơn đáng kể. Ngược lại, luồng một chiều có dung lượng truyền thấp hơn nhưng lại đạt được dung lượng nhận (số gói tin đến đích thành công) cao hơn. Điều này chứng tỏ giảm thiểu nhiễu trong mạng một chiều hiệu quả hơn, giúp tối ưu hóa hiệu năng mạng thực tế. Đặc biệt, khi mật độ nút tăng lên, lợi thế của luồng một chiều càng trở nên rõ rệt.

5.1. Phân tích throughput và delay qua mô phỏng NS 2 NS 3

Các biểu đồ kết quả mô phỏng cho thấy rõ ràng sự khác biệt về throughput và delay. Mạng hai chiều ban đầu có throughput truyền cao hơn nhưng nhanh chóng bị bão hòa và sụt giảm khi số nút tăng. Ngược lại, mạng một chiều duy trì được throughput nhận ổn định hơn. Về độ trễ, mạng hai chiều cũng có xu hướng delay cao hơn do các gói tin phải chờ đợi và truyền lại thường xuyên hơn. Đây là bằng chứng thực nghiệm mạnh mẽ về sự đánh đổi giữa khối lượng truyền và độ tin cậy.

5.2. Luồng một chiều Giảm thiểu nhiễu và tỷ lệ mất gói thấp

Ưu điểm cốt lõi của luồng một chiều nằm ở khả năng giảm thiểu nhiễu. Vì mỗi liên kết chỉ có một bộ phát hoạt động tại một thời điểm, số lượng nguồn gây nhiễu tiềm năng giảm đi. Điều này dẫn đến tỷ lệ mất gói thấp hơn, đặc biệt trong các kịch bản mạng dày đặc. Việc sử dụng ăng ten định hướng (directional antennas) có thể khuếch đại thêm lợi thế này, mặc dù luận văn không đi sâu vào khía cạnh này. Mạng một chiều phù hợp cho các ứng dụng yêu cầu độ tin cậy cao như streaming video hoặc thu thập dữ liệu từ mạng cảm biến không dây.

5.3. Luồng hai chiều Tăng lưu lượng truyền nhưng nhiều xung đột

Luồng hai chiều tận dụng kênh truyền tốt hơn về mặt lý thuyết bằng cách cho phép cả hai nút giao tiếp. Điều này làm tăng tổng lưu lượng gói tin được đưa vào mạng. Tuy nhiên, cái giá phải trả là sự gia tăng đột biến của xung đột. Mỗi liên kết hai chiều hoạt động như hai nguồn nhiễu tiềm năng. Khi không có đủ kênh tần số riêng biệt, các liên kết này sẽ cạnh tranh gay gắt, dẫn đến hiệu ứng "thảm họa" về hiệu năng. Trường hợp này chỉ hiệu quả khi mạng có mật độ thưa hoặc có số lượng kênh khả dụng rất lớn.

VI. Kết luận luận văn và định hướng phát triển trong tương lai

Luận văn thạc sĩ về "Allocation de canaux trong mạng ma trận không dây" đã hoàn thành xuất sắc các mục tiêu đề ra. Nghiên cứu đã chỉ ra một cách thuyết phục rằng hướng của lưu lượng là một yếu tố quan trọng ảnh hưởng đến sự xuất hiện của xung đột và hiệu năng tổng thể của mạng. Kết luận chính là luồng traffic một chiều, mặc dù có vẻ kém hiệu quả hơn về mặt lý thuyết, lại mang lại hiệu suất thực tế tốt hơn trong hầu hết các kịch bản nhờ khả năng giảm thiểu nhiễu và hạn chế xung đột. Trong khi đó, luồng hai chiều làm tăng đáng kể dung lượng truyền nhưng phải trả giá bằng tỷ lệ mất gói cao và hiệu năng không ổn định. Những phát hiện này có ý nghĩa thực tiễn lớn, gợi ý rằng các giao thức định tuyến và cấp phát kênh trong tương lai nên xem xét đến hướng lưu lượng để đưa ra quyết định thông minh hơn. Nghiên cứu này mở ra nhiều hướng phát triển tiềm năng. Việc tối ưu hóa độ phức tạp của các thuật toán, phát triển các thuật toán phân tán có khả năng thích ứng với hướng lưu lượng, và tiến hành các thử nghiệm trên thực địa là những bước đi tiếp theo đầy hứa hẹn. Những kết quả này sẽ góp phần xây dựng các mạng ad-hoc không dây mạnh mẽ và hiệu quả hơn.

6.1. Tổng kết giá trị cốt lõi của nghiên cứu cấp phát kênh

Giá trị cốt lõi của luận văn nằm ở việc định lượng hóa tác động của hướng lưu lượng, một khía cạnh thường bị đơn giản hóa trong các nghiên cứu trước đây. Bằng cách kết hợp mô hình toán học và mô hình mô phỏng mạng thực tế, nghiên cứu đã cung cấp những bằng chứng không thể chối cãi rằng việc ưu tiên các luồng một chiều hoặc thiết kế cơ chế kiểm soát truy cập phù hợp có thể cải thiện đáng kể throughput và delay của mạng.

6.2. Đề xuất thuật toán phân tán và tối ưu hóa độ phức tạp

Một hướng đi trong tương lai là phát triển các thuật toán phân tán mới. Các thuật toán này cho phép mỗi nút tự quyết định kênh sẽ sử dụng dựa trên thông tin cục bộ về hàng xóm và hướng lưu lượng của chúng. Thách thức là làm sao để các quyết định cục bộ này dẫn đến một trạng thái tối ưu toàn cục. Bên cạnh đó, việc giảm độ phức tạp tính toán của các thuật toán cấp phát kênh tối ưu vẫn là một lĩnh vực nghiên cứu quan trọng để có thể áp dụng trong các mạng quy mô lớn.

6.3. Triển vọng ứng dụng trong mạng cảm biến không dây

Kết quả của luận văn có tiềm năng ứng dụng rất lớn trong lĩnh vực mạng cảm biến không dây (WSN). Trong các mạng này, dữ liệu thường di chuyển theo một hướng chủ đạo (từ các nút cảm biến về nút trung tâm). Việc áp dụng một chiến lược cấp phát kênh nhận biết được hướng lưu lượng một chiều này sẽ giúp tối ưu hóa việc sử dụng năng lượng và kéo dài tuổi thọ của mạng, vốn là những yếu tố sống còn trong WSN. Đây là một hướng đi thực tiễn và có giá trị cao.

Trích đoạn nội dung tài liệu

Mémoire de fin de formation pour l’obtention du diplôme de Master Informatique : Spécialité réseaux et systèmes communicants Allocation de canaux dans les réseaux maillés sans fil : Conflits Directionnels-Bidirectionnels et algorithmes Encadreurs : M. NGUYEN Dai Tho Auteur : ASSADILLAH Youssouf – IFI- Promotion 17 Novembre 2014 TIEU LUAN MOI download : [e-mail] Table des matières Table des matières. 6 Liste de figures. 7 Liste des tableaux .1 Problématique et Motivation .3 Plan du rapport.

10 Chapitre 2 Concepts et état de l'art .1 Définition et explication des concepts.2 les problèmes d’allocation.3 Quelques algorithmes d'assignation de fréquences .2 CLICA: Connected Low Interference Channel Assignment. 16 Chapitre 3 Etudes et expérimentations .1 Cas directionnel : exemple .2 Cas bidirectionnel : exemple .2 Evaluation sur NS3 .1 Paramètres de simulations et Résultats. 25 Chapitre 4 Modélisation Mathématique des conflits et Evaluation .1 Probabilités des conflits .2 La moyenne des conflits. 27 2 TIEU LUAN MOI download : skknchat@gmail.4 La capacité moyenne (E[C]) .1 Probabilités des conflits .2 La moyenne des conflits bidirectionnels .4 La capacité moyenne (E[C]) .1 Rapport entre le nombre de conflits bidirectionnel et directionnel (en moyenne) .2 Distribution du nombre de conflits sur un lien bidirectionnel et directionnel.3 Débit moyen dans les deux cas.4 Simulation sur NS3 .1 Paramètres de simulations.

40 Chapitre 5 Conclusion Général et perspectives. 42 3 TIEU LUAN MOI download : [e-mail] Remerciements Je tiens tout d’abord à exprimer toute ma gratitude envers mes encadreurs Monsieur Anthony Busson Enseignant Chercheur à l'Université de Lyon 1 et Docteur NGUYEN Dai Tho enseignant à L'UNH et à l'IFI pour l’encadrement, l’aide et les conseils précieux qui m'ont permis d'arriver à bout de ce travail. Je remercie également tout le personnel et professeurs du département réseau de l’Université National de Hanoi (UNH) pour leur gentillesse et les moments que nous avons passé ensemble dans leur bureau. J’adresse mes sincères remerciements à tout le personnel et les professeurs de l’Institut de la Francophonie pour l’Informatique (IFI) et de l'Agence Universitaire de le Francophonie (AUF) pour m’avoir permis de suivre et achever cette formation de master.

Enfin, je voudrais remercier ma famille, mes parents et mes amis et tous ceux qui ont participé de prêt ou de loin à la réalisation de ce travail.tin TIEU LUAN MOI download : [e-mail] Résumé L'utilisation de plusieurs fréquences dans un réseau sans fil permet non seulement d’améliorer les performances du réseau mais surtout d'augmenter sa capacité globale. Le problème posé est l'assignation de ces fréquences d'une façon optimale. Comme il a été montré dans [1], l'assignation optimale des fréquences est un problème NP-complet. Toutefois plusieurs algorithmes d'allocation de fréquences ont été proposés dans la littérature.

La plupart d'entre eux intègre la notion de conflits afin qu'un nœud sache quelles fréquences il peut utiliser. Dans un travail précédent il a été montré que deux liens sont en conflits s'ils sont à moins de trois sauts, mais il existe un cas où des liens peuvent être à trois sauts sans pour autant être en conflits. Cela dépend du sens du trafic (directionnel ou bidirectionnel). Dans ce travail nous étudions les algorithmes intégrant la notion de conflits et l'impact du sens du trafic sur la présence des conflits.

Nous avons ensuite proposé un modèle mathématique qui permet d’évaluer la différence en nombre de conflits et en capacité entre un trafic directionnel et bidirectionnel. Ce modèle mathématique montre que le trafic bidirectionnel favorise les conflits par rapport au trafic directionnel. Les simulations sur NS3 de son implémentation montrent que le trafic bidirectionnel permet une augmentation des transmissions par rapport au trafic directionnel mais sur la réception, c’est le trafique directionnel qui est avantageux car il engendre moins de pertes. Mots- clés : Fréquences, assignation, réseau sans fil, conflits, sens du trafic.tin TIEU LUAN MOI download : [e-mail] Abstract The use of multiple frequencies in a wireless network allows not only to improve the network performance but also to increase its overall capacity.

A problem arises when we need an optimal assignment of frequencies. As was shown in [1] the optimal assignment is an NP-complete problem. But multiple frequency allocation algorithms have been proposed in the literature. Most of them incorporate the notion of conflicts so that a node knows what frequency it can use.

In a previous work it was shown that two links are in conflict if their distance is less than three hopes but there is a case where links can be in three hopes without being in conflict. It depends on the traffic direction (directional or bidirectional). In this work we study the algorithms incorporating the concept of conflict and the impact of the traffic direction on the presence of conflict. We proposed a mathematical model to evaluate the difference in number of conflicts and in capacity between a directional and bi-directional traffic.

This model shows that the bidirectional traffic promotes more conflicts than directional. NS3 simulations of its implementation show that bidirectional traffic allows an increase in transmission compared to directional traffic but on the receipt, the directional traffics is advantageous because it generates less waste. Keywords: Frequencies, subpoena, wireless network, conflicts, traffic direction 6 (LUAN.tin TIEU LUAN MOI download : [e-mail] Liste de figures Figure 1: Lien directionnel et lien bidirectionnel. 12 Figure 2: classification des algorithmes (source : [3]).

13 Figure 3: Allocation optimal : cas directionnel. 17 Figure 4: Allocation optimal : cas directionnel. 18 Figure 5: Evaluation de la capacité d’envoie par rapport au nombre de nœuds. 20 Figure 6: Evaluation de la capacité de réception par rapport au nombre de nœuds.

21 Figure 7: Evaluation de la capacité de réception par rapport au nombre de nœuds. 22 Figure 8: Evaluation de la capacité d’envoie par rapport au nombre de canaux. 23 Figure 9: Evaluation de la capacité de réception par rapport au nombre de canaux. 24 Figure 10: Rapport entre capacité de réception et d’envoie par rapport au nombre de canaux.

24 Figure 11: Situation de conflits. 26 Figure 12: Zone de conflits globale cas bidirectionnel. 29 Figure 13: Distribution des conflits directionnels et bidirectionnels :. 32 Figure 14: Evaluation de la capacité dans les deux cas.

32 Figure 15: Evaluation de la capacité dans les deux cas. 33 Figure 16: Evaluation des la capacité de transmission par rapport au délai. 34 Figure 17: Evaluation des la capacité de réception par rapport au délai. 35 Figure 18: Rapport entre la capacité de réception et la capacité de transmission par rapport au délai.

35 Figure 19: Capacité de transmission par rapport à la distance. 36 Figure 20: Capacité de réception par rapport à la distance. 37 Figure 21: Rapport entre la capacité de réception et la capacité de transmission par rapport à la distance. 38 Figure 22: Capacité de transmission par rapport au nombre de nœuds.

39 Figure 23: Capacité de réception par rapport au nombre de nœuds. 39 Figure 24: Rapport entre la capacité de réception et de la capacité de transmission par rapport au nombre de nœuds .tin TIEU LUAN MOI download : [e-mail] Liste des tableaux Tableau 1: Paramètres de simulation. 19 Tableau 2: Paramètres de simulations NS3: expérimentations finales .tin TIEU LUAN MOI download : [e-mail] Chapitre 1 Introduction 1.1 Problématique et Motivation Les réseaux sans fil ad hoc ont l’avantage de pouvoir être déployés rapidement et pour un coût très peu élevé. Cela en fait une solution efficace dans un certain nombre de contextes : couverture de zone blanches, mise en place de réseaux temporaires dans le cas d’événements ponctuels (sportifs, concerts, etc.), ou dans le cas d’intervention de sécurité civile (zone de désastre, intervention de force de l’ordre, etc.

L’idée est de déployer un ensemble de nœuds/routeurs équipés de cartes sans fil, a priori Wi-Fi, et configuré en mode ad hoc. Ces nœuds couvrent la zone où se situent les utilisateurs [8]. Les données provenant de ces utilisateurs transitent alors en multi- sauts au travers de ces nœuds. Certains de ces nœuds sont raccordés à l'Internet et servent de passerelles Internet pour le reste du réseau [1].

Ils servent d’infrastructure sans fil pour permettre d’interconnecter les utilisateurs entre eux, ou permettre de les relier à un point d’infrastructure filaire (accès à Internet par exemple) [9]. Un problème important persiste quand à l’utilisation de ces réseaux : la capacité. Nous définissons ici la capacité comme le nombre de bits par second que le réseau est capable de transporter des sources aux destinations. Si tous les nœuds utilisent le même canal Wi-Fi, la capacité du réseau est assez faible [11].

En effet, ce canal étant partagé par un nombre importants de liens sans fil, cela amène à une division de la bande passante utile de ces liens. Une solution simple et peu onéreuse à ce problème consiste à équiper les nœuds de plusieurs cartes sans fil. Des canaux différents sont alors associés à ces différentes cartes. Beaucoup moins de liens utilisent alors un même canal, ce qui permet une augmentation significative de la capacité [8] [9].

Mais l’assignation des canaux aux différentes radios doit être automatique, et faite de manière à optimiser la capacité du réseau. Dans ce travail nous étudions les algorithmes d’assignation de canaux et l’impact du sens du trafic dans la présence des conflits. Mon travail à porter sur deux aspects : l’étude des algorithmes d’assignation de canaux existants, et l’étude de gain quand à la prise en compte de la direction des liens (sens du trafic) dans le calcul des conflits.2 Contribution Dans ce travail j’ai réalisé deux principales tâches :  La première consistait à implémenter l’algorithme proposé dans [7] en intégrant la prise en 9 (LUAN.tin TIEU LUAN MOI download : [e-mail] charge de l’allocation des canaux selon le sens du trafic afin de pouvoir évaluer la différence en nombre de conflits entre un trafic directionnel et bidirectionnel selon le critère du métrique proposés dans [7].  La deuxième est de proposer un modèle mathématique qui prend en compte les distances (au lieu du nombre de sauts) pour déterminer les liens en conflits et où les nœuds ont une distribution aléatoire dans l’espace.3 Plan du rapport Le reste du document est structuré comme suit: Dans le chapitre 2 nous présenterons l'état de l'art et quelques notions concernant le sujet ; ensuite le chapitre 3 aborde les premières expérimentations pour évaluer l’impacte du sens trafic dans la présence des conflits.

Le chapitre 4 viendra présenter le modèle mathématique permettant d'évaluer toujours l'impacte du sens du trafic mais en se basant cette fois ci sur des notions probabilistes et de distances entre les nœuds. Enfin dans le chapitre 5, nous donnerons nos conclusions et perspectives.tin TIEU LUAN MOI download : [e-mail] Chapitre 2 Concepts et état de l'art 2.1 Définition et explication des concepts 2.1 Lien Nous disons qu’il y a un lien radio entre deux nœuds si les deux nœuds ont un canal commun et que les conditions radios (distance, qualité du signal) sont réunis pour permettre la communication sur ce signal [9][10].2 Conflits Nous disons qu'il y a conflits entre des liens lorsque ces liens ne peuvent pas être utilisés en même temps. Il existe deux types de conflits : les conflits entre deux émetteurs utilisant la même fréquence et dont chacun détecte le signal de l'autre, et le conflit entre un émetteur et un récepteur lorsque l'émetteur interfère avec un récepteur non légitime.  Protocol Model : deux liens e1(u1,v1) et e2(u2,v2) interfèrent entre eux s’ils utilisent le même canal et si toutes les distances d(u1,u2) , d(u1,v1) , d(v1,u2) , d(v1,v2) sont inférieures à Ri (Ri : rayon d’interférence)  Physical Model : une transmission est réussie si SNRij (Signal to noise ratio) est plus grand que SNRthres (threshold) où SNRij représente le rapport signal/bruit sur le noeud nj pour la transmission reçu du noeud ni [1][4].