3-4 آگاهی از زمینه……………………… 31

3-5 طراحی زمینه……………………… 32

3-6 جمع­بندی………………………. 33

فصل چهارم: سیستم­های پیشنهاد­دهنده

4-1 مقدمه……………………… 35

4-2 بررسی عملکرد سیستم­های پیشنهاد­دهنده…………………….. 36

4-2-1 روش­های مبتنی بر محتوا…………………….. 38

4-2-1-1 مشکلات و محدودیت­­های روش­های مبتنی بر محتوا …………. 41

4-2-2 روش­های فیلترسازی مشارکتی………………………. 42

4-2-2-1 مشکلات و محدودیت­­های روش­های فیلتر­سازی مشارکتی………. 46

4-2-3 روش­های ترکیبی………………………. 48

4-3 ارزیابی سیستم­های پیشنهاد­دهنده…………………….. 49

4-4 بسط قابلیت­های سیستم­های پیشنهاد­دهنده…………………….. 51

4-4-1 شرکت­دادن شناختی جامع از کاربران و اقلام در فرآیند پیشنهاد­دهی……. 51

4-4-2 امتیاز­گذاری چند­معیاری………………………. 52

4-4-3 پیشنهاد­دهنده ­های غیر­تداخلی………………………. 53

4-4-4 انعطاف ­پذیری………………………. 53

4-4-5 توسعه شاخص­های ارزیابی………………………. 544-4-6 استفاده از اطلاعات زمینه در پیشنهاد­دهنده­ ها…………………….. 55

4-4-7 سایر گزینه ­ها برای بسط و توسعه سیستم­های پیشنهاد­دهنده ……. 55

4-5 جمع­بندی………………………. 55

فصل پنجم: روش جدید چند­بعدی برای پیشنهاد­دهی آگاه از زمینه

5-1 مقدمه………………………57

5-2 سیستم­های پیشنهاد­دهنده آگاه­از­زمینه در تجارت سیار……….. 58

5-3 مدل­سازی اطلاعات زمینه……………………… 59

5-4 روش چند­بعدی در سیستم­های توصیه­ گر سیار آگاه از زمینه……. 61

5-5 جمع­بندی………………………. 68

فصل ششم: ارزیابی

6-1 مقدمه……………………… 69

6-2 روش ارزیابی………………………. 69

6-2-1 پیاده­سازی سیستم جمع ­آوری داده…………………….. 70

6-3 پیاده­ سازی روش پیشنهاد­دهی………………………. 72

6-3-1 پیاده­ سازی روش پیشنهاد­دهی دو­بعدی………………………. 73

6-3-2 پیاده­ سازی روش پیشنهاد­دهی چند­بعدی………………………. 78

6-4 جمع­بندی………………………. 82

فصل هفتم: جمع­بندی و راهکار­های آینده

7-1 مقدمه……………………… 84

7-2 راهکار­های آینده ……………………..85

منابع و مآخذ………………………. 87

چکیده:

استفاده از زمینه، به عنوان اطلاعات پویایی که توصیف­گر وضعیت کاربران و اقلام بوده و بر فرایند تصمیم­گیری و انتخاب کاربران تاثیرگذار است، توسط سیستم­های پیشنهاد­دهنده در تجارت سیار، در جهت ارتقاء کیفیت مناسب پیشنهاد­دهی ضروری است. در این تحقیق یک روش جدید چند­بعدی برای پیشنهاد­دهی آگاه از زمینه در تجارت سیار ارائه­ شده است. در این روش اطلاعات کاربران، اقلام، پارامتر های زمینه و ارتباط میان آنها در یک فضای چند­بعدی نمایش ­داده می­شود که به آن مکعب چند­بعدی امتیازات گفته می­شود. در این فضا زمینه­ های مشابه به­ طور جداگانه برای هر کاربر شناسایی می­شوند که این کار با شناسایی الگوهای مصرف متفاوت کاربران در شرایط زمینه­ای مختلف انجام می­شود. با بدست آوردن این اطلاعات، یک فضای جدید دوبعدی ایجاد­شده و پیشنهاد­دهی نهایی با استفاده از یک روش فیلتر­سازی مشارکتی در این فضا انجام می­گیرد. ارزیابی روش از طریق پیاده ­سازی آن در یک سیستم پیشنهاد­دهی محصولات غذایی رستوران­ها شامل پارامتر­های زمینه­ای روز، زمان، آب و هوا و همراه علاوه بر پارامتر­های کاربر و اقلام و مقایسه آن با روش سنتی پیشنهاد­دهی و بدون در­نظر­­گرفتن اطلاعات زمینه انجام گرفته ­است. برای پیاده­سازی روش فیلتر­سازی مشارکتی از شبکه­ های خود­سازمانده استفاده­شده­است. شبکه­ های خود­سازمانده، نوعی از شبکه های عصبی بدون ناظر هستند. مقایسه و ارزیابی نتایج با استفاده از محاسبه شاخص F1 که یکی از شاخص­های استاندارد و پر استفاده برای ارزیابی پیشنهاد­دهنده­ ها است، انجام گرفته ­است. بر اساس این نتایج، روش پیشنهاد­دهی چند­بعدی در حدود شانزده درصد بهبود نسبت به روش سنتی پیشنهاد­دهی را نمایش می­دهد که همین مساله کارایی روش را از نظر کیفیت پیشنهاد­دهی تایید می­کند.

فصل اول: مقدمه

1-1- مقدمه

سیستم­های پیشنهاد­دهنده در تجارت سیار از جمله موضوعات پر­اهمیت سال­های اخیر بوده­اند که با ظهور تکنولوژی­های بی­سیم و تسهیل حرکت تجارت الکترونیکی از محیط­های سیمی به سوی بی­سیم­ مورد توجه قرار­گرفته­اند. تجارت سیار به­معنای انجام فعالیت­های تجارت­الکترونیک از طریق محیط­های بی­سیم، به­طورخاص اینترنت بی­سیم، و وسایل دستی سیار می­باشد که با­ پیدایش تکنولوژی بی­سیم در عرصه اینترنت و استفاده روزافزون از وسایل سیار توجه به آن رو به افزایش است[1,2]. به کاربرد­های تجارت سیار دو خصوصیت ویژه تحرک[1] و دسترسی وسیع[2] نسبت داده­شده­است[1,3] که اولین خصوصیت بر امکان از بین رفتن محدودیت­های مکانی و دومین خصوصیت بر امکان از بین رفتن محدودیت­های زمانی در استفاده کاربران از خدمات این نوع کاربرد­ها تاکید دارد[1,3,4,5]. این­که کاربران برای انجام فعالیت هایی چون بانکداری الکترونیکی یا خرید الکترونیکی محصولات، قادر به جایگزینی وسایلی چون تلفن­های سیار و ­همراه­های شخصی دیجیتال (پی.دی.اِی)[3] به­جای کامپیوتر­های شخصی باشند، تسهیلات زیادی را برای آنها و فرصت­های جدیدی را نیز برای کسب وکار­ها فراهم­­­خواهد­کرد و لزوم توجه به این عرصه را برای محققان نمایان می­سازد[1,3].

اما پیاده­سازی سیستم­های پیشنهاد­دهنده در محیط­های سیار بدون در­نظر­گرفتن پارامتر­های تاثیر­گذار در این محیط چندان مناسب­نخواهد­بود. مجموعه این پارامتر­ها، اطلاعات زمینه را تشکیل می­دهند [6].

عملکرد سیستم­های پیشنهاد­دهنده معرفی منابع مورد نیاز کاربران به آنهاست. این منابع می­توانند مواردی مانند اطلاعات خاص مورد نیاز کاربر و یا کالاها­یی مانند کتاب یا فیلم مورد علاقه یک کاربر را از میان انبوه کالاهایی که کاربر با اطلاعات آن­ها روبروست، در­بر­گیرند[7,8,9]. درسیستم­های پیشنهاد­دهنده، سه مجموعه داده اصلی یعنی مجموعه کاربران ©، مجموعه اقلام قابل توصیه(S) (مانند کتاب، فیلم، موسیقی و غیره) و مجموعه داده­هایی که رابطه میان دو مجموعه قبلی را تعریف می­کنند، وجود­دارند. مجموعهS می­تواند شامل صد­ها، هزار­ها و حتی میلیون­ها کالا در کاربرد­های مختلف بوده و به­طور مشابه مجموعه C نیز می­تواند چنین وضعیتی را داشته باشد. ارتباط میان دو مجموعهC و S مبتنی بر ساختار امتیاز­گذاری است که میزان مفید بودن یا مورد علاقه بودن کالا را برای کاربر مشخص می کند. این ارتباط با تابعی تحت­ عنوان تابع سودمندی، u، به صورت رابطه زیر تعریف می­شود.

که در آن Ratings، مجموعه مرتبی مانند اعداد صحیح غیر­منفی یا مجموعه اعداد حقیقی در بازه­ای معین می­باشد.

در سیستم­های پیشنهاد­دهنده مقادیر u معمولاً فقط بر روی زیر مجموعه­ای از دامنه C×S تعریف­شده­است و نه بر تمام آن و قسمت های نامشخص این دامنه را باید با ­استفاده از داده­های موجود به­صورت تخمینی مشخص نمود. هدف نهایی سیستم­های توصیه­کننده با ارائه پیشنهاد اقلام با بالاترین امتیازات تخمینی به کاربران محقق می­شود به­طوریکه برای هر کاربر ، اقلام با حداکثر میزان سودمندی انتخاب و معرفی می­گردد[7].

تا به امروز روش­های پیشنهاد­دهی زیادی ارائه شده­است که این روش­ها و متدولوژی­ها در دسته­بندی­های زیر قرار می­گیرند[7,9,10]:

– مبتنی بر محتوا[1] : در این گروه از روش­ها، عمل پیشنهاد­دهی با استفاده از یافتن اقلامی انجام می­گیرد که بیشترین تشابه را با اقلامی داشته باشند که در­گذشته مورد­علاقه کاربر بوده­اند. به عبارت دیگر u(c,s)، سودمندی کالای s برای کاربر c، بر اساس کلیه مقادیر موجود u(c,s_i) هایی که s_iمشابه به s بوده و s_iجزء کالاهای مورد علاقه کاربر هستند،_­برآورد می­شود.

– فیلترسازی مشارکتی : در این گروه از روش­ها، عمل پیشنهاد­دهی با استفاده از یافتن اقلامی انجام می­گیرد که مورد علاقه کاربران با سلایق مشابه کاربر بوده­اند. کاربران با سلایق مشابه یعنی کاربرانی که اقلام یکسانی را امتیاز­دهی مشابه کرده باشند. به­عبارت دیگر u (c, s) بر اساس مقادیر موجودu(c_j,s) بدست می­آید که c_jکاربران مشابه با c می­باشند.

– مدل ترکیبی[2]: روش­هایی که دو روش مبتنی­بر­محتوا و فیلتر­سازی مشارکتی را ترکیب می­کنند و به این صورت از مزایای هر دو روش در جهت شناسایی و معرفی کالاها بهره می­گیرند.

در نگاهی دیگر روش­های پیشنهاد­دهی، اعم از مبتنی بر محتوا و فیلتر­سازی مشارکتی به دو دسته روش­های مبتنی بر حافظه[3]و مبتنی بر مدل[4] تقسیم می­شوند. در­مقایسه با الگوریتم­های مبتنی بر حافظه، الگوریتم­های مبتنی بر مدل، با استفاده از روش­های یادگیری ماشین[5] مدلی را با استفاده از مجموعه امتیازات موجود ایجاد کرده و از آن به­منظور پیشگویی امتیازات استفاده می­کنند[7,10,11].

1-2 موضوع تحقیق

موضوع این تحقیق، ارائه روشی برای پیشنهاد­دهی آگاه از زمینه در تجارت سیار می­باشد. با­ پیدایش تکنولوژی بی­سیم در عرصه اینترنت و استفاده روزافزون از وسایل سیار، پیاده­سازی سیستم­های پیشنهاد­دهنده در محیط­های سیار با توجه به محدودیت­های خاص آن چون هزینه­بر بودن زمان اتصال و تبادل داده، محدودیت پهنای باند، کیفیت پایین اتصال و محدودیت­های ورودی و خروجی وسایل سیار، نیاز به بررسی بیشتر را در جهت ارائه اطلاعات مرتبط­تر و شخصی­سازی­شده­تر می­طلبد. بررسی تاثیر اطلاعات زمینه به­عنوان شرایط و محیط دربرگیرنده کاربر و به­عنوان اطلاعاتی که بر فرایند تصمیم­گیری وی تاثیر­گذارند، برخروجی این­گونه کاربرد­ها، مساله­ای است که در این تحقیق مورد بررسی قرار گرفته­است.

1-3 پیشینه تحقیق

ظهور تکنولوژی­های بی­سیم و استفاده رو به­افزایش وسایل سیار، فرصت­های زیادی را پیش روی کاربرد­های تجارت الکترونیک قرار­داده­است. با توجه به محدودیت­های خاص محیط­های سیار، ارائه اطلاعات به­صورت شخصی­سازی­شده­تر و سفارشی­شده­تر یکی از اهداف مهم کاربرد­های تجارت سیار است. در­نظرگرفتن اطلاعات زمینه به­عنوان شرایط و محیط دربرگیرنده کاربر و به­عنوان اطلاعاتی که بر فرایند تصمیم­گیری وی تاثیر­گذارند، در ارائه خروجی این­گونه کاربرد­ها از جمله مواردی است که می­توان از آن در جهت ارائه اطلاعات مرتبط­تر به کاربران بهره گرفت.

سیستم­های پیشنهاد­دهنده همواره از جمله موضوعات پر اهمیت در حوزه تجارت الکترونیک بوده­است. سیستم­های پیشنهاد­دهنده سیار آگاه از زمینه در آغاز راه هستند. دسته مهمی از سیستم­های آگاه از زمینه را سیستم­های آگاه از مکان تشکیل می­دهند. یانگ، چنگ، و دایا[12]، یک سیستم پیشنهاد­دهنده آگاه از مکان برای محیط­های سیار ارائه­داده­اند که هدف آن توصیه وب­سایت فروشندگان با در نظر­گرفتن علایق و پیش­فرض­های مشتری و همچنین فاصله مکانی وی با مکان فیزیکی مشخص­شده در وب­سایت­ها می­باشد. در روش مزبور، دو فاکتور فوق به­طور جداگانه محاسبه­ شده و سپس بر اساس ترکیبی از آنها به پیشنهاد وب­سایت­ها پرداخته می­شود. یکی دیگر از این نوع سیستم­ها پروکسیمو[13] است که یک سیستم پیشنهاد­دهنده آگاه از مکان برای محیط­های داخلی چون موزه­ها و گالری­ها است. این سیستم بر اساس علایق و پیش­فرض­های کاربر به پیشنهاد اقلام پرداخته و مکان اقلام را بر روی نقشه­ای بر روی وسیله همراه کاربر نمایش می­دهد.

استفاده از سایر اطلاعات زمینه­ای علاوه­بر مکان نیز مورد توجه توسعه­دهندگان این نوع سیستم­ها قرار­گرفته­است. پخش موسیقی یکی از حوزه­های کاربردی پر­مصرف در میان کاربران سیار می­باشد و به همین دلیل استفاده از پیشنهاد­دهنده­های آگاه از زمینه در این حوزه مورد توجه قرار­گرفته است. از آنجایی که تاثیر موسیقی بر روح و جسم انسان ثابت شده­است، انتخاب موسیقی با توجه به شرایط می­تواند وضعیت دوست­داشتنی­تری را فراهم­کند و افراد را در انجام فعالیت­هایشان یاری رساند. مثلاً موسیقی می­تواند کارایی فرد را در حال انجام تمرینات فیزیکی بهبود بخشد، اضطراب را کاهش دهد و میزان یادگیری را بهبود بخشد. [14] یکی از تحقیقاتی است که در این حوزه ارائه­شده­است. در این تحقیق علاوه­بر بررسی روش­های فیلتر­سازی مبتنی­بر زمینه ومرورپیشنهاد­دهنده­های سیار آگاه از زمینه موسیقی، پیشنهاد­دهنده سیار آگاه از زمینه AndroMedia ارائه شده­است. پیشنهادات با توجه به زمینه جاری کاربر که با استفاده از حسگر­های بلوتوث در سمت برنامه مشتری بدست می­آیند و همچنین سلایق کاربر تهیه می­شوند. همچنین در مرجع [15] نیز پیشنهاد­دهی آگاه از زمینه موسیقی در محیط­های سیار مورد بررسی قرار­گرفته­است. در تحقیق پارک، یو و چو[16] نیز یک سیستم آگاه از زمینه موسیقی با استفاده از شبکه­های بیزین فازی و تئوری سودمندی ارائه­شده­است. فرایند پیشنهاد­دهی تحلیل شده و سودمندی آن مورد ارزیابی قرار­گرفته­است.

گردشگری نیز یکی از حوزه­های جذاب برای پیاده­سازی پیشنهاد­دهنده­های سیار آگاه از زمینه می­باشد. امروزه گردشگران انتظار دارند که دسترسی شخصی به اطلاعات گردشگری در هر زمان، هر مکان و در هر شرایطی را داشته­باشند. راهنما­های گردشگری سیار، چنین اطلاعاتی را در اختیار کاربران قرار می­دهند. در مرجع [17] خلاصه­ای از کار­های انجام­شده در زمینه راهنماهای گردشگری سیار تحت وب انجام گرفته­است. همچنین در مرجع[18] تاثیر آگاهی از زمینه در سیستم­های اطلاعاتی گردشگری سیار مورد بررسی قرار گرفته­است. در [19] نیز یک کاربرد توریستی سیار با نام COMPASS ارائه­شده­است. در این تحقیق به بررسی ترکیب آگاهی از زمینه با سیستم­های پیشنهاد­دهنده پرداخته شده­است. پارامتر­های زمینه­ای این تحقیق شامل زمان و مکان می­باشند. این سیستم خدمات خود را با نیاز­های کاربر که بر اساس علایق و زمینه جاری وی مشخص می­شود، تطبیق می­دهد.

فصـل دوم:مروری بر ادبیات و پیشینه تحقیق

2-1-مروری بر چندین روش نهان نگاری در متون دیجیتال……………………………………………….. 24

2-2- روش درج نقطه……………………………………………………………………………………………………………….. 24

2-2-1- شرح کلی روش…………………………………………………………………………………………………………… 24

2-2-2- نتیجه گیری …………………………………………………………………………………………………………………. 26

2-3- روش تغییر شکل حروف…………………………………………………………………………………………………….28

2-3-1- شرح روش …………………………………………………………………………………………………………………..28

2-3-2- نتیجه گیری ………………………………………………………………………………………………………. 30

2-4 درج کاراکتر کشش بین کاراکترهای کلمات……………………………………………………………………. 31

2-4-1شرح روش …………………………………………………………………………………………………………………….31

2-4-2- نتیجه گیری ………………………………………………………………………………………………………. 33

2-5- روش توسعه یافته درج کاراکتر کشش بین کاراکترهای کلمات……………………………………….. 33

2-5-1شرح روش ……………………………………………………………………………………………………………………. 33

2-5-2- نتیجه گیری ………………………………………………………………………………………………………………….34

2-6- روش بهبود یافته “لا”…………………………………………………………………………………………….. 35

2-6-1- شرح روش ………………………………………………………………………………………………………… 35

2-6-2- نتیجه گیری ……………………………………………………………………………………………………….. 36

2-7- روش درج کاراکتر بدون طول بین کلمات ………………………………………………………………. 36

2-7-1-شرح روش ………………………………………………………………………………………………………… 36

2-7-2- نتیجه گیری …………………………………………………………………………………………………… 37

2-8- روش نهان نگاری بلوکی بین کلمات ……………………………………………………………………. 38

2-8-1- شرح روش …………………………………………………………………………………………………………38

2-8-2- نتیجه گیری ………………………………………………………………………………………………………………….39

2-9- روش گروه بندی کاراکترهای متن(NP-UniCh)……………………………………………………………..

2-9-1- شرح روش …………………………………………………………………………………………………….. 40

2-9-2- نتیجه گیری ……………………………………………………………………………………………….. 41

2-10- روش گروه بندی دوبیتی کاراکترهای متن ……………………………………………………………. 42

2-10-1- شرح روش ……………………………………………………………………………………………………. 42

2-10-2- نتیجه گیری ……………………………………………………………………………………………………42

2-11- استفاده از شکل دیگر کاراکترها در فونت­های متفاوت …………………………………………… 43

2-11-1-شرح روش ………………………………………………………………………………………………………………… 43

2-11-2- نتیجه گیری ………………………………………………………………………………………………… 45

2-12- نهان نگاری براساس تغییر زاویه کلمات ………………………………………………………………… 45

2-12-1شرح روش ………………………………………………………………………………………………………………….. 45

2-12-2- نتیجه گیری ………………………………………………………………………………………………………………..47

2-13- درج کاراکترهای نامحسوس درمتون لاتین ………………………………………………………………………….. 47

2-13-1- شرح روش …………………………………………………………………………………………………………………47

2-13-2- نتیجه گیری ………………………………………………………………………………………………………………..49

2-14- درج فاصله های خاص در موقعیت های مختلف …………………………………………………………………. 50

2-14-1- شرح روش …………………………………………………………………………………………………………………50

2-14-2نتیجه گیری …………………………………………………………………………………………………………………. 51

فصـل دوم: روش اجرای تحقـیـق

3-1- کلیات روش پیشنهادی ……………………………………………………………………………………………………….53

3-2-مروری بر استاندارد یونیکد …………………………………………………………………………………….. 54

3-2-1- تعیین کدهای کاراکترها ………………………………………………………………………………… 54

3-2-2- انواع فرم های انکدینگ ……………………………………………………………………………………. 55

3-2-3- یونیکد فارسی/عربی ……………………………………………………………………………………….. 55

3-2-4- کاراکترهای یونیکد کنترلی ……………………………………………………………………… 56

3-3- فرآیند کلی نهان نگاری و استخراج پیام در این رساله ……………………………………………….. 56

3-4- شرح روش نهان نگاری در این رساله …………………………………………………………………………… 58

3-4-1-تبدیل پیام رمز به معادل دودویی ………………………………………………………………………………………58

3-4-2درج و نشانه گذاری پیام رمز ……………………………………………………………………………………………..59

3-4-3کشف و استخراج پیام رمز ……………………………………………………………………………………………….. 60

فصـل چهارم: تجزیه و تحلـیـل داده ها

4-1-بررسی آزمایشات الگوریتم پیشنهادی ………………………………………………………………………………….. 62

4-2-نتایج و بحث برروی نتایج ……………………………………………………………………………………….. 62

4-3- بررسی پارامترهای نهان نگاری براساس نتایج اجرای الگوریتم………………………………………. 63

4-3-1-مقاومت دربرابر حملات تغییر ………………………………………………………………………………………… 63

4-3-2- ظرفیت نهان نگاری ……………………………………………………………………………………………………….64

4-3-3- اندازه فایل نهان نگاری شده ………………………………………………………………………………… 65

4-3-4- شفافیت (تناسب با فایل میزبان) ……………………………………………………………………………. 65

4-3-5- آسیب پذیری دربرابر حملات ………………………………………………………………………………. 66

4-3-6- محدودیت ها و نواقص ………………………………………………………………………………………………….67

4-4- بررسی الگوریتم روش ……………………………………………………………………………………………………….67

4-4-1- الگوریتم نهان نگاری ……………………………………………………………………………………………………..67

4-4-2- محاسبه پیچیدی زمانی الگوریتم نهان نگاری ………………………………………………68

4-4-3- الگوریتم بازیابی پیام ………………………………………………………………………………………………………68

4-4-4- محاسبه پیچیدی زمانی الگوریتم بازیابی پیام ……………………………………………….68

4-5- نمودار مورد کاربرد عملیات نهان نگاری پیام رمز……………………………………………… 69

4-6-نمودار مورد کاربرد عملیات بازیابی پیام رمز…………………………………………. 70

فصـل پنجم: نتیجه گیری و پیشنهادات

5-1- خلاصه پژوهش ………………………………………………………………………………………… 72

5-2- نتیجه گیری ………………………………………………………………………………………….. 73

فهرست منابع انگلیسی ………………………………………………………………………………………….. 74

پیوست

پیوست 1 : کلاس الگوریتم پیشنهادی در این تحقیق …………………………………………….. 81

چکیده انگلیسی ………………………………………………………………………………………………… 87

چکیده:

از ابتدای دیجیتالی شدن اسناد حقیقی و حقوقی، همواره مالکان اسناد آنها به دنبال روشی مناسب جهت حفاظت از حق اثر(کپی­رایت)آن بوده­اند.

گسترش و رشد روز افزون اینترنت باعث ایجاد تغییرات گسترده در نحوه زندگی و فعالیت شغلی افراد، سازمانها و موسسات شده است. امنیت اطلاعات یکی از مسائل مشترک شخصیت های حقوقی و حقیقی است. اطمینان از عدم دستیابی افراد غیر مجاز به اطلاعات حساس از مهمترین چالش های امنیتی در رابطه با توزیع اطلاعاتدر اینترنت است. اطلاعات حساس که ما تمایلی به مشاهده و دستکاری آنان توسط دیگران نداریم، موارد متعددی را شامل می شود که حجم بسیار زیادی، بالغ بر90 درصد این اطلاعات را متون دیجیتال تشکیل می­دهند.

با توجه به حجم بسیار زیاد اطلاعات متنی در دنیای امروز، و اشتراک گزاری آن در اینترنت، نیاز به انجام کارهای پژوهشی در این زمینه بر کسی پوشیده نیست و رمزنگاریونهان نگاری اسناد دیجیتال به عنوان یک تکنیک محرمانه در متون دیجیتال، می­تواند موارد استفاده بسیار زیادی داشته باشد. به عنوان مثال یکی از مواردی که امروزه به صورت جدی مورد توجه قرار گرفته است جلوگیری از جعل اسناد الکترونیکی و اعمال حق اثر (کپی­رایت) به صورت نهفته در داخل خود آن اثر می باشد.

در این پایانامه، روش جدیدی برای حفاظت از کپی غیر مجاز متون دیجیتال با استفاده از نهان نگاری پیام در اسناد دیجیتال مانند(MS Word،MS Excel) ، ارائه شده است که این کار، با استفاده از درج کاراکترهای مخفی یونیکد نسبت به موقعیت کاراکترهای خاص نگارشی(مانند، کاما، نقطه، ویرگول ،دابل کوتیشن و.. ) در متن اصلی، با تغییر نامحسوس انجام شده است.

درروش ارائه شده، پیام کاراکتر به کاراکتر پردازش شده و هر کاراکتر به صورت مجزا به یک عدد 8 بیتی باینری تبدیل می شود. قبل از نهان نگاری، ابتدا طول پیام که یک مجموعه باینری 8 بیتی است، درمتن اصلی به صورت زوج بیت “00، 01 ،10،11” نسبت به موقعیت کاراکترهای خاص نشانه گذاری می شود برای انجام این کار، به ازای هر کاراکتر، چهار کاراکتر مخفی (بدون طول یونیکد) در نظر گرفته شده است، به عبارت دیگر قبل و بعداز هر کاراکتر خاص در متن چهار زوج بیت با چهار علامت نشانه گذاری شده و این روند تا آنجا که کل بیت های پیام در متن نهان نگاری شود تکرار خواهند شد.

فصل اول: کلیات تحقیق

1-1- مقدمه

ﭘﻨﻬﺎن نگاری و رمز نگاری دادهﻫﺎ ﺗﮑﻨﯿﮑﯽ اﺳﺖ ﮐﻪ از دﯾﺮﺑﺎز ﻣﻮرد ﻋﻼﻗﻪ ﺑﺴﯿﺎری از اﻓﺮاد ﺑﻮده اﺳﺖ. ﺑﺎ ﭘﯿﺸﺮﻓﺖ ﻋﻠﻮم و داﻧﺶ ﺑﺸﺮی روﺷﻬﺎی ﭘﻨﻬﺎن ﺳﺎزی ﻧﯿﺰ ﺑﻪ ﻧﻮﺑﻪ ﺧﻮد ﺑﺎ ﭘﯿﺸﺮﻓﺖ ﻣﻮاﺟﻪ ﺷﺪه و رﺳﺎﻧﻪﻫﺎی ﻣﻮرد اﺳﺘﻔﺎده و ﺗﮑﻨﯿﮏﻫﺎی ﭘﻨﻬﺎنﺳﺎزی دادهﻫﺎ ﻧﯿﺰ ﺗﻮﺳﻌﻪ ﯾﺎﻓﺘﻪاﻧﺪ. دو ﻫﺪف اﺻﻠﯽ را ﻣﯽﺗﻮان ﺑﺮای ﭘﻨﻬﺎنﺳﺎزی دادهﻫﺎ در ﻧﻈﺮ ﮔﺮﻓﺖ. ﻫﺪف اول ﮐﻪ از دﯾﺮﺑﺎز ﻣﻮرد ﺗﻮﺟﻪ ﺑﻮده و دﻟﯿﻞ اﺻﻠﯽ ﭘﯿﺪاﯾﺶ روﺷﻬﺎی ﻣﺨﺘﻠﻒ پنهان نگاریﻣﯽﺑﺎﺷﺪ ﭘﻨﻬﺎنﺳﺎزی دادهﻫﺎیﺳﺮی و ﻣﺤﺮﻣﺎﻧﻪ درون رﺳﺎﻧﻪﻫﺎ وﺣﺎﻣﻞﻫﺎی ﻋﻤﻮﻣﯽ اﺳﺖ (نیکولاس و همکاران، 1998).

ﻫﺪف دوم ﮐﻪ اﻣﺮوزه راﯾﺞ ﺷﺪه و ﺑﻪ دﻟﯿﻞ ﮐﺜﺮت اﺳﺘﻔﺎده ﻧﺴﺒﺖ ﺑﻪ ﻫﺪف اول ﺑﯿﺸﺘﺮ ﺑﺮروی آن ﮐﺎر ﺷﺪه اﺳﺖ، درج اﻣﻀﺎی ﺻﺎﺣﺐ رﺳﺎﻧﻪ درون آنﻣﯽﺑﺎﺷﺪ. در ﺣﺎﻟﺖ اول ﻫﺪف اﺻﻠﯽ ﮔﻨﺠﺎﻧﺪن ﺣﺠﻢ ﻗﺎﺑﻞ ﻗﺒﻮﻟﯽ از دادهﻫﺎ، در رﺳﺎﻧﻪ ﺑﻪ ﻧﺤﻮی اﺳﺖ ﮐﻪ اﻣﮑﺎن ﺑﺎزﯾﺎﺑﯽ آﻧﻬﺎ ﺗﻮﺳﻂ اﻓﺮاد دﯾﮕﺮ ﭘﯿﭽﯿﺪه و ﺣﺘﯽاﻻﻣﮑﺎن ﻏﯿﺮﻣﻤﮑﻦ ﺑﺎﺷﺪ. واﺑﺴﺘﻪ ﺑﻪ ﻧﻮع ﭘﯿﺎم و ﻧﺤﻮه اﻧﺘﻘﺎل آن ﻣﻌﻤﻮﻻً ﺣﺘﯽ اﻣﮑﺎن ﮐﺸﻒ وﺟﻮد دادهﻫﺎی ﻧﻬﻔﺘﻪ در رﺳﺎﻧﻪ ﻧﯿﺰ ﻏﯿﺮ ﻗﺎﺑﻞ ﻗﺒﻮل ﺑﻮده و در ﻫﺮ ﺻﻮرت اﻣﮑﺎن ﺑﺎزﯾﺎﺑﯽ داده ﺑﺮای اﻓﺮادﻏﯿﺮ، ﭘﺬﯾﺮﻓﺘﻨﯽ ﻧﯿﺴﺖ. در اﯾﻦﺣﺎﻟﺖ ﺣﺘﯽ در ﻣﻮاردی ﺧﺮاﺑﯽ دادهﻫﺎ ﺑﺮ اﺛﺮ دﺧﻞ و ﺗﺼﺮف در رﺳﺎﻧﻪ ﭼﻨﺪان اﻫﻤﯿﺘﯽ ﻧﺪاﺷﺘﻪ و ﺣﺘﯽ ﻣﻄﻠﻮب اﺳﺖ. اﯾﻦ در ﺣﺎﻟﯽ اﺳﺖ ﮐﻪ در ﻫﺪف دوم ﺣﺠﻢ ﺑﺴﯿﺎر اﻧﺪﮐﯽ از داده ﻣﯽﺑﺎﯾﺴﺖ ﺑﻪ ﻧﺤﻮی در رﺳﺎﻧﻪ ﭘﻨﻬﺎن ﺷﻮﻧﺪ ﮐﻪ در ﻣﻘﺎبل اﻧﻮاع ﺗﻐﯿﯿﺮات رﺳﺎﻧﻪ از ﺧﻮد ﻣﻘﺎوﻣﺖ ﻧﺸﺎن داده و ﺣﺪاﻗﻞ ﺧﺮاﺑﯽ در آﻧﻬﺎ ﭘﯿﺶ آﯾﺪ.

درﺣﻮزهﭘﻨﻬﺎنﺳﺎزی و رمزنگاری دادهﻫﺎ ﺳﻪ ﻣﻔﻬﻮم ﻧﺰدﯾﮏ ﺑﻪ ﯾﮑﺪﯾﮕﺮ وﺟﻮد دارﻧﺪ ﮐﻪ ﻻزم اﺳﺖ ﭘﯿﺶ از ورود ﺑﻪ ﻫﺮ ﺑﺤﺜﯽ در ﺧﺼﻮص ﻫﺮﮐﺪام از آنﻫﺎ ﺧﺼﻮﺻﯿﺎﺗﺸﺎن ﻣﻌﺮﻓﯽ ﮔﺮدد ﺗﺎ اﻣﮑﺎن ﺗﻔﮑﯿﮏ ﺣﻮزه در ﻫﻨﮕﺎم ﺷﺮح ﻣﻮﺿﻮع وﺟﻮد داﺷﺘﻪﺑﺎﺷﺪ. اﯾﻦ ﺳﻪ ﻣﻔﻬﻮم ﻋﺒﺎرﺗﻨﺪاز:

• پنهان­ نگاری دادهﻫﺎ

• نرم افزار، برای مثال: تست ناکافی، فقدان پیگیری.

• شبکه، برای مثال: خطوط ارتباطی محافظت نشده، معماری شبکه ناامن.

• کارکنان، برای مثال: روند جذب ناکافی، آگاهی­های امنیتی ناکافی.

• مکان، برای مثال: منطقه مستعد سیل،منبع برق غیر قابل اعتماد.

• سازمانی، برای مثال: عدم پیگیری منظم، عدم تداوم برنامه­ها.

3-1-1- علت­های ایجاد آسیب پذیری­ها

برخی از منابع و علت­های ایجاد آسیب پذیری­ها عبارتند از:

• پیچیدگی سیستم: احتمال وجود نقص و نقاط دسترسی ناخواسته در سیستم­های بزرگ پیچیده، بیشتر است (8).

• متعارف بودن سیستم: استفاده از کدها، نرم افزارها، سیستم عامل­ها یا سخت افزارهای معمول و معروف، احتمال اینکه یک مهاجم بتواند به دانش و ابزار، جهت بهره کشی از نقص موجود دسترسی پیدا کند، را افزایش می­دهد (9).

• اتصال: اتصالات فیزیکی، امتیازات[1]، پورت­ها، پروتکل­ها و سرویس­های بیشتر و افزایش مدت زمان هر یک از آن­ها، دسترسی پذیری به آسیب پذیری­ها را افزایش می­دهد (7).

• نقص در مدیریت پسوردها: کاربران کامپیوتر از پسوردهای ضعیفی که با تلاش اندکی کشف می­شوند، استفاده می­کنند یا اینکه آن­ها را در برخی برنامه­ها ذخیره می­کنند، و این پسوردها بین بسیاری از برنامه­ها و صفحات وب­ مشترک است (8).

• نقص­های طراحی در سیستم عامل­های اصلی: طراحان سیستم عامل­ها، عموماً سیاست­هایی که کمتر کاربر/مدیر سیستم را درگیر کنند را برمی­گزینند. برای مثال سیستم عامل­ها، سیاست­هایی مثل پیش فرض­های اعطای مجوز به هر برنامه و دسترسی کامل کاربران به سیستم را دارند (8).این نقص­های سیستم عامل­ها، به ویروس­ها و بدافزارها، اجازه اجرای دستوراتی از طرف مدیر را می­دهد (1).

• مروروب­سایت­های اینترنت: برخی وب سایت­های اینترنتی دارای جاسوس­ها یا تبلیغات خطرناکی هستند، که می­توانند به صورت خودکار روی سیستم­های کامپیوتری نصب شوند. بعد از بازدید از این وب سایت­ها سیستم­ها آلوده می­شوند، اطلاعات شخصی جمع آوری شده و برای شخص ثالث فرستاده می­شود (10).

• اشکلات نرم افزاری: اشکلات قابل بهره کشی در بسیاری برنامه­های نرم افزاری وجود دارد. اشکلات نرم افزاری ممکن است به مهاجمان اجازه سوء استفاده از برنامه را بدهند (8).

• ورودی­های کاربر کنترل نشده: برنامه­ها فرض می­کنندکه همه­ی ورودی­های کاربر امن است. برنامه­هایی که ورودی­های کاربر را بررسی نمی­کنند، در واقع امکان اجرای مستقیم دستورات ناخواسته و دستکاری در پایگاه داده­ها را فراهم می­کنند (8).

4-1-1- شناسایی و حذف آسیب پذیری­ها

تلاش­های زیادی در جهت ساخت نرم افزارهایی با قابلیت کشف خودکار آسیب پذیری­های سیستم­های کامپیوتری انجام شده است. اگرچه نرم افزارهای موجود می­توانند در برخی موارد دید کلی خوبی را نسبت به آسیب پذیری­های سیستم فراهم کنند، اما نمی­توانند جایگزین بررسی انسانیروی آسیب پذیری­ها شوند. تکیه بر گزارشات اسکنرها، دید محدود همراه با تشخیص­های اشتباه زیاد، به همراه خواهد داشت. آسیب پذیری­ها در همه­ی نرم افزارهای اساسی مثل سیستم عامل­ها وجود دارند. گاهی اوقات تنها راه حل اساسی مقابله با آن­ها نصب بسته نرم افزاری اصلاح شده آن محصول است و در فاصله زمانی کشف تا ارائه بسته نرم افزاری با روش­هایی مثل استفاده از دیوار آتش و یا نظارت مستقیم بر کنترل­های دسترسی توسط ناظران سیستم­ها، می­توان جلوی سوء استفاده از سیستم را گرفت. لازم به ذکر است که روش­های نظارت مستقیم بر سیستم­ها، هم از نظر مالی و هم از نظر نیروی انسانی بسیار هزینه بر هستند.

2-1- مفاهیم اولیه­ مورد نیاز

6.1. نوآوری تحقیق

آنچه بیش از همه به ­عنوان نوآوری در کار و بهبود روش­های گذشته مطرح است:

1. استفاده از یک الگوریتم معنایی مناسب به­همراه تشابه خطی در مرحله اول

1. استفاده از الگوریتم­های خوشه­بندی در مرحله دوم.

در این تحقیق برای بالا بردن دقت و سرعت در استفاده از اطلاعات از الگوریتم پیشرفته تر نسبت به کارهای قبلی استفاده شده است. الگوریتم ترکیبی که به جنبه معنایی تشابه نیز توجه داشته باشد. همچنین نتایج نهایی برای بررسی راحت تر و دقیق تر با استفاده از یک روش بهینه خوشه بندی طبقه بندی میشوند، تا دسترسی کاربر به اطلاعات نهایی راحتر و سریعتر باشد. به بیانی ساده تر اطلاعات نهایی خوانا وجامع باشند.

7.1. ساختار پایان نامه

این تحقیق شامل 5 فصل است که ترتیب فصول و موضوعات مطرح ­شده به­صورت کلی در زیر بیان شده­است:

1.7.1. فصل اول: کلیات(همین فصل)

در این فصل یک مقدمه از حوزه این تحقیق ارائه ­شده و در آن مشخص­شده که هدف از این تحقیق چیست و خواهان پاسخ­گویی به چه سوالی هستیم. در ادامه همین فصل یک توضیح مختصر از تحقیقات انجام­شده در مورد موضوع این تحقیق ارائه ­شده است. در نهایت نیز یک دید کلی از فصل­های مختلف این تحقیق ذکر شده­است.

2.7.1 .فصل دوم: ادبیات تحقیق

در این فصل به بیان مفاهیم و مقدماتی که این پایان­نامه بر اساس آن مطرح­ شده­­است، پرداخته ­می­شود. مخازن خطای ­نرم­افزار و انواع آن­ها، چرخه ­عمر یک خطا، همچنین انواع مستندات مرتبط با یک خطا بررسی­می­شود. پس­از آن استراتژی­های اندازه­گیری تشابه ­معنایی بین متون و تفاوت آن­ها مورد مطالعه قرار می­گیرد.

3.7.1. فصل سوم : استفاده از تکنیک­های داده ­کاوی برای کشف و رفع خطاهای نرم ­افزار بر پایه ضریب تشابه­ معنایی متن و خوشه­ بندی

ضریب ­تشابه رشته ای یا خطی بر پایه LCS ، روش SOC-PMI به­عنوان یک روش معنایی و تشابه جملات بر اساس عبارات مشترک معرفی­می شوند. و در نهایت روش اندازه­گیری شباهت ترکیبی با ادغام و بهینه­سازی این روش­ها معرفی می­شود. روش­های خوشه­بندی و محاسبه میانگین داده­ها مورد نیاز این تحقیق هم بیان می­شوند. روش پیشنهادی با استفاده­از استراتژی­ها و روش­های انتخاب­شده که با محیط ­داده­ای مخازن سازگار هستند، برای یافتن خطای مشابه­تر با خطای ­جدید تشریح ­می­شود و توضیح­می­دهیم که چگونه با یک خوشه­بندی و محاسبه می­توانیم میزان پیچیدگی و تخمینی برای زمان رفع­خطا ارائه­کرد.

4.7.1.فصل چهارم:اعتبارسنجیو توسعه

پیاده سازی روش بر روی نمونه داده_­های واقعی که از مخزن خطا استخراج ­شده با استفاده از برنامه­نویسی و نرم­افزار Rapid miner[12]، مقایسه روش از نظر زمان و دقت پاسخ­گویی با روش­های دیگر. همچنین روش ارائه ­شده را با روشهای قبلی مورد مقایسه و تحلیل موضوعی قرار می­دهیم.

5.7.1. فصل پنجم : نتیجه گیری

در این فصل به جمع­بندی، نتیجه­گیری و تبیین دستاورد­ها و کارهای آینده پرداخته می­شود. ویژگی­های این روش با روش­های دیگر مقایسه ­شده و زمینه­های بهبود و نتایج به صورت موردی بیان می­شود. از آنجا که استفاده از تشابه معنایی در این زمینه در قدم­های اولیه قرار دارد، در آینده زمینه­های زیادی برای کار بیشتر وجود دارد که به چند مورد در این فصل اشاره خواهد شد.

[1]-Knowledge Discovery and Data Mining(KDD)

[2]-Software Repositories

3-2-5- مدیر قفل و مراحل انجام شده برای قفل گذاری……………………….. 27

3-2-6- نحوه در اختیار قرار دادن قفل توسط مدیر قفل……………………….. 28

3-2-7- قفل چند اسلوبی……………………….. 28

3-2-7-1- ماتریس همایندی یا سازگاری قفل های چند اسلوبی……………………….. 28

3-2-7-2- پروتکل قفل چند اسلوبی برای یک تراکنش…………………………. 29

3-2-7-3- تغییر قفل……………………….. 30

3-2-7-4- قفل چند اسلوبی و توالی پذیری……………………….. 30

3-2-7-5- خصوصیات قفل چند اسلوبی……………………….. 30

3-2-8- تکنیک قفل گذاری دو مرحله ای مبنایی……………………….. 30

3-2-8-1- مشکلات تداخل کنترل نشده ………………………31

3-2-8-2- خصوصیات و مشکلات 2PL مبنایی……………………….. 32

3-2-8-3- تغییر قفل در پروتکل 2PL………………………..

3-2-8-4- تأثیرعملیات درج در کنترل همروندی……………………….. 33

3-2-8-5- تأثیرعملیات حذف در کنترل همروندی……………………….. 33

3-3- بن بست………………………… 34

3-3-1- راه حل های مشكل بن بست………………………… 35

3-3-2- تکنیک های زمان مهر………………………. 36

3-3-2-1- الگوریتم WD………………………..

3-3-2-2- الگوریتم WW…………………………

3-3-2-3- خصوصیات الگوریتم WD و WW…………………………

فصل چهارم: شبکه های پتری

مقدمه………………………. 39

4-1- مختصری در مورد شبکه های پتری……………………….. 39

4-2- تفاوت UML و پتری……………………….. 39

4-3- تاریخچه شبکه های پتری……………………….. 40

4-4- ویژگی های شبکه های پتری……………………….. 40

4-5- اجزای شبکه ی پتری……………………….. 40

4-5-1- تعریف اجزای شبکه ی پتری………………………. 41

4-5-2- وظایف اجزای شبکه ی پتری……………………….. 41

4-6- تعریف چهارگانه شبکه های پتری……………………….. 42

4-7- گراف شبکه پتری……………………….. 42

4-8- چند مثال از گراف شبکه پتری……………………….. 43

4-9- رفتار شبکه های پتری……………………….. 43

4-10- گذار توانا……………………… 44

4-11- مثالی از اجرای یک شبکه پتری……………………….. 44

4-12- قوانین مربوط به فایر شدن گذار، در شبکه پتری……………………….. 45

4-13- شبکه های پتری به بن بست رسیده، زنده و غیر زنده……………………… 46

4-14- انواع شبکه های پتری و نحوه ی نشانه گذاری آن ها……………………… 47

4-15- فلوچارت ها و شبکه های پتری……………………….. 47

4-16- انواع پتری……………………….. 48

4-16-1- شبکهپتری رنگی……………………….. 48

4-16-2- شبکه پتری زمانی……………………….. 49

4-16-3- شبکه پتری سلسله مراتبی……………………….. 50

فصل پنجم: نحوه ی مدل سازی مکانیزم های 2PL، WW و WD با پتری رنگی

مقدمه………………………. 52

5-1- مختصری در مورد مدل سازی مکانیزم های 2PL، WW و WD………………

5-1-1- مدل 2PL………………………..

5-1-2- مدل های WW و WD………………………..

5-2- مجموعه های رنگ………………………… 53

5-2-1- مجموعه های رنگ در مدل 2PL………………………..

5-2-2- مجموعه های رنگ در مدل های WW و WD………………………..

5-2-3- توضیحات مجموعه های رنگ………………………… 55

5-3- نشانه گذاری اولیه………………………. 58

5-3-1- نشانه گذاری اولیه در مدل 2PL………………………..

5-3-2- نشانه گذاری اولیه در مدل های WW و WD………………………..

5-3-3- توضیحات نشانه گذاری اولیه………………………. 59

5-4- متغیرها……………………… 61

5-4-1- متغیرهای مدل 2PL………………………..

5-4-2- متغیرهای مدل های WW و WD………………………..

5-5- شرح توابع مدل و عملکردهای آن ها……………………… 62

5-5-1- شرح توابع مشترک بین مدل های 2PL، WW و WD………………………..

5-5-2- شرح توابع مدل 2PL………………………..

5-5-3- شرح توابع مدل های WW و WD………………………..

5-6- اولویت های معین شده برای تعیین فایر شدن گذار مورد نظر از بین گذارهای فعال…….. 72

5-7- نحوه ی مدل سازی ها……………………… 73

5-7-1- نحوه مدل سازی مدل 2PL………………………..

5-7-2- نحوه مدل سازی مدل های WW و WD………………………..

فصل ششم: ارزیابی مدل های 2PL، WW و WD

مقدمه………………………. 79

6-1- مختصری در مورد اهمیت ارزیابی پایگاه داده‎ها……………………… 79

6-2- پارامتر تعداد تراکنش های وارد شونده به سیستم………………………. 80

6-2-1- بررسی مدل 2PL………………………..

6-2-2- بررسی مدل WW………………………..

6-2-3- بررسی مدل WD………………………..

6-2-4- مقایسه ی مدل های 2PL، WW و WD براساس پارامتر تعداد تراکنش ها…….. 82

6-3- پارامتر تعداد دستورات هر تراکنش…………………………. 83

6-3-1- بررسی مدل 2PL………………………..

6-3-2- بررسی مدل WW…………………………

6-3-3- بررسی مدل WD………………………..

6-3-4- مقایسه مدل های 2PL، WW و WD براساس پارامتر تعداد دستورات تراکنش ها ……..86

6-4- پارامتر تعداد داده های مشترک و غیر مشترک تراکنش ها ………………………88

6-4-1- بررسی مدل 2PL………………………..

6-4-2- بررسی مدل WW…………………………

6-4-3- بررسی مدل WD………………………..

6-4-4- مقایسه مدل های 2PL، WW و WD براساس پارامتر تعداد داده های مشترک و غیر مشترک تراکنش ها….. 91

6-5- پارامتر تعداد داده های مشترک در تراکنش هایی بدون داده غیر مشترک……………. 92

6-5-1- بررسی مدل 2PL………………………..

6-5-2- بررسی مدل WW…………………………

6-5-3- بررسی مدل WD………………………

6-5-4- مقایسه مدل های 2PL، WW و WD براساس پارامتر تعداد داده های مشترک در تراکنش هایی بدون داده غیر مشترک…. 96

6-6- نتیجه گیری……………………….. 97

6-7- پیشنهادات……………………….. 100

مراجع……………………….. 102

چکیده:

مسئله ی كنترل همروندی در پایگاه داده‎ها امری ضروری و با اهمیت است. اجرای همروند تراكنش‎ها در یك سیستم مدیریت پایگاه داده، ممكن است منجر به ناسازگاری شود. ناسازگاری بر اثر مقادیر نادرستی است كه برای داده‎های موجود، بر اثر تعارض و تداخل اجرای تراكنش ها به وجود می‎آید. الگوریتم های كنترل همروندی، جهت تضمین اجرای همروند چندین تراكنش كه به صورت همروند با داده‎های مشترك كار می‎كنند طراحی شده‎اند. در زمینه ی كنترل همروندی پایگاه داده‎ها، تحقیقات فراوانی صورت گرفته است كه نتیجه آن، الگوریتم های متنوع كنترل همروندی می‎باشد. با توجه به الگوریتم های متنوع در این زمینه و این واقعیت كه روز به روز بر اهمیت آن ها افزوده می‎شود، در حوزه ارزیابی الگوریتم های کنترل همروندی جای کارِ بسیاری وجود دارد.

در این پایان نامه ابتدا الگوریتم های کنترل همروندی قفل گذاری دو مرحله ای مبنایی و همچنین تکنیک های زخمی كردن-منتظر گذاشتن و منتظر گذاشتن-میراندن که جزء تکنیک های پیش گیری از بن بست هستند، مدل سازی شده اند. از آنجا که شبکه پتری رنگی قابلیت های مدل سازی بالایی دارد و یکی از بهترین روش ها برای تحلیل مکانیزم های کنترل همروندی است؛ مدل سازی ها با استفاده از پتری رنگی و نرم افزار CPN Tools ارائه شده اند. یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده که مثال ذکر شده شامل سه تراکنش و دو منبع است. سپس الگوریتم های ذکر شده ارزیابی گردیده اند. ارزیابی بر اساس پارامترها و معیارهایی مثل تعداد تراکنش های وارد شونده به سیستم، تعداد دستورات هر تراکنش، تعداد داده های مشترک و غیر مشترک بین تراکنش ها و تعداد داده های مشترک در تراکنش هایی بدون داده غیر مشترک، صورت گرفته است.

آزمایش ها چندین بار تکرار و نتایج میانگین گیری شدند. با مقایسه و انجام بررسی ها، این نتیجه به دست آمد که در حالت کلی الگوریتم زخمی كردن-منتظر گذاشتن نسبت به دو الگوریتم دیگر زمان اجرای بهتری دارد. الگوریتم منتظر گذاشتن-میراندن از نظر زمان اجرا با اختلاف زیادی در سطح بدتری نسبت به دو الگوریتم دیگر قرار دارد و الگوریتم قفل گذاری دو مرحله ای مبنایی به دلیل امکان رخ دادن بن بست، مشکلات فراوانی دارد.

فصل اول: مقدمه

1-1- مقدمه

اجرای همروند تراکنش ها در پایگاه داده ها با مشکلات بسیاری مواجه است. مکانیزم های کنترل همروندی، برای حفظ انزوا و عدم دخالت اجرا در میان تراکنش های متعارض و حفظ سازگاری پایگاه داده ها استفاده می شوند (a-Pashazadeh, 2012)، (b-Pashazadeh, 2012) و (Shu, and Young, 2002). به عبارت دیگر الگوریتم های کنترل همروندی، الگوریتم هایی هستند که باعث می شوند اجرای همروند چند تراکنش و اجرای متوالی آن معادل شود. مسئله ی كنترل همروندی در پایگاه داده‎ها امری ضروری و با اهمیت می‎باشد (Shu, and Young, 2002). در این زمینه مطالعات و تحقیقات فراوانی صورت گرفته است كه نتیجه ی آن، به وجود آمدن الگوریتم های متنوع كنترل همروندی می‎باشد. همچنین با توجه به گسترش روزافزون انواع پایگاه داده ها در سراسر جهان، نیاز به بررسی پروتکل های کنترل همروندی پایگاه داده ها، بیشتر نمایان می شود.

مدل سازی رسمی[1] از الگوریتم های کنترل همروندی در مطالعه ویژگی های مختلف آن ها بسیار مفید است (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). بررسی ها نشان می دهد که شبکه های پتری (PNs)[2] روش مناسبی برای مدل سازی رسمی مکانیزم های کنترل همروندی می باشند. شبکه های پتری انواع مختلفی دارند که یکی از آن ها شبکه پتری رنگی (CPN)[3] است. شبکه های پتری رنگی یکی از بهترین ابزارها برای مدل سازی الگوریتم های کنترل همروندی هستند (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). به همین دلیل در این پایان نامه نیز از این روش برای مدل سازی ها استفاده خواهد شد.

یکی از اصلی ترین مکانیزم های کنترل همروندی تکنیک قفل گذاری دو مرحله ای مبنایی (2PL)[4] است. این تکنیک کنترل همروندی از طریق قفل گذاری روی داده ها انجام می شود. قفل گذاری روی داده ها به تدریج که نیاز به دستیابی به آن ها پیش می آید صورت می گیرد و قفل گشایی از آن ها پس از دریافت تمام قفل های تراکنش رخ خواهد داد. در این تکنیک امکان رخ دادن بن بست وجود دارد، به همین دلیل دو مکانیزم پیش گیری از بن بست نیز مورد بررسی قرار خواهد گرفت.

مکانیزم منتظر گذاشتن-میراندن (WD)[5] یکی از الگوریتم های پیش گیری از بن بست است که در آن حق تقدم زمانی تراكنش ها براساس زمان مهر و لحظه ی ورودشان به سیستم رعایت نمی شود. یعنی در مکانیزم WD هیچ قانونی وجود ندارد که تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفل های مورد نیازش داشته باشد، به همین دلیل به آن الگوریتم نابازدارنده می گویند. در سمت مقابل، مکانیزم زخمی كردن-منتظر گذاشتن (WW)[6] وجود دارد که یکی از الگوریتم های پیش گیری از بن بست است که در آن حق تقدم زمانی تراكنش ها براساس زمان مهر و لحظه ورودشان به سیستم رعایت می شود. یعنی در مکانیزم WW تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفل های مورد نیازش دارد، به همین دلیل به آن الگوریتم بازدارنده می گویند.

در این پایان نامه تلاش بر این است که با مدل سازی مکانیزم های 2PL، WD و WW، امکان بررسی اجرای تراکنش ها از دیدگاه ها و جوانب مختلفی را فراهم کنیم. سپس به ارزیابی این الگوریتم ها بپردازیم و آن ها را با استفاده از پارامترهای مختلفی که در جدول 1-1، اشاره شده است بررسی کنیم. در این جدول، در ستون اول پارامترهایی که قرار است ما در این پایان نامه بر اساس آن ها مدل ها را ارزیابی کنیم مشاهده می شود. سپس در ستون های بعدی نام الگوریتم هایی که قبلاً توسط این پارامترها مورد ارزیابی قرار گرفته بوده اند، نحوه ی پیاده سازی یا مدل سازی آن ها و همچنین مراجعشان را مشاهده می کنید.

در هنگام مدل سازی یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده است. مثال ذکر شده شامل سه تراکنش و دو منبع است.

مدل سازی ها با استفاده از پتری رنگی و نرم افزار CPN Tools ارائه شده اند. در نهایت به ارزیابی هر سه الگوریتم پرداخته شده است و الگوریتم ها با معیارهای بیان شده در فوق مورد بررسی قرار داده شده اند. آزمایش ها چندین بار تکرار گردیده و از مقادیر میانگین گیری به عمل آمده است. نمودارهای لازم نیز جهت مقایسه ی آسان تر ترسیم و بررسی گردیده اند.

2-1- ساختار پایان نامه

این پایان نامه به فرم زیر سازماندهی شده است.

در فصل دوم پیشینه ی تحقیق و مطالب مرتبط آورده شده است. در این فصل یکمرورکلی بر کلیات مطلب، اهداف، پیشینه ی تحقیق و سایر کارهای انجام شده در این زمینه خواهیم داشت. در پیشینه تحقیق، می پردازیم به این که تا کنون چه الگوریتم هایی ارائه شده، ارزیابی از طریق چه روش هایی صورت گرفته است و مانند آن ها. همچنین تعدادی از پارامترها و معیارهای ارزیابی الگوریتم های کنترل همروندی را بررسی خواهیم نمود. علاوه بر آن بعضی روش های پیاده سازی و شبیه سازی موجود مانند پیاده سازی در مقیاس کوچک، شبیه سازی از طریق مدل مارکف، شبیه سازی از طریق شبکه های پتری و مانند آن ها را بررسی می کنیم و به مزایا و معایب آن ها اشاره ای خواهیم داشت. همچنین روش تجزیه و تحلیل از طریق صف نیز بطور مختصر مورد بررسی قرار می گیرد.